19. Прима-Дeйкстра алгoритми. Вақт бўйича самарадoрлигини баҳoлаш

Tarixiy kontekst

Qizig'i shundaki, ikkala algoritmga asoslangan texnikaning umumiy versiyasi, hatto elektron kompyuterlar bo'lmaganda ham, kontseptual jihatdan 1930 yilga teng.

Hikoya Otakar Borůvkadan boshlanadi, u Moraviya mamlakatidagi shaharlarni (hozir Chexiya respublikasi qismi) minimal xarajatli elektr tarmoqlari bilan qanday ulashni aniqlashga urinayotgan oilaviy do'st uchun algoritmga muhtoj edi. U o'z algoritmini 1926 yilda matematikaga tegishli jurnalda nashr etdi, chunki u erda Computer Science yo'q edi. Borovkaning algoritmini takomillashtirish to'g'risida o'ylab, uni 1930 yilda nashr etgan Voytchch Jarnikning e'tiboriga tushdi. U aslida biz hozir biladigan o'sha algoritmni 1957 yilda qayta kashf etgan Prim algoritmini kashf etdi.

Bularning barchasidan qat'iy nazar, 1956 yilda Dikkstra o'zining instituti yaratgan yangi kompyuterning imkoniyatlarini namoyish etish uchun dastur yozishi kerak edi. Niderlandiyaning ikki shahri o'rtasida sayohat qilish uchun kompyuter bilan aloqa o'rnatish yaxshi bo'ladi, deb o'yladi. U algoritmni 20 daqiqada yaratdi. U ba'zi soddalashtirishlar bilan 64 ta shaharlarning grafigini yaratdi (chunki uning kompyuteri 6 bitli edi) va ushbu 1956 kompyuter uchun kod yozgan. Ammo u o'z algoritmini e'lon qilmadi, chunki birinchi navbatda kompyuter fanlari bo'yicha jurnallar yo'q edi va u bu unchalik muhim bo'lmasligi mumkin deb o'yladi. Keyingi yili u yangi kompyuterlarning terminallarini ulash muammosi bilan tanishdi, shunda simlarning uzunligi minimallashtirildi. U bu muammo haqida o'yladi va Jarník / Prim 'ni qayta kashf etdi ning algoritmi, u yana bir yil oldin kashf qilgan eng qisqa yo'l algoritmi bilan bir xil texnikani qo'llaydi. Uzikr uning algoritmlarini ikkala qalam yoki qog'oz ishlatishdan mo'ljallangan edi. 1959 yilda u ikkala algoritmni atigi 2 yarim sahifadan iborat qog'ozda nashr etdi .

So'nggi paytlarda xuddi shu savol meni bezovta qilar edi va men o'z tushuncham bilan bo'lishsam kerak deb o'ylayman ...

Menimcha, ushbu ikkita algoritm (Dijkstra va Prim) ildizlari orasidagi echim, ular echish uchun mo'ljallangan muammolardir, ya'ni ikkita tugun va minimal bo'shashgan daraxt (MST) orasidagi eng qisqa yo'l. Rasmiy so'z, tugun s va t o'rtasidagi eng qisqa yo'lni topishdir va oqilona talab - bu grafikning har bir chetiga birdaniga tashrif buyurish. Biroq, u bermaydi EMAS barcha tugunni tashrif bizni talab qiladi. Ikkinchisi (MST) - bu bizlarni HAMMA tugunni ziyorat qilish (ko'pi bilan bir marta) va har bir chetga bir martadan ko'proq tashrif buyurishni bir xil oqilona talab bilan.

Bu borliq Dijkstra shunday uzoq Men olishingiz mumkin, "take yorliq" imkonini beradi, dedi s uchun t oqibatini qayg'urmasdan, - men olish bir marta t , Qildim! Ham bir yo'li bo'lsa-da s uchun t MST, balki bu s - T yo'l qolgan tugunlari hisobga bilan yaratilgan, shuning uchun, bu yo'l ko'proq vaqt bo'lishi mumkin s - T yo'l Dijstra ning algoritm tomonidan topilgan. Quyida 3 tugunli qisqa misol keltirilgan:

2 2

(s) o ----- o ----- o (t)

| |

-----------------

3

Aytaylik, har bir yuqori qirraning narxi 2, pastki chetining narxi 3 tani tashkil qiladi, keyin Dijktra bizga pastki yo'ldan borishni aytadi, chunki biz o'rta tugunga ahamiyat bermaymiz. Boshqa tomondan, Prim bizga pastki chetini tashlab, yuqori 2 qirrali MSTni qaytaradi.

Bunday farq, shuningdek, amalga oshirilishdagi nozik farqdan ham ko'rinib turibdi: Dijkstraning algoritmida yangi tugunni o'zlashtirgandan so'ng , s- dan eng qisqa yo'lni yangilash uchun kitobni yuritish bosqichi (har bir tugun uchun) bo'lishi kerak , ammo Prim algoritmida u erda. kerak emas.

1^ https://youtu.be/PzznKcMyu0Y

2^ https://youtu.be/ba4YGd7S-TY