Dijkstraning eng qisqa yo'l algoritmi batafsil va vizual kirish
Download 107.44 Kb.
|
Dijkstraning eng qisqa yo
|
Dijkstraning eng qisqa yo'l algoritmi - batafsil va vizual kirish Asosiy grafik tushunchalar (tezkor ko'rib chiqish). Dijkstra algoritmi nima uchun ishlatiladi. Bosqichma-bosqich misol bilan sahna ortida qanday ishlaydi. Asosiy tushunchalar Grafiklar - elementlar juftlari orasidagi "bog'lanishlarni" ifodalash uchun ishlatiladigan ma'lumotlar tuzilmalari. Ushbu elementlar tugunlar deb ataladi . Ular real hayotdagi ob'ektlar, shaxslar yoki shaxslarni ifodalaydi. Tugunlar orasidagi ulanishlar deyiladi qirralar . Bu grafikning grafik tasviri: Tugunlar rangli doiralar bilan, qirralar esa bu doiralarni bog'laydigan chiziqlar bilan ifodalanadi. Maslahat: Ikki tugun oʻrtasida chekka boʻlsa, ulanadi. Ilovalar Grafiklar to'g'ridan-to'g'ri real stsenariylarga qo'llaniladi. Misol uchun, biz transport tarmog'ini modellash uchun grafiklardan foydalanishimiz mumkin, bu erda tugunlar mahsulotlarni jo'natish yoki qabul qilish ob'ektlarini va qirralarni ularni bog'laydigan yo'llarni yoki yo'llarni ifodalaydi (pastga qarang). Grafik bilan ifodalangan tarmoq Grafik turlari Grafiklar quyidagicha bo'lishi mumkin: Yo'naltirilmagan: agar ulangan tugunlarning har bir jufti uchun siz ikkala yo'nalishda ham bir tugundan ikkinchisiga o'tishingiz mumkin. Yo'naltirilgan: agar har bir bog'langan tugun juftligi uchun siz faqat bitta tugundan boshqasiga ma'lum bir yo'nalishda o'tishingiz mumkin. Yo'naltirilgan qirralarni ko'rsatish uchun oddiy chiziqlar o'rniga o'qlardan foydalanamiz. Biz yo'naltirilmagan grafiklar bilan ishlaymiz . Og'irlangan grafiklar Og'irlik grafigi - chekkalarida " og'irlik" yoki "narx" bo'lgan grafik. Kenarning og'irligi masofani, vaqtni yoki u bog'laydigan tugunlar juftligi orasidagi "bog'lanish" ni modellashtiradigan har qanday narsani ifodalashi mumkin. Misol uchun, quyida keltirilgan vaznli grafikda siz har bir chekkaning yonida ko'k raqamni ko'rishingiz mumkin. Bu raqam mos keladigan qirraning og'irligini ifodalash uchun ishlatiladi. Bu vaznlar Dijkstra algoritmi uchun zarur. 🔸 Dijkstra algoritmiga kirish Endi siz grafiklarning asosiy tushunchalarini bilganingizdan so'ng, keling, ushbu ajoyib algoritmga sho'ng'ishni boshlaylik. Maqsad va foydalanish holatlari Tarix Algoritm asoslari Talablar Maqsad va foydalanish holatlari Dijkstra algoritmi yordamida siz grafikdagi tugunlar orasidagi eng qisqa yo'lni topishingiz mumkin. Xususan, siz tugundan ("manba tugun" deb ataladi) grafikdagi barcha boshqa tugunlarga eng qisqa yo'lni topishingiz mumkin, bu esa eng qisqa yo'l daraxtini hosil qiladi. Ushbu algoritm joriy joylashuv va maqsad o'rtasidagi eng qisqa yo'lni topish uchun GPS qurilmalarida qo'llaniladi. U sanoatda, xususan, modellashtirish tarmoqlarini talab qiladigan domenlarda keng qo'llanilishiga ega. Tarix Ushbu algoritm ajoyib gollandiyalik kompyuter olimi va dastur muhandisi doktor Edsger V. Dijkstra tomonidan yaratilgan va nashr etilgan . 1959 yilda u o'zining yangi algoritmini tushuntirib bergan "Grafiklar bilan bog'liq ikkita muammo haqida eslatma" nomli 3 betlik maqolani nashr etdi. 1994 yilda ETH Zurichda doktor Edsger Dijkstra (Andreas F. Borchert tomonidan surat) 2001 yilda suhbat chog'ida doktor Dijkstra algoritmni qanday va nima uchun ishlab chiqqanini aytdi: Rotterdamdan Groningenga borishning eng qisqa yo'li qanday? Bu men 20 daqiqada ishlab chiqqan eng qisqa yo'lning algoritmidir. Bir kuni ertalab men yosh kelinim bilan Amsterdamda xarid qildim va charchab, bir piyola qahva ichish uchun kafe terasida o'tirdik va men buni qila olamanmi, deb o'yladim va keyin eng qisqa yo'l algoritmini ishlab chiqdim. . Aytganimdek, bu 20 daqiqalik ixtiro edi. Darhaqiqat, u 1959 yilda, uch yildan keyin nashr etilgan. Nashr hali ham juda yaxshi. Bu juda chiroyli bo'lishining sabablaridan biri men uni qalam va qog'ozsiz ishlab chiqqanim edi. Qalam va qog'ozsiz deyarli barcha oldini olish mumkin bo'lgan murakkabliklardan qochishga majbur bo'lasiz. Oxir-oqibat, bu algoritm mening shon-shuhratimning asoslaridan biriga aylandi. - Edsger W. Dijkstra maqolasida keltirilganEdsger V. Dijkstra bilan suhbatdan . ⭐ Ajablanarlisi, shunday emasmi? Doktor Deykstra atigi 20 daqiqada kompyuter fanlari tarixidagi eng mashhur algoritmlardan birini yaratdi. Deykstra algoritmining asoslari Dijkstra algoritmi asosan siz tanlagan tugundan (manba tugun) boshlanadi va u ushbu tugun va grafikdagi barcha boshqa tugunlar orasidagi eng qisqa yo'lni topish uchun grafikni tahlil qiladi. Algoritm har bir tugundan manba tuguniga maʼlum boʻlgan eng qisqa masofani kuzatib boradi va agar u qisqaroq yoʻl topsa, bu qiymatlarni yangilaydi. Algoritm manba tugun va boshqa tugun o'rtasidagi eng qisqa yo'lni topgandan so'ng, bu tugun "tashrif buyurilgan" deb belgilanadi va yo'lga qo'shiladi. Jarayon grafikdagi barcha tugunlar yo'lga qo'shilmaguncha davom etadi. Shunday qilib, biz har bir tugunga erishish uchun mumkin bo'lgan eng qisqa yo'l bo'ylab manba tugunini boshqa barcha tugunlarga bog'laydigan yo'lga egamiz. Talablar Dijkstra algoritmi faqat ijobiy og'irliklarga ega bo'lgan grafiklar bilan ishlashi mumkin. Buning sababi shundaki, jarayon davomida eng qisqa yo'lni topish uchun qirralarning og'irliklari qo'shilishi kerak. Agar grafikda salbiy og'irlik bo'lsa, u holda algoritm to'g'ri ishlamaydi. Tugun "tashrif buyurilgan" deb belgilanganidan so'ng, ushbu tugunga boradigan joriy yo'l ushbu tugunga erishish uchun eng qisqa yo'l sifatida belgilanadi. Va agar bu bosqich sodir bo'lgandan keyin umumiy og'irlik kamayishi mumkin bo'lsa, salbiy og'irliklar buni o'zgartirishi mumkin. 🔹 Dijkstra algoritmiga misol Endi siz ushbu algoritm haqida ko'proq ma'lumotga ega bo'lganingizdan so'ng, keling, uning sahna ortida qanday ishlashini bosqichma-bosqich misol bilan ko'rib chiqamiz. Bizda bu grafik bor: 0Algoritm tugundan grafikdagi barcha boshqa tugunlarga eng qisqa yo'lni yaratadi . Maslahat: Ushbu grafik uchun biz qirralarning og'irligi ikki tugun orasidagi masofani ifodalaydi deb faraz qilamiz. Grafikdagi har bir tugun uchun biz tugundan tugunga, tugundan tugunga, tugundan tugunga va hokazo 0eng 1qisqa 0yo'lga 2ega 0bo'lamiz .3 Dastlab, bizda ushbu masofalar ro'yxati mavjud (quyidagi ro'yxatga qarang): Manba tugunidan o'ziga bo'lgan masofa 0. Ushbu misol uchun manba tugun tugun bo'ladi, 0lekin u siz tanlagan har qanday tugun bo'lishi mumkin. Manba tugunidan boshqa barcha tugunlargacha bo'lgan masofa hali aniqlanmagan, shuning uchun biz buni dastlab ifodalash uchun cheksizlik belgisidan foydalanamiz. Hali tashrif buyurmagan tugunlarni (yo'lga kiritilmagan tugunlarni) kuzatib borish uchun bizda ushbu ro'yxat mavjud (pastga qarang): Maslahat: Yodda tutingki, algoritm barcha tugunlar yoʻlga qoʻshilgandan soʻng yakunlanadi.Biz tugundan boshlashni tanlaganimiz sababli 0, biz ushbu tugunni tashrif buyurilgan deb belgilashimiz mumkin. Xuddi shunday, biz uni ko'rilmagan tugunlar ro'yxatidan kesib tashlaymiz va diagrammadagi tegishli tugunga qizil chegara qo'shamiz: 0Endi biz tugundan uning qo'shni tugunlarigacha bo'lgan masofani tekshirishni boshlashimiz kerak . Ko'rib turganingizdek, bu tugunlar 1va 2(qizil qirralarga qarang): 💡 Maslahat: Bu biz darhol ikkita qo‘shni tugunni eng qisqa yo‘lga qo‘shamiz degani emas. Ushbu yo'lga tugun qo'shishdan oldin, biz unga erishish uchun eng qisqa yo'lni topganimizni tekshirishimiz kerak. Mavjud variantlarni ko'rish uchun biz shunchaki dastlabki imtihon jarayonini o'tkazmoqdamiz. 0Tugundan tugungacha 1va tugungacha bo'lgan masofalarni ularni tugunga (manba tuguniga) 2bog'laydigan qirralarning og'irliklari bilan yangilashimiz kerak. 0Bu og'irliklar mos ravishda 2 va 6 ga teng: Qo'shni tugunlarning masofalarini yangilagandan so'ng, biz quyidagilarni bajarishimiz kerak: Joriy ma'lum masofalar asosida manba tuguniga eng yaqin bo'lgan tugunni tanlang. Uni tashrif buyurilgan deb belgilang. Uni yo'lga qo'shing. Agar biz masofalar ro'yxatini tekshirsak, biz tugunning 1manba tuguniga eng qisqa masofaga ega ekanligini ko'rishimiz mumkin (masofa 2), shuning uchun biz uni yo'lga qo'shamiz. Diagrammada biz buni qizil qirra bilan ifodalashimiz mumkin: Biz uni "tashrif buyurilgan" va biz ushbu tugunga eng qisqa yo'lni topganimizni ko'rsatish uchun ro'yxatda qizil kvadrat bilan belgilaymiz: Biz uni ko'rilmagan tugunlar ro'yxatidan kesib tashlaymiz: Endi biz ularga erishish uchun eng qisqa yo'lni topish uchun yangi qo'shni tugunlarni tahlil qilishimiz kerak. Biz faqat eng qisqa yo'lning bir qismi bo'lgan tugunlarga qo'shni bo'lgan tugunlarni tahlil qilamiz (qizil qirralar bilan belgilangan yo'l). Tugun 3va tugun 2ikkalasi ham allaqachon yo'lda bo'lgan tugunlarga ulashgan, chunki ular to'g'ridan-to'g'ri tugun 1va tugunga ulangan 0, quyida ko'rib turganingizdek. Bu biz keyingi bosqichda tahlil qiladigan tugunlar. Bizning ro'yxatimizda manba tugunidan tugungacha bo'lgan masofa allaqachon 2yozilganligi sababli, bu safar masofani yangilashimiz shart emas. Biz faqat manba tugunidan yangi qo'shni tugun (tugun)gacha bo'lgan masofani yangilashimiz kerak 3: Bu masofa 7 ga teng . Keling, nima uchun ekanligini bilib olaylik. Manba tugunidan boshqa tugungacha bo'lgan masofani topish uchun (bu holda, tugun 3), biz ushbu tugunga erishish uchun eng qisqa yo'lni tashkil etuvchi barcha qirralarning og'irliklarini qo'shamiz: Tugun uchun 3: umumiy masofa 7 ga teng, chunki biz yo'lni tashkil etuvchi qirralarning og'irliklarini qo'shamiz 0 -> 1 -> 3(qirra uchun 2 va chekka 0 -> 1uchun 5 1 -> 3). Endi biz qo'shni tugunlargacha bo'lgan masofaga egamiz, biz yo'lga qaysi tugun qo'shilishini tanlashimiz kerak. Biz manba tuguniga eng qisqa (hozirda ma'lum) masofaga kirmagan tugunni tanlashimiz kerak. Masofalar ro'yxatidan biz bu 2masofa 6 bo'lgan tugun ekanligini darhol aniqlashimiz mumkin : Biz uni tugun atrofida qizil chegara va qizil qirra bilan grafik tarzda yo'lga qo'shamiz: Shuningdek, masofalar ro'yxatiga kichik qizil kvadrat qo'shish va uni ko'rilmagan tugunlar ro'yxatidan kesib o'tish orqali uni tashrif buyurilgan deb belgilaymiz: Endi manba tugunidan yangi qo'shni tugungacha bo'lgan eng qisqa yo'lni topish uchun jarayonni takrorlashimiz kerak, bu tugun 3. Bizda ikkita mumkin bo'lgan yo'l borligini ko'rishingiz mumkin 0 -> 1 -> 3yoki 0 -> 2 -> 3. Keling, qaysi biri eng qisqa yo'l ekanligini qanday aniqlashimiz mumkinligini ko'rib chiqaylik. Tugun 3allaqachon ro'yxatda oldindan yozib olingan masofaga ega ( 7, quyidagi ro'yxatga qarang). Bu masofa oldingi qadamning natijasi bo'lib, biz yo'lni bosib o'tishimiz kerak bo'lgan ikkita chetning 5 va 2 og'irliklarini qo'shdik 0 -> 1 -> 3. Ammo endi bizda boshqa muqobil bor. Agar biz yo'ldan borishni tanlasak 0 -> 2 -> 3, biz ikkita qirraga 0 -> 2va mos ravishda 6 va 82 -> 3 og'irliklarga ega bo'lishimiz kerak , bu umumiy masofa 14 ni tashkil qiladi . Shubhasiz, birinchi (mavjud) masofa qisqaroq (7 va 14), shuning uchun biz asl yo'lni saqlashni tanlaymiz 0 -> 1 -> 3. Biz faqat yangi yo'l qisqaroq bo'lsa, masofani yangilaymiz. Shuning uchun biz ushbu tugunni birinchi muqobil yordamida yo'lga qo'shamiz: 0 -> 1 -> 3. Biz ushbu tugunni tashrif buyurilgan deb belgilaymiz va uni ko'rilmagan tugunlar ro'yxatidan kesib tashlaymiz: Endi biz jarayonni yana takrorlaymiz. Biz hozirgacha tashrif buyurmagan yangi qo'shni tugunlarni tekshirishimiz kerak. Bu safar, bu tugunlar tugun 4va tugundir 5, chunki ular tugunga ulashgan 3. Biz ushbu tugunlarning manba tuguniga masofalarini yangilaymiz, iloji bo'lsa, har doim qisqaroq yo'lni topishga harakat qilamiz: Tugun uchun 4: masofa yo'ldan 170 -> 1 -> 3 -> 4 . Tugun uchun 5: masofa yo'ldan 220 -> 1 -> 3 -> 5 . 💡 Maslahat: E'tibor bering, biz faqat eng qisqa yo'lni (qizil bilan belgilangan) kengaytirishni ko'rib chiqishimiz mumkin. Bizni eng qisqa yo'lga qo'shilmagan qirralardan o'tadigan yo'llarni ko'rib chiqa olmaymiz (masalan, biz chetidan o'tadigan yo'lni hosil qila olmaymiz 2 -> 3). Qaysi tashrif buyurilmagan tugun hozir tashrif buyurilgan deb belgilanishini tanlashimiz kerak. Bu holda, bu tugun 4, chunki u masofalar ro'yxatida eng qisqa masofaga ega. Biz uni diagrammaga grafik tarzda qo'shamiz: Shuningdek, biz ro'yxatga kichik qizil kvadrat qo'shish orqali uni "tashrif buyurilgan" deb belgilaymiz: Va biz uni ko'rilmagan tugunlar ro'yxatidan kesib tashlaymiz: Va biz jarayonni yana takrorlaymiz. Biz qo'shni tugunlarni tekshiramiz: tugun 5va tugun 6. Biz allaqachon tashrif buyurilgan deb belgilangan va yo'lga qo'shilgan tugunlardan ularga erishish uchun borishimiz mumkin bo'lgan har bir yo'lni tahlil qilishimiz kerak. Tugun uchun 5: Birinchi variant - yo'lni kuzatib borish , manba tugunidan 220 -> 1 -> 3 -> 5 masofaga ega (2 + 5 + 15). Bu masofa oldingi bosqichda masofalar ro'yxatida allaqachon qayd etilgan. Ikkinchi variant esa manba tugunidan (2 + 5 + 10 + 6) 230 -> 1 -> 3 -> 4 -> 5 masofaga ega bo'lgan yo'lni kuzatish bo'ladi. Shubhasiz, birinchi yo'l qisqaroq, shuning uchun biz uni tugun uchun tanlaymiz 5. Tugun uchun 6: Mavjud yo'l , manba tugunidan 190 -> 1 -> 3 -> 4 -> 6 masofaga ega (2 + 5 + 10 + 2). Biz tashrif buyurilgan eng qisqa (hozirda ma'lum) masofa bilan tugunni belgilaymiz. Bunday holda, tugun 6. Va biz uni ko'rilmagan tugunlar ro'yxatidan kesib tashlaymiz: Endi bizda bu yo'l bor (qizil bilan belgilangan): Faqat bitta tugunga hali tashrif buyurilmagan, tugun 5. Keling, uni qanday qilib yo'lga kiritishimiz mumkinligini ko'rib chiqaylik. 5Yo'lga qo'shilgan tugunlardan tugunga erishish uchun uchta turli yo'l bor : Variant 1: 22 (2 + 5 + 15) 0 -> 1 -> 3 -> 5masofa bilan . Variant 2: 23 (2 + 5 + 10 + 6) 0 -> 1 -> 3 -> 4 -> 5masofa bilan . Variant 3: 25 (2 + 5 + 10 + 2 + 6) 0 -> 1 -> 3 -> 4 -> 6 -> 5masofa bilan . Biz eng qisqa yo'lni tanlaymiz: 220 -> 1 -> 3 -> 5 masofa bilan . Biz tugunni tashrif buyurilgan deb belgilaymiz va uni ko'rilmagan tugunlar ro'yxatidan kesib tashlaymiz: Va voila! 0Grafikdagi tugundan har bir tugungacha bo'lgan eng qisqa yo'l bilan yakuniy natijaga egamiz . Diagrammada qizil chiziqlar eng qisqa yo'lga tegishli bo'lgan qirralarni belgilaydi. Tugundan boshlab grafikdagi berilgan tugunga erishish uchun eng qisqa yo'lni bosib o'tish uchun ushbu qirralarga amal qilishingiz kerak 0. Misol uchun, agar siz tugundan 6boshlab tugunga erishmoqchi 0bo'lsangiz, faqat qizil qirralarga amal qilishingiz kerak va siz avtomatik ravishda eng qisqa yo'lni kuzatib borasiz 0 -> 1 -> 3 -> 4 - > 6. Xulosa Grafiklar ob'ektlar, odamlar yoki ob'ektlar o'rtasidagi aloqalarni modellashtirish uchun ishlatiladi. Ular ikkita asosiy elementga ega: tugunlar va qirralar. Tugunlar ob'ektlarni, qirralar esa bu ob'ektlar orasidagi bog'lanishlarni ifodalaydi. Dijkstra algoritmi berilgan tugun (u "manba tugun" deb ataladi) va grafikdagi barcha boshqa tugunlar orasidagi eng qisqa yo'lni topadi. Ushbu algoritm manba tugun va boshqa barcha tugunlar orasidagi umumiy masofani (og'irlik) minimallashtiradigan yo'lni topish uchun qirralarning og'irliklaridan foydalanadi. Download 107.44 Kb. Do'stlaringiz bilan baham: 
|