Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.


Mavzu: Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish. Reja: 1 . Kirish . 2. Asosiy qisim 1. Eng qisqa yo’llar masalalarining turlari. 2. Deykstra algoritmning so’zli tavsifi 3. Masalaning qo’yilishi. 4. Deysktra algoritmi. 3 . Xulosa. 4. Foydalanilgan adabiyotlar.
Kirish Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma- ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma-ketligi algoritm deb ataymiz. Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o‘rganadigan maxsus “Algoritmlar nazariyasi” bo‘limi xam mavjud. Algoritmlar nazariyasi – algoritmlarning umumiy xossalari , qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o‘rganish bilan shug'ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo‘llanilish sohasini aniqlash mumkin. Rotterdamdan Groningenga umuman olganda berilgan shahardan ushbu shahargacha sayohat qilishning eng qisqa yo'li nima? Bu yigirma daqiqada mo'ljallangan eng qisqa yo'l uchun algoritm. Bir kuni ertalab men yosh yigitlar bilan Amsterdamda xarid qilardim va charchagan edik, biz kofe choy ichib, kofe terastasiga o'tirdik va men buni qila olamanmi yoki yo'qmi deb o'ylagandim va keyinchalik eng qisqa yo'l uchun algoritmni yaratdim . Men aytganimdek, yigirma daqiqalik ixtiro bo'ldi. Darhaqiqat, u 59 yil ichida, uch yil o'tib nashr etildi. Bu kitob hali ham o'qilishi mumkin, aslida juda yaxshi. Bu juda yaxshi bo'lgan sabablardan biri men uni qalam va qog'ozsiz tasvirladim. Keyinchalik bilib oldimki , qalam va qog'ozsiz loyihalashtirishning afzalliklaridan biri deyarli barcha oldini olish mumkin bo'lgan murakkabliklardan qochishingiz kerak. Oxir-oqibat, bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo'lgan. - Edzger Dijkstra, ACM bilan aloqa, Philip L. Frana, 2001. Dijkstra 1956 yilda Amsterdamdagi Matematik markazda ARMAC nomli yangi kompyuterning imkoniyatlarini namoyish etish uchun dasturchi sifatida eng qisqa yo'l muammosini o'ylab topdi.Uning maqsadi ham hisoblanmaydigan odamlar tushunishi mumkin bo'lgan muammoni va echimni (kompyuter tomonidan ishlab chiqariladigan) tanlash edi. U eng qisqa yo'l algoritmini ishlab chiqdi va undan keyin uni Gollandiyada 64 ta shaharning biroz soddalashtirilgan transport xaritasi uchun ARMAC uchun amalga oshirdi (64, ya'ni 6 bit shahar raqamini kodlash uchun etarli bo'ladi).Bir yil o'tgach, u institutning navbatdagi kompyuterida ishlaydigan apparat-muhandislardan boshqa muammolarga duch keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo'lgan simni kamaytirish. Yechim sifatida u Primning eng kichik spanning daraxt algoritmi deb nomlanadigan algoritmni (avvalroq Jarnikka ma'lum va shuningdek, Primni qayta
kashf qilgan) kashf etdi. Dijkstra 1959 yilda, Primdan ikki yil keyin va Jarnikdan 29 yil o'tgach algoritmi nashr etdi. 1. Eng qisqa yo’llar masalalarining turlari. Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar. Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning modeli turlar yordamida tuziladi. Uzluksiz G turni har bir qirrasiga uning uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa irralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar orasidagi eng qisqa marshrutni topishdir. Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning fundamental muammolaridandir. Ularning bir necha turlari mavjud, masalan, ikkita berilgan uchlar orasida, berilgan va qolgan barcha uchlar orasida , turdagi har bir uchlar juftliklari orasida va boshqalar. 2. Deykstra algoritmning so’zli tavsifi Eng qisqa masofani topish masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan. Algoritm quyidagi qa damlardan iborat: 1. Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi. 2. Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi). 3. Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi. 4. Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi. 5. BVa uchi, eng qisqa masofa aniqlangan uch sifatida, ruyhatdan o’chiriladi.
Ruyhatga boshqa uch qo’yiladi, masalan, Roa. Bva o’z navbatida, boshqa, izlanayotgan ruyhatga qo’yiladi. Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi. BVa dan keyin yana bir uch ruyhatga qo’yiladi. Dastlabkisi esa ruyhatdan o’chiriladi. Sikl Bed va Lex uchlarini bog’lash uchun belgilangan qirralar aniqlanishi bilan to’xtatiladi. 3. Deyskra Algoritmi. Grafdagi eng qisqa marshrutlar uchun ko'plab qidiruv algoritmlari bo'yicha, Habreda faqatgina Floyd-Worschall algoritmining ta'rifi topildi. Ushbu algoritm grafikaning barcha vertikalari va ularning uzunligi o'rtasidagi eng qisqa yo'llarni topadi. Ushbu maqolada Dijkstra algoritmining ishlash printsipini tasvirlab beraman. Bu algoritm optimal yo'nalishlarni va ularning uzunligini ma'lum bir vertikal (manba) va grafikning boshqa vertikalari orasida topadi. Ushbu algoritmning nochorligi, agar grafika salbiy og'irliklarga ega bo'lsa, u noto'g'ri ishlaydi. Misol uchun, G quyidagi ko'rsatgichni bajaring: tasvirUshbu grafikani matritsa sifatida taqdim etamiz:tasvir Keling, vertex 1ni manba sifatida qabul qilaylik, shuning uchun vertex 1dan eng kichkina marshrutlarni 2, 3, 4 va 5-ustungacha topamiz.Ushbu algoritm grafaning barcha verticesida yineleyadi va manba verteksidan muayyan vertexga ma'lum minimal masofa bo'lgan belgilarga ularni belgilaydi. Masalan, ushbu algoritmni ko'rib chiqaylik.Keling, 1 tepalikka tegni 0 ga teng qilamiz, chunki bu vertex manba hisoblanadi. Qolgan tepaliklar abadiylikka teng teglar bilan belgilanadi. Keyinchalik, minimal yorlig'i (hozirda vertex 1) bo'lgan vertikal W ni tanlang va vertex W dan mediatorlar vertikalarini o'z ichiga olmaydi. W belgisining yig'indisiga teng bo'lgan belgini va hisobga olingan vertikalarning har biriga qarab, Vdan vertikaga yo'llarni belgilang, lekin natijada faqat oldingi qiymatdan kamroq bo'lsa. Agar bu miqdor kam bo'lmasa, oldingi belgini o'zgartirmang.Biz W dan to'g'ridan-to'g'ri yo'lni egallagan barcha vertikalarni ko'rib chiqdik, keyin V ga tashrif buyurib, tepaligini eng past qiymatga ega bo'lganlardan tanlaymiz va u keyingi V tepasida bo'ladi. Bu holda, bu birinchi 2 yoki 5. Agar bir xil teglar bilan bir necha vertikalar mavjud bo'lsa, ularning qaysi biri W ni tanlashimiz muhim emas. Biz vertex 2 ni tanlaymiz. Biroq, undan bitta chiqish yo'li yo'q, shuning uchun darhol ushbu vertexni tashrif buyurgan deb belgilab olamiz va keyingi vertikaga minimal belgisi bilan kiramiz. Bu safar faqat vertex 5da eng kam belgilar mavjud. 5-dan 5-gacha to'g'ridan-to'g'ri yo'llar mavjud bo'lgan barcha vertikalarni ko'rib