Mavzu: Prima-Deyskrita Algaritmi. Uni vaqt bo`yicha baholash

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI
VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Mavzu:Prima-Deyskrita Algaritmi. Uni vaqt bo`yicha baholash.
Bajardi:Xoliyorova Muxlisa
Tekshirdi:Qo`ldoshev Hakim

Toshkent 2022

Reja:

1. 
   Prima-deyskrita algaritmi hamida
   
2. 
   Prima-deyskrita algaritmning berilishi
   
3. 
   Deyskrita algaritmining murakkabligi.
   

Prima-Deyskrita algaritmi haqida
Deykstra algoritmi -1959 yilda golland olimi Edsger Deykstra tomonidan ixtiro qilingan grafik algoritmdir. Grafikning bir cho'qqisidan qolgan barcha nuqtalarga eng qisqa yo'llarni topadi. Algoritm faqat manfiy og'irlikdagi qirralari bo'lmagan grafiklar uchun ishlaydi. Algoritm dasturlashda keng qo'llaniladi, masalan, OSPF va IS-IS marshrutlash protokollari tomonidan qo'llaniladi.
Primm algoritmi faqat n ta burchaklar orasidagi bogʻlanish muammosini grafigini qamrab oluvchi daraxt orqali hal qilibgina qolmay, balki umumiy xarajatni, yaʼni minimal xarajatlarni qamrab oluvchi daraxtni ham minimallashtiradi.
Avval quyidagi rasmda ko'rsatilganidek, Prim algoritmining g'oyasini qisqacha tushuntiriladi:

Birinchidan, birinchi rasm yo'naltirilmagan grafikdir. Biz 1 cho'qqini boshlang'ich nuqtasi sifatida belgilaymiz va ikkita U va W to'plamini o'rnatamiz. 1 cho'qqi va boshqa cho'qqilar orasidagi masofaga e'tibor bering. 3-cho'qqi eng qisqasi, shuning uchun biz 1-cho'qqini va 3-cho'qqini ajratamiz. To'g'ridan-to'g'ri to'g'ri chiziq, 3 cho'qqisi U to'plamiga joylashtirilgan va to'rtta raqam 2, 4, 5 va 6 W to'plamida qoladi;

Ikkinchi bosqich U dagi 1 cho‘qqi va 3 cho‘qqidan W dagi har bir cho‘qqigacha bo‘lgan masofalarni kuzatishdan iborat. Masalan, U dagi 1 cho‘qqidan W dagi 2 cho‘qqigacha bo‘lgan masofa 6 ga, U da 3 cho‘qqigacha bo‘lgan masofa. W dagi 2 cho'qqisi 5,5 < 6 ga teng, shuning uchun 3 cho'qqi va 2 cho'qqining nuqtali chiziqlari qoladi va hokazo, natijada ikkinchi grafik;
Eng kam og'irlikdagi chiziq chizig'ini topish uchun birinchi qadamni yana bajaring va uni qattiq chiziq sifatida torting va barcha cho'qqilarga tashrif buyurmaguncha ikkinchi qadamni takrorlanadi.
Dijkstra algoritmi:
Deykstra algoritmi bitta manbali eng qisqa yo'lni topadi.. Og'irlangan yo'naltirilgan D grafigi va v boshlang'ich nuqtasi berilgan bo'lsa, v dan D ning boshqa uchlarigacha bo'lgan eng qisqa yo'lni toping.
Maxsus usullar:
Faraz qilaylik, S to'plami birinchi toifali po'lat tomonidan hisoblangan eng qisqa yo'lning oxirgi nuqtasini saqlaydi. Boshlang'ich holatda S to'plamda v0 sifatida ko'rsatilgan faqat bitta boshlang'ich nuqta mavjud. , va keyin bitta (v0, ... .vk), S toʻplamiga barcha uchlari qoʻshilmaguncha va algoritm tugaguncha S toʻplamiga

vk qoʻshing. Boshlang'ich v0 nuqtasidan vi boshqa oxirgi nuqtalarigacha bo'lgan

eng qisqa yo'l uzunligini topish uchun dis[i] matritsasi kiritiladi va matritsaning har bir qiymati v0 boshlang'ich nuqtasidan vi oxirigacha bo'lgan eng qisqa yo'lning uzunligini ifodalaydi. . Quyida ko'rsatilganidek:

Birinchidan, birinchi qadam boshlang'ich urug' nuqtasini 1 cho'qqisiga o'rnatishdir, shuning uchun muammo shundaki, 1 cho'qqi va boshqa har bir tepalik orasidagi masofa eng qisqa. Eng qisqa cho'qqi 1 va cho'qqi 2 ni birinchi yo'naltirilgan grafikdan olish mumkin.Shuning uchun 1 va 2 cho'qqilar S to'plamga kiradi;
Ikkinchi qadam - boshlang'ich nuqtadan 1-chi nuqtagacha bo'lgan masofani topishdir 3. 1-cho'qqidan 3-cho'qqigacha bo'lgan masofa cheksizdir, lekin 2-cho'qqi 3-cho'qqiga yetsa, masofa 3 + 25 = 28, lekin cho'qqidan o'tsangiz. 4, keyin siz 3 cho'qqisiga erishasiz, masofa 3 + 8 + 4 = 15 bo'ladi, shuning uchun Deykstra birinchi navbatda 4 tepalikdan o'tadi va keyin 3 cho'qqiga etadi,

shuning uchun S to'plamiga 4 qo'ying, keyin 3 ni o'rnating, eng qisqa masofa 15 ga teng. ;

Uchinchi qadam, boshlang'ich nuqtadan 1-nuqtadan 5-chi nuqtagacha bo'lgan masofani topishdir. 1-cho'qqidan 5-cho'qqigacha bo'lgan to'g'ridan-to'g'ri masofa 30, 3-cho'qqidan 5-cho'qqigacha bo'lgan masofa 3 + 8 + 4 + 10 = 25 ga teng bo'ladi. 5– 4, masofa 3 + 8 + 12 = 23 bo'ladi, shuning uchun oxirgi marshrutni tanlang;
V dan har bir tepaga yorliq beriladi - bu cho'qqidan agacha bo'lgan minimal ma'lum masofa.
Algoritm bosqichma-bosqich ishlaydi - har bir bosqichda u bitta cho'qqiga "tashrif buyuradi" va teglarni qisqartirishga harakat qiladi.
Algoritm barcha cho'qqilarga tashrif buyurilgandan so'ng tugaydi.
Initializatsiya.
A cho'qqi yorlig'ining o'zi 0 deb qabul qilinadi, boshqa cho'qqilarning teglari cheksizlikka o'rnatiladi.
Bu a dan boshqa cho'qqilargacha bo'lgan masofalar hali ma'lum emasligini ko'rsatadi.
Grafikning barcha uchlari ko'rilmagan deb belgilangan.
Algoritm bosqichi.
Agar barcha cho'qqilarga tashrif buyurilgan bo'lsa, algoritm tugaydi.
Aks holda, hali tashrif buyurmagan cho'qqilardan minimal yorlig'i bo'lgan u tepasi tanlanadi.

Biz u oxirgi nuqta bo'lgan barcha mumkin bo'lgan marshrutlarni ko'rib chiqamiz. U dan chekkalari olib boradigan cho'qqilar bu cho'qqining qo'shnilari deyiladi. U ning har bir qo'shnisi uchun, tashrif buyurilgan deb belgilanganlardan tashqari, joriy u yorlig'i qiymatlari va u ni ushbu qo'shni bilan bog'laydigan chekka uzunligi yig'indisiga teng bo'lgan yangi yo'l uzunligini ko'rib chiqing.

Qabul qilingan uzunlik qiymati qo'shnining yorlig'i qiymatidan kam bo'lsa, yorliq qiymatini qabul qilingan uzunlik qiymati bilan almashtiring. Barcha qo'shnilarni ko'rib chiqib, biz u uchini tashrif buyurilgan deb belgilaymiz va algoritm qadamini takrorlaymiz.
Misol
Rasmda ko'rsatilgan grafik misolida algoritmning bajarilishini ko'rib chiqing.
1-cho'qqidan qolgan barcha nuqtalargacha bo'lgan eng qisqa masofalarni topish talab qilinsin.

Doiralar cho'qqilarni, chiziqlar ular orasidagi yo'llarni (grafikning qirralarini) ko'rsatadi.

Cho'qqilarning raqamlari doiralarda ko'rsatilgan, ularning og'irligi qirralarning tepasida - yo'lning uzunligida ko'rsatilgan.
Har bir cho'qqi yonida qizil yorliq belgilanadi - bu cho'qqiga 1-cho'qqigacha bo'lgan eng qisqa yo'lning uzunligi.

Birinchi qadam.
1-vertex minimal yorlig'iga ega.2, 3 va 6 cho'qqilari uning qo'shnilaridir.

1-cho'qqining birinchi qo'shnisi o'z navbatida 2-cho'qqidir, chunki unga boradigan yo'lning uzunligi minimaldir.

1-cho'qqi orqali unga boradigan yo'lning uzunligi 1-cho'qqi yorlig'i qiymati va 1-dan 2-gacha bo'lgan chekka uzunligi yig'indisiga teng, ya'ni 0 + 7 = 7.
Bu 2-cho'qqining joriy yorlig'i, cheksizlikdan kamroq, shuning uchun 2-cho'qqining yangi yorlig'i 7 ga teng.

Biz shunga o'xshash operatsiyani 1-vertexning boshqa ikkita qo'shnisi - 3 va 6-chi bilan bajaramiz.




Algoritmning bajarilishini yakunlash.
Algoritm barcha cho'qqilarga tashrif buyurilgandan so'ng tugaydi.
Algoritmning natijasi oxirgi rasmda ko'rinadi: 1 cho'qqidan 2 gacha bo'lgan eng qisqa yo'l 7, 3 gacha - 9, 4 - 20, 5 - 20, 6 - 11.
Agar biror nuqtada barcha ko'rilmagan cho'qqilar cheksizlik bilan belgilangan bo'lsa, demak, bu cho'qqilarga etib bo'lmaydi (ya'ni, grafik uzilgan). Keyin algoritm muddatidan oldin bajarilishi mumkin.