Mavzu: Kruskal algoritmi. Prima algoritmi. XoDеykstra-Prim algoritmi

Prim algoritmi haqida batafsil
Algoritmni 1930 yilda chex matematikasi Voytox Yarnik, keyinroq mustaqil ravishda 1957 yilda kompyuter olimi Robert C. Prim tomonidan ishlab chiqilgan. 1959 yilda Edsger Dijkstra tomonidan qayta kashf qilingan. Algoritm uchta asosiy bosqichda ifodalanishi mumkin;
N tugunlari va har bir qirraning tegishli og'irligi bilan bog'langan grafikni hisobga olgan holda,
1. Grafikdan ixtiyoriy tugunni tanlang va uni T daraxtiga qo'shing (bu birinchi tugun bo'ladi)
2. Daraxtdagi tugunlarga ulangan har bir qirraning og'irligini ko'rib chiqing va minimalini tanlang. T daraxtining boshqa uchidagi chekka va tugunni qo'shing va qirrani grafikdan olib tashlang. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Daraxtga n-1 qirralari qo'shilmaguncha, 2-qadamni takrorlang.
Bu usulda daraxt bitta ixtiyoriy tugun bilan boshlanadi va har bir tsikl bilan shu tugundan boshlab kengayadi. Demak, algoritm to'g'ri ishlashi uchun grafik bog'langan grafik bo'lishi kerak. Prim algoritmining asosiy shakli O (V ² ) vaqt murakkabligiga ega.
Kruskal algoritmi haqida
Jozef Kruskal tomonidan ishlab chiqilgan algoritm Amerika matematik jamiyati ishida 1956 yilda paydo bo'lgan. Kruskal algoritmini uchta oddiy qadam bilan ifodalash mumkin.
N tugunli grafik va har bir qirraning tegishli og'irligi hisobga olinsa,
1. Butun grafikning eng kichik og'irligi bo'lgan yoyni tanlang va daraxtga qo'shing va grafikdan o'chiring.
2. Qolganlardan, tsikl hosil qilmaydigan tarzda, eng kam vaznli chekkani tanlang. Daraxtga chekkasini qo'shing va grafikdan o'chiring. (Ikki yoki undan ortiq minimallar mavjud bo'lsa, birini tanlang)
3. Jarayonni 2 -bosqichda takrorlang.
Bu usulda algoritm eng kam qirrali bilan boshlanadi va har bir tsiklda har bir chekkani tanlashda davom etadi. Shuning uchun algoritmda grafikni ulash shart emas. Kruskal algoritmining vaqt murakkabligi O (logV) kkilik Huffman kodini qurish algoritmi
Huffman kodining qurilishi quyidagi algoritmga muvofiq mos keladigan ikkilik daraxtni qurishga qisqartiriladi:

Keling, kodlangan belgilar ro'yxatini tuzamiz, shu bilan birga biz bitta belgini satrdagi belgining paydo bo'lish chastotasiga teng vaznli bitta elementdan iborat daraxt sifatida ko'rib chiqamiz.
Ro'yxatdan eng kichik vaznga ega ikkita tugunni tanlang.
Og'irligi tanlangan tugunlarning og'irliklari yig'indisiga teng bo'lgan yangi tugun hosil qilamiz va unga ikkita tanlangan tugunni bolalar sifatida biriktiramiz.
Keling, ikkita birlashtirilgan tugun o'rniga yangi tashkil etilgan tugunni ro'yxatga qo'shamiz.
Agar ro'yxatda bir nechta tugun bo'lsa, ikkinchidan beshinchigacha bosqichlarni takrorlang.
Ish vaqti
Har bir yig'indidan so'ng elementlarni tartiblasangiz yoki ustuvor navbatdan foydalansangiz, algoritm O(NlogN) vaqtida ishlaydi.
.Bu asimptotikani O(N) ga yaxshilash mumkin.
, muntazam massivlar yordamida.

Misol

Abrakadabra so'zi uchun Huffman daraxti
Keling, abrakadabra so'zini kodlaylik
. Keyin alifbo A={a,b,r,c,d} bo'ladi.
, va og'irliklar to'plami (kodlangan so'zda alifbo belgilarining paydo bo'lish chastotasi) W={5,2,2,1,1}
:

Huffman daraxtida 5 ta bo'ladi
tugunlar:

D bilan a b r tugun
Og'irligi 5 2 2 1 1
Algoritmga ko'ra, biz eng past chastotali ikkita belgini olamiz - bu c
va d
. Ulardan yangi tugun diskini hosil qilaylik
vazn 2
va uni tugunlar ro'yxatiga qo'shing:

Tugun a b r cd
Og'irligi 5 2 2 2
Keyin yana bitta tugunga minimal og'irlikdagi ikkita tugunni birlashtiramiz - r
va CD
:

Tugun a rcd b
Og'irligi 5 4 2
Keling, xuddi shu operatsiyani yana bir bor takrorlaymiz, lekin rcd tugunlari uchun
va b
:

Tugun brcd a
Og'irligi 65
Oxirgi bosqichda biz ikkita tugunni birlashtiramiz - brcd
va a
:

abrcd tugun
Og'irligi 11
Bitta tugun qoldi, ya'ni biz Huffman daraxtining ildiziga keldik (rasmga qarang). Endi har bir belgi uchun biz kod so'zini tanlaymiz (daraxt orqali ildizdan ushbu belgiga boradigan yo'lni bildiruvchi ikkilik ketma-ketlik):

a b r belgisi d bilan
Kod 0 11 101 1000 1001
Shunday qilib, kodlangan so'z abrakadabra hisoblanadi
01110101000010010111010 kabi ko'rinishga ega bo'ladi
. Kodlangan so'zning uzunligi 23 ga teng
bit. Shuni ta'kidlash kerakki, agar biz barcha kodli so'zlarning uzunligi bir xil bo'lgan kodlash algoritmidan foydalansak, kodlangan so'z 33 ni oladi.
bit, bu ancha katta.

Huffman algoritmining to'g'riligi
Huffman algoritmining to'g'riligini isbotlash uchun biz optimal prefiks kodini qurish masalasi ochko'z tanlov va optimal quyi tuzilma xususiyatlarini namoyish etishini ko'rsatamiz. Quyidagi lemma ochko'z tanlov xususiyatiga ega ekanligini ko'rsatadi.

Lemma (1):
C bo'lsin
— alifbo, har bir belgi c∈C
f[c] chastotasi bilan sodir bo'ladi
. X bo'lsin
va y
- alifboning ikkita belgisi C
eng past chastotalar bilan. Keyin C alifbosi uchun
optimal prefiks kodi mavjud, belgilar kod so'zlari x
va y
unda ular bir xil maksimal uzunlikka ega va faqat oxirgi bitda farqlanadi.