|
Primning minimal tejamkor daraxti (MST)
|
| bet | 3/3 | | Sana | 07.07.2024 | | Hajmi | 1,86 Mb. | | #266910 |
Primning minimal tejamkor daraxti (MST).
Dijkstraning algoritmi og'irligi qirralari salbiy bo'lgan grafikalar uchun ishlamaydi. Salbiy vazn qirralariga ega grafikalar uchun Bellman-Ford algoritmidan foydalanish mumkin, yaqin orada biz uni alohida post sifatida ko'rib chiqamiz.
Prim algoritmi grafika uchun barcha tugunlarni bog'laydigan va barcha tugunlarni bog'laydigan daraxtlar orasida eng kam xarajat keltiradigan daraxt bo'lgan minimal grafik daraxtini quradi . Biroq, MSTdagi har qanday ikkita tugun orasidagi yo'lning uzunligi asl grafikdagi ushbu ikki tugun orasidagi eng qisqa yo'l bo'lmasligi mumkin. MSTlar oydali bo'ladi, masalan, agar siz grafikadagi tugunlarni elektr energiyasini eng kam xarajat bilan ta'minlash uchun jismonan o'tkazmoqch ibo'lsangiz. Ikkala tugun orasidagi yo'l uzunligi eng maqbul bo'lmasligi muhim emas, chunki siz ularni bog'lab qo'yishingizni istaysiz.
Dijkstra algoritmi ba'zi bir manbali tugunlardan boshlab eng qisqa yo'l daraxtini quradi . Qisqa yo'l daraxti – bu grafikadagi barcha tugunlarni qaytariladigan manba tuguniga bog'laydigan va har qanday yo'lning grafikadagi boshqa tugungacha bo'lgan uzunligi minimallashtirilgan xususiyatdir. Bu foydalidir, masalan, agar siz bironbir muhim muhim joyga etib borishga imkon beradigan darajada yo'l tarmog'ini qurmoqchi bo'lsangiz. Biroq, engqisqa yo'l daraxti minimal daraxt bo'lishi kafolatlanmaydi va eng qisqa yo'lli daraxtning chekkalari xarajatlari MST narxidan ancha katta bo'lishi mumkin.
Yana bir muhim farq algoritmlarning qaysi grafik turlari ustida ishlashiga bog'liq. Prim algoritmi faqat yo'naltirilmagan grafiklar ustida ishlaydi, chunki MST tushunchasi grafiklarning yo'naltirilmaganligini anglatadi. (Yo'naltirilgan grafikalar uchun "minimal tejamkorlik" deb nomlangan narsa bor, ammo ularni topish algoritmlari ancha murakkab). Dijkstraning algoritmi yo'naltirilgan grafikalarda yaxshi ishlaydi, chunki eng qisqa daraxt daraxtlarini chindan ham yo'naltirish mumkin. Bunga qo'shimcha ravishda, Dijkstra algoritmi salbiy qirralarni o'z ichiga olgan grafiklarda to'g'ri echimni ta'minlamaydi , Prim esa algoritmi bunga qodir.
Men ko'rgan yagona farq shundaki, Prim algoritmi minimal xarajatlar chegarasini saqlaydi, Dijkstra algoritmi esa manba uchidan hozirgi verteksgacha bo'lgan umumiy xarajatlarni saqlaydi.
Dijkstra sizga xarajatlar minimal bo'lishi uchun manba tugunidan maqsad tuguniga yo'l beradi. Ammo Prim algoritmi sizga barcha tugunlar ulanishi va umumiy xarajat minimal bo'lishi uchun minimal daraxtni beradi.
Oddiy so'zlar bilan:
Shunday qilib, agar siz bir nechta shaharlarni ulash uchun poezdni joylashtirmoqchi bo'lsangiz, siz Prim algoritmidan foydalanasiz. Ammo agar siz bir shahardan ikkinchisiga imkon qadar ko'proq vaqt tejashnii stasangiz, Dijkstra algoritmidan foydalangan bo'lar edingiz.
Natijada, eng yaxshi Primning minimal tejamkor daraxti (MST)-ni topadi va uni ekranga chiqaradi.
Xulosa:
Prima-Dijkstra algoritmi, grafikning minimum yo‘l tarmog‘ini topishda qo‘llaniladigan, ammo bir-biriga aylanmagan algoritmdir. Bu algoritm orqali bir grafikning minimum yo‘l tarmog‘i topiladi. Grafikning barcha tugunlari orasida boshlang‘ich tugun (boshlang‘ich tugunni tanlangan qo‘shilish tartibiga qarab) bilan boshlaydi. Keyin qo‘shilgan tugunlar orasidan minimum bog‘lanish bo‘yicha o‘zgaruvchilar (masalan, yo‘l uzunligi) ni hisoblab, eng kam qiymatga ega bo‘lgan tugunni tanlab, uni birinchi yulduz bo‘yicha qo‘shish jarayonini boshlaydi. Keyin, yangi qo‘shilgan tugun orqali yuqori o‘zgaruvchilarni hisoblab, ulardan minimum qiymatga ega bo‘lgan tugunlarni tanlab, ularni ham yulduzlar bo‘yicha qo‘shishni davom ettiradi.
Bu algoritmning xulosa qismi uni imkoniyatlar va cheklovlar uchun to‘liq ishlatishning bir xulosasini taklif qiladi. Prima-Dijkstra algoritmi eng kam yo‘l uzunligi bo‘yicha tugunlarni birlashtirib, eng kam yo‘l uchun eng qisqa yo‘l tarmog‘ini topadi. Lekin, algoritm bilan yoki uning ishlash jarayonlarida cheklanmagan yo‘l o‘rnatishda boshqacha variantlarni hisobga olish lozim. Bu qisqa vaqt ichida yo‘l topish uchun ishlatiladigan eng yaxshi algoritmlardan biri.
Foydalanilgan adaabiyotlar ro’yxati:
1.https://www.cyberforum.ru/cpp-beginners/thread638112.html
2.https://www.youtube.com/watch?v=W7U4OVjVMx0
3.https://oefen.uz/ru/documents/diplom-ishlar/umumiy/deykstra-algoritmi
4.https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
5. https://oefen.uz/ru/documents/slaydlar/umumiy/tarmoqda-eng-qisqa-masofani-topish-masalasi-dyekstr-algoritmi
6.https://soff.uz/product/xborotlshtirish-v-kutubxonshunoslik-prime-deykstra
|
| |
