|
Primning minimal tejamkor daraxti (MST)
|
| bet | 5/7 | | Sana | 15.05.2024 | | Hajmi | 46,46 Kb. | | #234563 |
Bog'liq sarviiiiii4. Primning minimal tejamkor daraxti (MST).
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 algosidan foydalanasiz. Ammo agar siz bir shahardan ikkinchisiga imkon qadar ko'proq vaqt tejashni istasangiz, Dijkstra algidan foydalangan bo'lar edingiz.
Ikkalasi ham xuddi shunday umumiy algoritm yordamida bajarilishi mumkin:
Inputs:
G: Graph
s: Starting vertex (any for Prim, source for Dijkstra)
f: a function that takes vertices u and v, returns a number
Generic(G, s, f)
Q = Enqueue all V with key = infinity, parent = null
s.key = 0
While Q is not empty
u = dequeue Q
For each v in adj(u)
if v is in Q and v.key > f(u,v)
v.key = f(u,v)
v.parent = u
Prim, pass f = w(u, v)va Dijkstra dovoni uchun f = u.key + w(u, v).
Yana bir qiziq tomoni shundaki, Generic-dan yuqorida "Bread" birinchi qidirishni (BFS) amalga oshirishi mumkin, ammo bu haddan tashqari ko'p bo'lishi mumkin, chunki qimmat ustunlik navbati aslida talab qilinmaydi. Yuqoridagi umumiy algoritmni BFS-ga o'tkazish uchun, f = u.key + 1barcha og'irliklarni 1 ga bog'lash bilan bir xil (masalan, BFS A nuqtadan B ga o'tish uchun zarur bo'lgan minimal qirralarni beradi).
Uni vaqt bo'yicha baholash
Algoritmning uni vaqt boʻyicha baholash (runtime analysis) muhimligi, algoritmlarning ishlashining necha martaqadir ishlayotgani vaqti bilan bog'liqdir. Bu aniq vaqt yuzaga kelishi odatda algoritmda ishlatilgan operatsiyalar va ma'lumotlar soni bilan bog'liqdir. Uni vaqt boʻyicha baholash, algoritmning ishga tushirish va ishlayotgan vaqtni o'rganish uchun foydali bo'ladi. Bu, algoritmning ish faoliyatida ishlatilgan yodgorlik (memory) xotirasiga, har bir ishlatilgan elementning qiymati va uning jadvallashuvi, shuningdek, ishlatilgan operatsiyalar kabi ko'plab faktorlarni ko'rsatishi mumkin.
Uni vaqt bo'yicha baholash, algoritmlarni boshqarishning va aniq yechim topishning bir qismi sifatida ham ishlatiladi. Masalan, bir dasturda eng yaxshi algoritmlardan foydalanish uchun, algoritmlarning ishlash vaqtlarini solishtirishdan foydalanish mumkin. Shuningdek, bir algoritmning uni vaqt bo'yicha baholashini tushunish, o'zida o'zgarishlarni qilish uchun to'g'ri vaqtida, qo'shimcha resurslar ishlatishni belgilash imkonini beradi.
Bular bilan birga, algoritmlarni tartibga solishda, ularning uni vaqt bo'yicha baholashini bilish katta ahamiyatga ega bo'ladi, shunda o'zgarishlarni qilish va hujjatlar bilan ishlashda aniq vaqtni belgilash mumkin bo'ladi.
Biz kruskalning minimal tejamkorlik daraxti uchun algoritmini muhokama qildik . Kruskalning algoritmi singari, Prim algoritmi ham ochko'z algoritmdir . U bo'shashgan daraxtdan boshlanadi. G'oya ikkita vertikal to'plamni ushlab turishdir. Birinchi to'plamda allaqachon MST-ga kiritilgan uchlari mavjud, ikkinchisida esa hali mavjud bo'lmagan uchlari mavjud. Har qadamda, u ikkita to'plamni bog'laydigan barcha qirralarni ko'rib chiqadi va bu qirralarning minimal og'irligini tanlaydi. Yonni tanlaganingizdan so'ng, u chetning boshqa oxirgi uchini MST o'z ichiga olgan to'plamga o'tkazadi.
Grafikdagi ikkita uch uchini bog'laydigan qirralar guruhi grafik nazariyasida kesilgan deb nomlanadi . Shunday qilib, Prim algoritmining har bir bosqichida biz kesmani topamiz (ikkita to'plam, bittasida allaqachon MST kiritilgan va boshqa vertikal qismlar mavjud), kesmaning eng kam og'irligini tanlang va bu uchni MST Set-ga qo'shing. (allaqachon kiritilgan uchlarini o'z ichiga olgan to'plam).
|
| |
