Algoritmning tavsifi
Algoritmning o'zi juda oddiy. Kerakli minimal skelet, bir vaqtning o'zida qirralarni qo'shib, asta-sekin quriladi. Dastlab, skelet bitta vertexdan iborat deb taxmin qilinadi (u ixtiyoriy tanlanishi mumkin). Keyin, ushbu uchdan chiqadigan minimal og'irlik qirrasi tanlanadi va minimal oraliq daraxtga qo'shiladi. Shundan so'ng, skelet allaqachon ikkita cho'qqini o'z ichiga oladi va endi minimal og'irlikning chekkasi qidiriladi va qo'shiladi, bir uchi tanlangan ikkita cho'qqidan birida, ikkinchisi esa aksincha, bu ikkitadan tashqari qolganlarida. Va hokazo, ya'ni. har safar minimal og'irlik qirrasi qidiriladi, uning bir uchi allaqachon skeletga olingan uchdir, ikkinchi uchi esa hali olinmagan va bu chekka skeletga qo'shiladi (agar bir nechta bunday qirralar bo'lsa, siz istalganini oling). Ushbu jarayon kengaytma daraxti barcha uchlarini (yoki ekvivalenti, n-1 qirralarini) o'z ichiga olguncha takrorlanadi.Natijada, minimal bo'lgan skelet quriladi. Agar grafik dastlab ulanmagan bo'lsa, u holda hech qanday kengaytmali daraxt topilmaydi (tanlangan qirralarning soni n-1 dan kam bo'lib qoladi).
Amalga oshirish
Algoritmning ishlash vaqti, asosan, mos qirralar orasidan keyingi minimal qirrani qanday izlashimizga bog'liq. Turli xil asimptotiklarga va turli xil ilovalarga olib keladigan turli yondashuvlar bo'lishi mumkin.
amalga oshirish: O(nm) va O(n2 + m log n) algoritmlari
Agar har safar biz barcha mumkin bo'lgan variantlarni ko’rish orqali qirra izlasak, unda barcha mumkin bo'lganlar orasida eng kichik og'irlikdagi qirrani topish uchun asimptotik ravishda O(m) qirralarni ko’rish kerak bo'ladi. Bu holda algoritmning umumiy asimptotikasi O(nm) bo'ladi, bu eng yomon holatda O(n^3) bo'ladi, bu juda sekin algoritmdir.Bu algoritmni yaxshilash mumkin, agar har safar barcha qirralar emas, balki tanlangan har bir uchdan faqat bitta qirra tekshirilsa. Buni amalga oshirish uchun, masalan, har bir uchdan qirralarni og'irliklarning o'sish tartibida saralashingiz va ko'rsatgichni birinchi ruxsat etilgan chetiga saqlashingiz mumkin (esda tuting, faqat hali tanlanmagan uchlar to'plamiga olib keladigan qirralarga ruxsat beriladi). Keyin, agar skeletga har safar qirra qo'shilganda bu ko'rsatkichlarni qayta hisoblab chiqsak, algoritmning umumiy asimptotikasi O(n2 + m) bo'ladi, lekin avval O(m ) dagi barcha qirralarni tartiblash kerak bo'ladi. log n), bu eng yomon holatda (zich graf uchun) O(n2 log n) asimptotikani beradi.
Xulosa
Bizga ma’lumki, hozirda aholi punktlari orasidagi yo`llarni, aloqa tarmoqlari kanallarini, suv, gaz uzatish va kanalizasiya quvurlarini loyixalashda axboro tyoki 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. “Xasisalgoritmlar” nomi bilan birlashtirilgan algoritmlar grafning shunday A va D uchlari orasidagi marshrutni (yo`nalishni) topishga qaratilganki, u eng arzon (engkamxarajatli) 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 xarajatliligin itanlaymiz.
Foydalanilgan adabiyotlar
|
