Mustaqil ish Mavzu

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARNIN RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Algoritmlarni loyihalash fani bo’yicha

Mustaqil ish

Mavzu: Deykstra algoritmi.

Bajardi: Rasulov Izzatbek

TOSHKENT 2020

Reja:

1. 
   Deykstra algoritmi deb nimaga aytiladi?
   
2. 
   Deykstra algoritmini dasturiy ta'minotini amalga oshirish.
   
3. 
   Deykstra algoritmining tadbiqi
   

Deykstra algoritmi

Deykstra algoritmi - bu Gollandiyalik olim Edsger Diykstra 1959 yilda ixtiro qilgan grafik algoritm. Grafikning uchidan boshqalarigacha bo'lgan eng qisqa yo'llarni topadi. Algoritm faqat salbiy og'irliksiz chizmalar uchun ishlaydi. Algoritm dasturlash va texnologiyalarda keng qo'llaniladi, masalan, uning yordamida, marshrutlash protokollari undan foydalanadi, agar barcha zarur ma'lumotlar berilgan bo'lsa, masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta shahardan boshqa shaharlarning har biriga borish uchun qaysi yo'llar ketma-ketligini tanlash afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy tomoni shundaki, manfiy vaznga ega bo’lgan qirralari mavjud bo'lgan graflarni qayta ishlash imkonining mavjud emasligi, ya'ni, masalan, ba'zi tizim birorta kompaniya uchun foydasiz bo'lgan marshrutlarni taqdim qilsa, u holda u bilan ishlash uchun Deykstraning algoritmidan foydalanib bo’lmaydi.

Dunyo shaharlari orasida ma'lum miqdordagi reyslar mavjud, ularning har biri uchun narx ma'lum. A dan Bgacha bo'lgan parvozning narxi B dan A gacha bo'lgan parvozning narxiga teng bo'lmasligi mumkin

Algoritm qadam-baqadam ishlaydi - har bir qadamda bitta cho'qqiga "tashrif buyuradi" va teglarni kamaytirishga harakat qilinadi. Algoritmning ishi barcha cho’qqilarni ziyorat qilish bilan tugaydi. O'zining uchi ostidagi yorliq 0 ga teng, qolgan uchlarining yorlig'i cheksizdir. Bu boshqa cho'qqilargacha bo'lgan masofalar hali ma'lum emasligini aks ettiradi. Grafikning barcha uchlari ko'rinmas deb belgilangan. Doiralar shaklida uchlar, chiziqlar shaklida ular orasidagi yo’l (grafning qovurg’alari) tasvirlangan. Doiralar ichida uchlarning nomerlari, qovurg’alar ostida ularning og’irligi – yo’l uzunligi berilgan. Har bir uchning yonida qizil belgi bilan shu uchga birinchi uchdan eng qisqa masofa uzunligi belgilangan.

1–uchning belgisi 0 ga teng deb hisoblanadi, qolgan uchlarning belgilari yetib bo’lmas darajada juda katta sonlardan iborat. Bu 1–uchdan boshqalarigacha bo’lgan masofa hali noma’lumligiki ko’rsatadi. Grafning barcha uchlari ko’rilmagan deb belgilanadi.

Birinchi qadam

Minimal belgiga 1–uch ega. Uning qo’shnilari 2, 3 va 6 uchlar. Uchning qo’shnilarini navbat bilan ko’rib chiqamiz. 1–uchning birinchi qo’shnisi 2–uch, chunki ungacha bo’lgan masofa minimal. 1–uch orqali ungacha bo’lgan masofa 1–uchgacha bo’lgan qisqa masofaning summasiga teng, 1–dan 2–ga boruvchi uning belgisi va qovurg’asi uzunligiga, ya’ni 0+7=7. Bu 2–uchning joriy belgisidan (10000) kichik, shu sababdan ham 2–uchning yangi belgisi 7 ga teng.

Shunga mos ravishda qolgan qo’shnilar (3 va 6 uchlar) uchun ham yo’l uzunligini aniqlaymiz. 1-uchning barcha qo’shnilari ko’rib chiqildi. 1-uchgacha joriy minimal masofa yakuniy hisoblanadi va qayta ko’rib chiqilmaydi. 1-uch ko’rib chiqildi deb belgilanadi.

Ikkinchi qadam

Birinchi qadam takrorlanadi. Ko’rib chiqilmagan uchlardan “yaqini”ni topamiz. Bu 2-uch belgisi 7 ga teng. Yana tanlangan uchning qo’shnilari belgilarini kamaytirishga harakat qilamiz, bunda ularga 2-uch orqali o’tamiz. 2- uchning qo’shnilari 1, 3 va 4 uchlar.

1-uch ko’rib chiqilgan, shu sababdan 3-uch ko’rib chiqilmagan va uchlar ichida minimal belgiga ega. Agar unga 2 orqali borilsa, u holda bu yo’lning uzunligi 17 (7+10=17)ga teng bo’ladi. Ammo 3-uchning joriy belgisi 9 ga teng, ya’ni 9<17, shu sababdan belgi o’zgarishsiz qoladi.

2-ucning yana bir qo’shnisi 4-uch. Agar unga 2-uch orqali borsak, u holda bunday yo’lning uzunligi 22 (7+15=22) ga teng. 22<10000 dan bo’lganligi sabab, 4-uchning belgisini 22 ga tenglaymiz.

2-uchning barcha qo’shnilari ko’rib chiqildi, endi uni ko’rib chiqilgan sifatida belgilaymiz.



Uchinchi qadam

3-uchni tanlab algoritmning qadamini takrorlaymiz. Uni “qayta ishlab chiqish”dan so’ng quyidagi natijaga ega bo’lamiz.

To’rtinchi qadam. Beshinchi qadam.





Oltinchi qadam

Shu tarzda 1-uchdan 5-uchga eng qisqa masofa 1 – 3 – 6 – 5 uchlari orqali bo’ladi. Shu yo’l orqali biz 20 ga teng minimal og’irlik yig’amiz.

Minimal masofa haqida xulosaga keladigan bo’lsak. Har bir uch uchun yo’l uzunligini bilamiz va endi uchlarni oxirdan ko’rib chiqamiz. Yakuniy uchni ko’rib chiqamiz (bu holatda 5-uch). U bilan bog’langan barcha uchlarni ham ko’rib chiqamiz, yakuniy uch yo’li uzunligidan mos qovurg’aning og’irligini ayirgan holda yo’l uzunligini topamiz. Bizda 5-uch yo’l uzunligi 20. U 6 va 4 uchlar bilan bog’langan. 6- uch uchun 20-9=11 og’irlikka ega bo’lamiz (mos tushdi). 4-uch uchun 20-6=14 og’irlikka ega bo’lamiz (mos tushmadi). Agar natijada biz ko’rilayotgan uchning (joriy holda 6-uch) yo’l uzunligiga mos qiymatga ega bo’lsak, u holda yakuniy uchga o’tish aynan o’sha uchdan amalga oshirilgan bo’ladi. Bu uchni qidirilayotgan yo’lda belgilan qo’yamiz.

6-uchga qaysi qovurg’a orqali kelganimizni aniqlaymiz. Va shu holda toki boshiga chiqmagunimizcha davom qildiramiz.

Agar bunday kuzatish natijasida bizda qaysidir qadamda bir nechta uchlar uchun bu qiymat mos tushsa, u holda ulardan ixtiyoriy birini olish mumkin – bir necha yo’llar bir xil uzunlikka ega bo’ladi.