"Алгоритмларни лойиҳалаш" фанидан маърузалар матни

“Алгоритмларни лойиҳалаш” фанидан маърузалар матни
11-маъруза
11 “ОЧКЎЗ” АЛГОРИТМЛАР. КРУСКАЛ АЛГОРИТМИ.ПРИМА АЛГОРИТМИ.ХОФФМАН ДАРАХТИ.
Бизга маълумки, ҳозирда аҳоли пунктлари орасидаги йўлларни, алоқа тармоқлари каналларини, сув, газ узатиш ва канализация қувурларини лойихалашда ахборот ёки моддий ресурсларни узатиш ҳаражатлари билан боғлиқ масалалар юзага келади. Бундай масалаларни математик моделлаштиришда графлар назариясидан фойдаланиш ва математик моделлар бўйича энг яхши вариантини таҳлил қилиш ва оптимал вариантларини танлаш мумкин бўлади. Ушбу ёндашувнинг қулайлиги шундаки, биз масаланинг физик параметрларига вақтинча эътибор бермасдан туриб, математик масалани ечишимиз ва шундан сўнг дастлабки масалага қайтиб,олинган натижаларини берилган масалага мос равишда таҳлил қилишимиз мумкин.
Бизга боғланган, йўналтирилмаган граф берилган бўлиб, унинг қирралари маълум вазнларга эга бўлсин. Вазнлар- бу шундай сонларки ,уларберилган қирраларнинг чекка учлари орасидаги масофасини билдиради, бу қирра бўйлабхаракатланишда транспорт харажатларини ёки бошқа харажатларни англатади.“Хасис алгоритмлар” номи билан бирлаштирилган алгоритмлар графнинг шундай А ва D учлари орасидаги маршрутни(йўналишни) топишга каратилганки, у энг арзон(энг кам харажатли) бўлиши керак. Табиийки, бундай масалаларни ечишдабиз аввал А ва D учлари орасидаги барча мумкин бўлган йўналишларни аниқлаб, шундан сўнг ушбу йўналишларни энг кам харажатлилигини танлаймиз.
Ушбу турдаги маълум масалалардан бири “коммивояжер масаласи” бўлади.Агар бирор графни тасаввур қилсак ва унинг учлари қайсидир ташкилотнинг бўлимларини ва қирралари эса шу бўлимлар орасидаги йўлини англатса,у холда коммивояжер–ушбу ташкилотнинг ходими, ҳамма бўлимларни айланиб чиқиб, яна ўзининг идорасига қайтиши керак бўлади. Бунда у энг кам харажатли йўналишни танлаши керак бўлади. Бошқача қилиб айтганда коммивояжер графда энг кам харажатли Гамильтон циклини танлаши керак.
Шунга ўхшаш кўплаб масалалар бирор коммуникация тармоқлари билан боғлиқ граф учун ҳам вужудга келиши мумкин.Шунинг учун дастлабки ишланмаларни олдиндан хозирлаб қўйиш мақсадга мувофиқ бўлиб,улар асосида масала ечими тезлашиб боради. Бунинг учун барилган граф асосида энг арзон(кам харажатли) граф қурилиб, бу граф остов дарахти дейилади. Кейинроқ кўрамизки,бу дарахт минимал маршрутлар топишда эффектив восита бўлади. Остов дарахти қуриш усулларининг бирини тасвирлашга ўтамиз.