|
Primo algoritmi
Ushbu algoritm dastlab 1930 yilda chesh matematigi Voysex Yarnik tomonidan taklif etilgan. Keyin Robert Primo tomonidan 1957 yilda qayta ko’rib chiqilgan va ulardan tashqari E. Deykstratomonidan 1959 yilda ishlab chiqilgan.
Algoritm kirishiga yo’naltirilmagan og’irlikka ega bo’lgan graf uzatiladi.
Boshida istalgan tugun olinadi va unga tegishli bo’lgan eng kam vaznga ega insident yoy topiladi. Topilgan yoy va unga tegishli tugunlar daraxtni shakllantira boshlaydi.
Keyin bir uchi bilan daraxtga tegishli bo’lgan tugunlariga tutashgan va ikkinchi uchi esa tutashmagan boshqa yoylar xam tekshiriladi. Ulardan og’irligi kami tanlanadi.
Xar bir qadamdagi yoy daraxtga qo’shilib boraveradi. Daraxtning balandligi xam 1 taga oshib boraveradi. Grafning barcha tugunlari ko’rib chiqilmaguncha algoritm davom etaveradi.
Algoritm natijasi bo’lib minimal narxli daraxt skeleti xisoblanadi. E’tibor qaratish lozimki, minimal narxli daraxtlarni xosil qilishda xalqa paydo bo’lishiga yo’l qo’ymaslik kerak.
Misol keltiramiz.
tasvir
|
U tanlangan tugunlar to’plami
|
(u,v)yoylar
|
v\u tanlanmagan tugunlar
|
izox
|
|
{}
|
|
{A,B,C,D,E,F,G}
|
Dastlab daraxt tugunlar to’plami bo’sh
|
|
{D}
|
(D,A) = 5 V
(D,B) = 9
(D,E) = 15
(D,F) = 6
|
{A,B,C,E,F,G}
|
Ilk tugun sifatida Dolindi. Unga tegishli yoylar A,B,E,F tugunlarga olib boradi. Ularning minimal yoyligini tanlaymiz. ya’ni A
|
|
{A,D}
|
(D,B) = 9
(D,E) = 15
(D,F) = 6 V
(A,B) = 7
|
{B,C,E,F,G}
|
|
|
{A,D,F}
|
(D,B) = 9
(D,E) = 15
(A,B) = 7 V
(F,E) = 8
(F,G) = 11
|
{B,C,E,G}
|
|
|
{A,B,D,F}
|
(B,C) = 8
(B,E) = 7 V
(D,B) = 9 sikl
(D,E) = 15
(F,E) = 8
(F,G) = 11
|
{C,E,G}
|
(D,B)yoy tanlansa xalqa xosil bo’ladi. Shuning uchun uni tanlay olmaymiz.
|
|
{A,B,D,E,F}
|
(B,C) = 8
(D,B) = 9 sikl
(D,E) = 15 sikl
(E,C) = 5 V
(E,G) = 9
(F,E) = 8 sikl
(F,G) = 11
|
{C,G}
|
|
|
{A,B,C,D,E,F}
|
(B,C) = 8 sikl
(D,B) = 9 sikl
(D,E) = 15 sikl
(E,G) = 9 V
(F,E) = 8 sikl
(F,G) = 11
|
{G}
|
|
|
{A,B,C,D,E,F,G}
|
(B,C) = 8 sikl
(D,B) = 9 sikl
(D,E) = 15 sikl
(F,E) = 8 sikl
(F,G) = 11 sikl
|
{}
|
Grafdagi barcha tugunlar tekshirib bo’ldi.
|
Nazoratsavollar
Graflarnima?
Minimal narxlidaraxtlarnima?
U qaerlardavanimamaqsaddaishlatiladi?
Minimal narxlidaraxtniqurishniqandayalgoritmlarinibilasiz?
Adabiyotlar.
AdamDrozdek. Data structure and algorithms in C++. Fourthedition. 2013. Chapter 8.
14 – mavzu. Heap tree tuzilmasi, uni qurish va
ustida amal bajarish algoritmlari
Reja
Heap tree tuzilmasi tavsifi.
Heap tree ustida amal bajarish algoritmlari.
Heap treeni tashkil etish usullari va samaradorligi.
Kalit so’zlar: heap tree, element, algoritm, binar daraxt.
Heap tree tuzilmasi tavsifi
Heap tree so’zi inglizchadan olingan bo’lib, ikkilik uyurma daraxti degan ma’noni anglatadi va binar daraxtning bir turi bo’lib, binar daraxtdan quyidagi ikkita xususiyati bilan ajralib turadi.
Har bir tugun qiymati uning o’g’il tugunlari qiymatidan katta yoki teng (yoki kichik yoki teng bo’lishi ham mumkin);
Daraxt ideal muvozanatlangan, yoki daraxt barg tugunlari chapdan o’ngga qarab to’ldiriladi.
Agar xar bir tugun o’g’il tugunlatdan katta yoki teng bo‘lsa, bu uyurma daraxtiga max heap, aks holda ya’ni ota tugun farzandlardan kichik yoki teng bo’lsa, min heap deyiladi. Bu degani, max heap da maksimal element daraxt ildizida joylashadi, min heapda esa daraxtning ildizida minimal element joylashadi.
13.1-rasm. Heap tree (a) va heap tree bo’lmagan daraxtlar
Bu yerda rasmdagi a) heap tree va b),c) lar esa heap tree emas. Chunki b va c rasmda heap treening birinchi va ikkinchi xususiyatlari buzilgan mos ravishda. Qizig’I shuki, heap tree massiv yordamida yasalishi mumkin. Masalan, data[] = {2 8 6 1 10 15 3 12 11} massiv berilgan bo’lsin. Undan yuqoridan pastga va chapdan o’ngga elementlarni joylab daraxtni (heap tree bo’lmagan) xosil qilamiz. Bunday daraxtlarda bosqichlar soni O(lgn) gat eng.
13.2-rasm. Massivdan daraxt xosil qilish
Bu daraxtni heap tree ko’rinishida qayta tashkil etish uchun uzunligi n ga teng heap massivini quyidagi shartlarga asoslanib tashkil etamiz:
heap[i] ≥ heap[2·i], for 0 ≤ i<
va
heap[i] ≥ heap[2·i + 1], for 0 ≤ i<
heap tree elementlari tartiblanmagan hisoblanadi.
Boshqacha qilib aytadigan bo’lsak, sonlar ketma-ketligidan heap treeni qurish uchun
1-elementni daraxt ildizi qilib olamiz.
Har qanday i-element uchun quyidagi o’rinli:
Uning chap o’g’il tuguni 2*i indeksda
O’ng o’g’il tuguni esa 2*i+1 indeksda
Uning ota tuguni i/2 indeksda bo’ladi.
13.3-rasm. Heap tree
Ya’ni 1-elementni ildiz qilib olgach, qolgan elementlarni chapdan o’ngga qarab daraxtni to’ldirib ketiladi. Xar bir ildizda faqat ikkita o’g’il tugun chiqishi kerak. Agar shunday tartibda elementlar joylashtirilib chiqadigan bo’lsa, xar bir a[i]-o’rinda turgan ota tugunning chap tomoniga a[2*i]-element va o’ng tomoniga esa a[2*i+1]-element joylashadi. Quyida bir xil sonlardan turlicha heap tree xisol qilinganligi keltirilgan:
13.4 – bir xil sonlardan tashkil topgan heap tree tuzilmalari
13.5. Heap treeni to’g’ri va noto’g’ri tashkil etilganligi.
Bu min-heapmi yoki yo’q?
Heap tree nimaga kerak?
Heap tree prioritetli navbatni ifodalashda juda qo’l keladi. Eng kerakli element tuzilma eng yuqorisida joylashadi. Agar u o’chirilsa, elementlar qayta joylashtirilishi zarur. Bu tuzilma graflarda eng qisqa masofani aniqlash masalasini echish Dijkstra algoritmini samaradorligini oshirishda prioritetli navbatlardan foydalanilganda qo’l keladi. Bundan tashqari heap tree - samaradorligi O(nlogn) bo’lgan piramida saralash algoritmida ham qo’llaniladi.
Do'stlaringiz bilan baham: |
