“Ochko`z” Algoritmlar. Kruskal algoritmi. Prima algoritmi. Xoffman daraxti
Download 222.03 Kb. Pdf ko'rish
|
Ochko\'z algoritmlar
|
“Ochko`z” Algoritmlar. Kruskal algoritmi. Prima algoritmi. Xoffman daraxti. Bizga ma’lumki, hozirda aholi punktlari orasidagi yo`llarni, aloqa tarmoqlari kanallarini, suv, gaz uzatish va kanalizasiya quvurlarini loyixalashda axborot yoki moddiy resurslarni uzatish harajatlari bilan bog`liq masalalar yuzaga keladi. Bunday masalalarni matematik modellashtirishda graflar nazariyasidan foydalanish va matematik modellar bo`yicha eng yaxshi variantini tahlil qilish va optimal variantlarini tanlash mumkin bo`ladi. Ushbu yondashuvning qulayligi shundaki, biz masalaning fizik parametrlariga vaqtincha e’tibor bermasdan turib, matematik masalani yechishimiz va shundan so`ng dastlabki masalaga qaytib, olingan natijalarini berilgan masalaga mos ravishda tahlil qilishimiz mumkin. Bizga bog`langan, yo`naltirilmagan graf berilgan bo`lib, uning qirralari ma’lum vaznlarga ega bo`lsin. Vaznlar- bu shunday sonlarki, ular berilgan qirralarning chekka uchlari orasidagi masofasini bildiradi, bu qirra bo`ylab xarakatlanishda transport xarajatlarini yoki boshqa xarajatlarni anglatadi. “Xasis algoritmlar” nomi bilan birlashtirilgan algoritmlar grafning shunday A va D uchlari orasidagi marshrutni (yo`nalishni) topishga qaratilganki, u eng arzon (eng kam xarajatli) bo`lishi kerak. Tabiiyki, bunday masalalarni yechishda biz avval A va D uchlari orasidagi barcha mumkin bo`lgan yo`nalishlarni aniqlab, shundan so`ng ushbu yo`nalishlarni eng kam xarajatliligini tanlaymiz. Ushbu turdagi ma’lum masalalardan biri “kommivoyajer masalasi” bo`ladi. Agar biror grafni tasavvur qilsak va uning uchlari qaysidir tashkilotning bo`limlarini va qirralari esa shu bo`limlar orasidagi yo`lini anglatsa, u xolda kommivoyajer– ushbu tashkilotning xodimi, hamma bo`limlarni aylanib chiqib, yana o`zining idorasiga qaytishi kerak bo`ladi. Bunda u eng kam xarajatli yo`nalishni tanlashi kerak bo`ladi. Boshqacha qilib aytganda kommivoyajer grafda eng kam xarajatli Gamilton siklini tanlashi kerak. Shunga o`xshash ko`plab masalalar biror kommunikasiya tarmoqlari bilan bog`liq graf uchun ham vujudga kelishi mumkin. Shuning uchun dastlabki ishlanmalarni oldindan xozirlab qo`yish maqsadga muvofiq bo`lib, ular asosida masala yechimi tezlashib boradi. Buning uchun berilgan graf asosida eng arzon (kam xarajatli) graf qurilib, bu graf ostovdaraxti deyiladi. Keyinroq ko`ramizki, bu daraxt minimal marshrutlar topishda effektiv vosita bo`ladi. Ostov daraxti qurish usullarining birini tasvirlashga o`tamiz. Download 222.03 Kb. Do'stlaringiz bilan baham: 
|