Tekshirdi: Begimov O’ktam Toshkent 2023 Mavzu: Prima Deykstra algoritmi. Uni vaqt bo'yicha baholasho. Reja

OʻZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI





Algoritmlarni loyihalash
1-Mustaqil ish

Bajardi:Eshonov Shohruxxon
Tekshirdi: Begimov O’ktam

Toshkent 2023


Mavzu: Prima Deykstra algoritmi. Uni vaqt bo'yicha baholasho.

Reja:

1. 
   Kirish
   
2. 
   Prim algoritmi qanday ishlaydi?
   
3. 
   Deykstriyaning eng qisqa yo’l algoritmi.
   
4. 
   Ishlash vaqti
   
5. 
   Xulosa
   
6. 
   Foydalanilgan adabiyotlar
   

Kirish.
Dijkstra algoritmi - bu vaznli grafikdagi tugunlar orasidagi eng qisqa yo'llarni topish algoritmi, masalan, yo'l tarmoqlarini ifodalashi mumkin. U 1956 yilda kompyuter olimi Edsger V. Deykstra tomonidan ishlab chiqilgan va uch yildan keyin nashr etilgan.
Algoritm ko'plab variantlarda mavjud. Dijkstraning asl algoritmi ikkita berilgan tugun oʻrtasidagi eng qisqa yoʻlni topdi, lekin keng tarqalgan variant bitta tugunni “manba” tugun sifatida oʻrnatadi va manbadan grafikdagi barcha boshqa tugunlarga eng qisqa yoʻllarni topib, eng qisqa yoʻlni ishlab chiqaradi. daraxt.
Grafikdagi ma'lum bir manba tugun uchun algoritm shu tugun va boshqa tugunlar orasidagi eng qisqa yo'lni topadi. 196–206 Bundan tashqari, to'xtash orqali bitta tugundan bitta maqsad tuguniga eng qisqa yo'llarni topish uchun ham foydalanish mumkin. maqsad tugunga eng qisqa yo'l aniqlangandan keyin algoritm. Misol uchun, agar grafikning tugunlari shaharlarni va chekka yo'llarning narxi to'g'ridan-to'g'ri yo'l bilan bog'langan shaharlar juftligi orasidagi harakat masofalarini ifodalasa (oddiylik uchun qizil chiroqlar, to'xtash belgilari, pullik yo'llar va boshqa to'siqlarga e'tibor bermang), u holda Dijkstra algoritmi mumkin. bir shahar va boshqa barcha shaharlar orasidagi eng qisqa yo'lni topish uchun ishlatiladi. Eng qisqa yo'l algoritmlarining keng qo'llaniladigan qo'llanilishi tarmoq marshrutlash protokollari, ayniqsa IS-IS (Oraliq tizimdan oraliq tizimga) va OSPF (Ochiq eng qisqa yo'l birinchi) hisoblanadi. Shuningdek, u Jonson algoritmi kabi boshqa algoritmlarda subprogramma sifatida ishlatiladi.
Dijkstra algoritmi musbat butun sonlar yoki to'liq tartiblangan haqiqiy sonlar bo'lgan teglardan foydalanadi. Qisman buyurtma qilingan har qanday yorliqlardan foydalanishni umumlashtirish mumkin, agar keyingi yorliqlar (chekkani kesib o'tishda keyingi yorliq ishlab chiqariladi) monoton ravishda kamaymaydi. Bu umumlashtirish umumiy Dijkstra eng qisqa yo'l algoritmi deb ataladi.
Dijkstra algoritmi boshidan masofa bo'yicha tartiblangan qisman echimlarni saqlash va so'rash uchun ma'lumotlar tuzilmasidan foydalanadi. Dijkstraning asl algoritmi minimal ustuvorlikdan foydalanmaydi va o'z vaqtida ishlaydi
|V| tugunlar soni). Ushbu algoritm g'oyasi Leyzorek va boshqalarda ham berilgan. 1957 yil. Fredman va Tarjan, 1984 yil ishlash vaqtining murakkabligini optimallashtirish uchun Fibonachchi to'plamidan foydalanishni taklif qiladi. . Bu asimptotik jihatdan chegaralanmagan manfiy bo'lmagan og'irliklarga ega bo'lgan ixtiyoriy yo'naltirilgan grafiklar uchun eng tez ma'lum bo'lgan yagona manbali eng qisqa yo'l algoritmidir. Biroq, ixtisoslashtirilgan holatlar (masalan, chegaralangan butun sonlar og'irliklari, yo'naltirilgan asiklik grafiklar va boshqalar) Ixtisoslashtirilgan variantlarda batafsil tavsiflanganidek, yanada yaxshilanishi mumkin. Bundan tashqari, agar oldindan ishlov berishga ruxsat berilsa, qisqarish ierarxiyasi kabi algoritmlar etti kattalikgacha tezroq bo'lishi mumkin.
Ba'zi sohalarda, xususan, sun'iy intellekt, Dijkstra algoritmi yoki uning bir varianti yagona xarajat qidiruvi sifatida tanilgan va eng yaxshi birinchi qidiruv g'oyasining namunasi sifatida shakllantirilgan.
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).
Biz boshlayotgan tugunni boshlang‘ich tugun deb ataymiz. Y tugunning masofasi boshlang'ich tugundan Y.gacha bo'lgan masofa bo'lsin. Deykstra algoritmi dastlab cheksiz masofalardan boshlanadi va ularni bosqichma-bosqich yaxshilashga harakat qiladi.