|
Prima algoritmi
Algoritmni 1930 yilda chex matematikasi Voytex Jarnik yaratgan va keyinchalik 1957 yilda kompyuter olimlari Robert C. Prim va 1959 yilda Edsger V.Daykstra tomonidan qayta kashf etilib, qayta nashr etilgan. Shuning uchun uni ba'zida Jarnik algoritmi, Prim – Jarnik algoritmi, Prim –Daykstra algoritmi yoki DJP algoritmi deb ham atashadi.
Algoritmning birinchi muallifi Voytex Jarnik 1897-yil 22-dekabrda Paragada tug’ilgan. 1921 yilda u tabiiy fanlar bo'yicha doktorlik dissertatsiyasini oldi. 1919-1921 yillarda u Brno texnika universitetida assistent bo'lib ishlagan. 1921 yildan - Pragadagi Charlz universitetida o'qituvchi. 1929-1967 yillarda - Praga universitetining matematika professori. 1930-yilda shu algoritmni yaratgan.
Algoritmning o'zi juda oddiy. Kerakli minimal skelet asta-sekin qirralarni birma-bir qo'shib quriladi. Dastlab skelet bitta tepadan iborat deb taxmin qilinadi (u o'zboshimchalik bilan tanlanishi mumkin). Keyin ushbu tepalikdan kelib chiqadigan minimal og'irlikdagi chekka tanlanadi va minimal skeletga qo'shiladi. Shundan so'ng, skelet allaqachon ikkita tepalikni o'z ichiga olgan va hozirda eng kam og'irlikdagi chekka qidiriladi va qo'shiladi, uning bir uchi tanlangan ikkita tepaning birida, ikkinchisida, aksincha, boshqa uchlari bor, bundan mustasno bu ikkitasi. Va shunga o'xshash narsalar, ya'ni har safar minimal og'irlik qirrasi izlanadi, uning bir uchi allaqachon skeletga kiritilgan tepalik bo'lib, boshqa uchi hali olinmagan va bu chekka skeletga qo'shilgan (agar shunday qirralar bir nechta bo'lsa, siz har qanday narsani oling). Bu jarayon skelet barcha tepaliklarni (yoki bir xil bo'lgan n-1 qirralarni) o'z ichiga olguncha takrorlanadi. Natijada minimal skelet quriladi. Agar grafik dastlab ulanmagan bo'lsa, unda skelet topilmaydi (tanlangan qirralarning soni n-1 dan kam bo'lib qoladi).
Daraxtning minimal qiymatini topish uchun Primning algoritmi (Kruskal algoritmi kabi) ochko'zlik usulidan foydalanadi. Primning algoritmi eng qisqa yo'l birinchi algoritmlari bilan o'xshashlikni taqsimlaydi.
Prima algoritmi, Kruskal algoritmidan farqli o'laroq, tugunlarni bitta daraxt sifatida ko'rib chiqadi va berilgan grafikadan yangi daraxt tugunlarini qo'shishda davom etadi.
Kruskal algoritmidan farqli o'laroq va Primning algoritmini yaxshiroq tushunish uchun biz o'sha misoldan foydalanamiz
1
1-rasm.
12-rasm.
1-qadam - barcha ko'chadan va parallel qirralarni olib
13-rasm.
Berilgan grafikadan barcha ko'chadan va parallel qirralarni olib tashlang. Parallel qirralar bo'lsa, eng kam xarajat bilan bog'liq bo'lgan narsalarni saqlang va boshqalarni olib tashlang
1
4-rasm
2-qadam - har qanday ixtiyoriy tugunni ildiz tuguni sifatida tanlang
Bunday holda biz S tugunini Primning yoyilgan daraxtining ildiz tuguni sifatida tanlaymiz. Ushbu tugun o'zboshimchalik bilan tanlangan, shuning uchun har qanday tugun ildiz tuguni bo'lishi mumkin. Nima uchun har qanday video ildiz tuguni bo'lishi mumkinligi haqida hayron bo'lish mumkin. Shunday qilib, shpal daraxtiga grafikaning barcha tugunlari kiritilgan va u bog'langanligi sababli, daraxtning qolgan qismiga qo'shiladigan kamida bitta chekka bo'lishi kerak.
3-qadam - Chiqib ketgan qirralarni tekshiring va arzonroq bo'lganini tanlang
S ildiz tugunini tanlagandan so'ng, biz S, A va S, C navbati bilan 7 va 8 og'irlikdagi ikkita qirralar ekanligini ko'ramiz. Biz S, A qirrasini tanlaymiz, chunki u boshqasidan kichikroq.
E
ndi S-7-A daraxti bitta tugun sifatida qaraladi va biz undan chiqib ketadigan barcha qirralarni tekshiramiz. Eng arzon narxni tanlaymiz va daraxtga kiritamiz
15-rasm
U
shbu qadamdan keyin S-7-A-3-C daraxti hosil bo'ladi. Endi biz uni yana tugun sifatida ko'rib chiqamiz va yana barcha qirralarni tekshiramiz. Biroq, biz faqat eng kam xarajatli tomonni tanlaymiz. Bunday holda, C-3-D yangi qirradir, bu
boshqa qirralarning narxiga nisbatan kamroq, 8, 6, 4 va boshqalar
16-rasm
D tugunini yoyilgan daraxtga qo'shgandan so'ng, endi biz ikkita qirraga teng narxga ega bo'lamiz, ya'ni D-2-T va D-2-B. Shunday qilib, ikkalasini ham qo'shishimiz mumkin. Ammo keyingi qadam yana eng kam xarajat sifatida 2-darajani beradi. Shunday qilib, biz ikkala qirrasi kiritilgan daraxt daraxtini ko'rsatmoqdamiz.
17-rasm
Ikki xil algoritmdan foydalangan holda bir xil grafadagi chiqish daraxti bir xil ekanligini aniqlashimiz mumkin.
Do'stlaringiz bilan baham: |
