k eng qisqa yo'nalish - k shortest path routing - Wikipedia

The k eng qisqa yo'nalish muammo - bu umumlashma eng qisqa yo'lni yo'naltirish muammosi berilgan tarmoq. U nafaqat eng qisqa yo'l, balki keyingi yo'l haqida ham so'raydi k-1 eng qisqa yo'llar (bu eng qisqa yo'ldan uzunroq bo'lishi mumkin). Muammoning o'zgarishi quyidagicha halqasiz k eng qisqa yo'llar.

Topish k kengaytirish orqali eng qisqa yo'llar mumkin Dijkstra algoritmi yoki Bellman-Ford algoritmi va ularni bir nechta yo'llarni topish uchun kengaytiring.

Tarix

1957 yildan beri ko'plab maqolalar chop etildi k eng qisqa yo'lni yo'naltirish muammosi. Asosiy ishlarning aksariyati 1960 va 2001 yillar orasida amalga oshirildi. O'shandan beri tadqiqotlarning aksariyati muammoning qo'llanilishi va uning variantlari bilan bog'liq. 2010 yilda Maykl Gyunter va boshq. haqida kitob nashr ettirdi Ramziy hisoblash k-stoxastik jarayon algebra vositasi CASPA bilan eng qisqa yo'llar va tegishli choralar.^[1]

Algoritm

The Dijkstra algoritmi ni topish uchun umumlashtirilishi mumkin k eng qisqa yo'llar.

Ta'riflar: G (V, E): to'plami bilan tortilgan yo'naltirilgan grafik tepaliklar V va yo'naltirilgan to'plam qirralar E, w (u, v): tugundan yo'naltirilgan chekka narxi siz tugun v (xarajatlar salbiy emas). Eng qisqa yo'lda cheklovlarni qondirmaydigan havolalar grafikadan o'chiriladi s: manba tuguni t: manzil tuguni K: topish uchun eng qisqa yo'llar soni P_siz: dan yo'l s ga siz B yo'llarni o'z ichiga olgan yig'ma ma'lumotlar tuzilishi P: dan eng qisqa yo'llar to'plami s ga t hisoblash_siz: tugunga topilgan eng qisqa yo'llar soni siz Algoritm: P = bo'sh, hisoblash_siz = 0, Vdagi barcha u uchun yo'lni qo'shish P_s = {s} ga B narx bilan 0 esa B bo'sh emas va hisoblash_t < K: - ruxsat bering P_siz eng qisqa xarajat yo'li bo'lishi B narx bilan C – B = B − {P._siz }, hisoblash_siz = hisoblash_siz + 1 - agar siz = t keyin P = P U {P._siz} - agar hisoblash_siz ≤ K keyin har bir tepalik uchun v qo'shni siz: - ruxsat bering P_v xarajatlar bilan yangi yo'l bo'ling C + w (u, v) birlashtiruvchi qirradan hosil bo'lgan (u, v) yo'lga P_siz - kiritmoq P_v ichiga B qaytish P

O'zgarishlar

Ning ikkita asosiy o'zgarishi mavjud k eng qisqa yo'lni yo'naltirish muammosi. Bitta o'zgarishda yo'llar bitta tugunga bir necha bor tashrif buyurishi mumkin, shuning uchun ko'chadan yaratiladi. Boshqa bir o'zgarishda yo'llar talab qilinadi oddiy va halqasiz. Loop versiyasi yordamida hal qilinadi Eppshteyn algoritmi^[2] va halqasiz variatsiya bilan hal qilinadi Yen algoritmi.^[3]^[4]

Loop varianti

Ushbu variantda muammo yo'llarning halqasiz bo'lishini talab qilmasdan soddalashtiriladi.^[4] 1975 yilda B. L. Foks tomonidan echim berilgan, unda k- eng qisqa yo'llar O(m + kn jurnal n) asimptotik vaqt murakkabligi (foydalanib katta O yozuv.^[5] 1998 yilda, Devid Eppshteyn ning asimptotik murakkabligini saqlaydigan yondashuv haqida xabar berdi O(m + n jurnaln + k) har biri chiqarilishi mumkin bo'lgan yo'llarning yashirin ko'rinishini hisoblash orqali O(n) qo'shimcha vaqt.^[2]^[4] 2007 yilda, Jon Xershberger va Subhash Suri almashtirish yo'llari algoritmini taklif qildi, bu bilan Eppshteyn algoritmini yanada samarali amalga oshirish O(n) vaqtni yaxshilash.^[6] 2015 yilda Akuba va boshq. Eppshteyn algoritmi uchun indekslash usulini juda tezkor alternativa sifatida ishlab chiqdi, bunda indeks deb nomlangan ma'lumotlar strukturasi grafikadan tuzilib, keyin yuqorik tepaliklarning ixtiyoriy juftliklari orasidagi masofani tezda olish mumkin.^[7]

Loopless variant

Davrsiz variantda yo'llarga qo'shimcha murakkablik darajasini qo'shadigan ko'chadan foydalanish taqiqlanadi.^[4] Buni yordamida hal qilish mumkin Yen algoritmi^[3]^[4] sobit tugundan an-dagi boshqa tugunlarga qadar barcha eng qisqa yo'llarning uzunligini topish n-tugma manfiy bo'lmagan masofaviy tarmoq, bu usul faqat 2 ni talab qiladin² qo'shimchalar va n² taqqoslash, mavjud bo'lganlardan kamroq eng qisqa yo'l algoritmlari kerak. Ish vaqtining murakkabligi psevdo-polinom, bo'lish O(kn(m + n jurnal n)) (qayerda m va n navbati bilan qirralarning va tepalarning sonini ifodalaydi).^[3]^[4]

Ba'zi bir misollar va tavsif

Misol №1

Quyidagi misol Yenning modelini topish uchun foydalanadi k aloqa tugatish tugunlari orasidagi eng qisqa yo'llar. Ya'ni K ga qadar eng qisqa yo'lni, ikkinchi qisqa yo'lni va boshqalarni topadi^th eng qisqa yo'l. Batafsil ma'lumotni topish mumkin Bu yerga Ushbu misolda keltirilgan kod k bir yo'nalishli va ikki tomonlama yo'nalishlarning kombinatsiyasini o'z ichiga olgan 15 tugunli tarmoq uchun eng qisqa yo'lni yo'naltirish muammosi:

Ikki yo'nalishli va bitta yo'nalishli bog'lanishlarning kombinatsiyasini o'z ichiga olgan 15 tugunli tarmoq

Misol # 2

Yana bir misol - ning ishlatilishi k bir nechta ob'ektlarni kuzatib borish uchun eng qisqa yo'llar algoritmi. Texnika asosidagi bir nechta ob'ektni kuzatuvchini amalga oshiradi k eng qisqa yo'llarni yo'naltirish algoritmi. Kirish sifatida ehtimollik xaritalari to'plami ishlatiladi. Ob'ekt detektori kirishni ta'minlaydi.

To'liq tafsilotlarni "Kompyuterni ko'rish laboratoriyasi - CVLAB ".

Misol # 3

Ning yana bir ishlatilishi k eng qisqa yo'llar algoritmlari - yo'lovchilarning jamoat transporti tizimidagi tajribasini oshiradigan tranzit tarmog'ini loyihalash. Tranzit tarmog'ining bunday namunasini sayohat vaqtini hisobga olgan holda qurish mumkin. Sayohat vaqtidan tashqari, iqtisodiy va geografik cheklovlarga qarab boshqa shartlar ham olinishi mumkin. Parametrlarning o'zgarishiga qaramay, k eng qisqa yo'l algoritmlari deyarli barcha foydalanuvchilar ehtiyojlarini qondiradigan eng maqbul echimlarni topadi. Bunday dasturlar k eng qisqa yo'l algoritmlari odatiy holga aylanib bormoqda, yaqinda Xu, He, Song va Chaudry (2012) k tranzit tarmoq tizimidagi eng qisqa yo'l muammolari. ^[8]

Ilovalar

The k eng qisqa yo'l marshrutlash:

Geografik yo'llarni rejalashtirish
Tarmoqni yo'naltirish, ayniqsa optik tarmoq tarmog'i qo'shimcha cheklovlar mavjud bo'lib, ularni ishlatish bilan hal qilish mumkin emas oddiy qisqa yo'l algoritmlari.
Hisoblash lingvistikasida gipotezani yaratish
Bioinformatikada ketma-ketlikni moslashtirish va metabolik yo'lni topish
Ob'ektni bir necha marta kuzatib borish yuqorida tavsiflanganidek
Yo'l tarmoqlari: yo'l tutashuvlari - bu tugunlar (tepalar) va grafaning har bir qirrasi (zvenosi) ikkita tutashgan yo'l o'rtasidagi segment bilan bog'langan.

Bilan bog'liq muammolar

The birinchi navbatda qidirish algoritmi qidirish faqat ikkita operatsiya bilan cheklangan bo'lsa ishlatiladi.
The Floyd-Uorshall algoritmi barcha juftlarni eng qisqa yo'llarni hal qiladi.
Jonson algoritmi barcha juftlarning eng qisqa yo'llarini hal qiladi va Floyd-Uorshallga qaraganda tezroq bo'lishi mumkin siyrak grafikalar.
Perturbatsiya nazariyasi mahalliy (eng yomoni) eng qisqa yo'lni topadi.

Cherkasskiy va boshqalar.^[9] ko'proq algoritmlar va tegishli baholarni taqdim eting.

Shuningdek qarang

Cheklangan qisqa yo'l yo'nalishi

Izohlar

^ Maykl Gyunter va boshq.: "Ning ramziy hisobi k- stokastik jarayon algebra vositasi CASPA bilan eng qisqa yo'llar va tegishli choralar ". In: Xatolarga chidamli tizimlar uchun ishonchlilik modellarining dinamik jihatlari bo'yicha xalqaro seminar (DYADEM-FTS), ACM Press (2010) 13-18.
^ ^a ^b Eppshteyn, Devid (1998). " k Eng qisqa yo'llar " (PDF). SIAM J. Comput. 28 (2): 652–673. doi:10.1137 / S0097539795290477.
^ ^a ^b ^v Yen, J. Y. (1971). " k-Tarmoqdagi eng qisqa ilmoqsiz yo'llar ". Menejment fanlari. 1 7 (11): 712–716. doi:10.1287 / mnsc.17.11.712..
^ ^a ^b ^v ^d ^e ^f Boule, Erik; Ellinas, Georgios; Leyboret, Jan-Fransua; Ramamurti, Ramu (2007). "Yo'lni yo'naltirish - 2-qism: Evristika". Mesh optik tarmoqlarida yo'llarni yo'naltirish. John Wiley & Sons. 125-138 betlar. ISBN 9780470015650.
^ Fox, B. L. (1975). "Kehtimollik tarmoqlariga eng qisqa yo'llar va ilovalar ". ORSA / TIMS qo'shma milliy yig'ilishi. 23: B263. CiNii National Article ID: 10012857200.
^ Xershberger, Jon; Maksel, Metyu; Suri, Subhash (2007). " k Eng qisqa yo'llar: yangi algoritm va uni amalga oshirish " (PDF). Algoritmlar bo'yicha ACM operatsiyalari. 3 (4). 45-modda (19 bet). doi:10.1145/1290672.1290682.
^ Akuba, Takuya; Xayashi, Takanori; Nori, Nozomi; Ivata, Yoichi; Yoshida, Yuichi (2015 yil yanvar). "Samarali Top-k Yirik tarmoqlarda eng qisqa masofali so'rovlar "Belgilangan belgi yorlig'i bilan". Sun'iy intellekt bo'yicha AAAI yigirma to'qqizinchi konferentsiyasi materiallari. Ostin, TX: Sun'iy intellektni rivojlantirish assotsiatsiyasi. 2-8 betlar.
^ Xu, W., He, S., Song, R., & Chaudhry, S. (2012). Topish k jadvalga asoslangan tranzit tarmog'idagi eng qisqa yo'llar. Kompyuterlar va operatsiyalarni tadqiq qilish, 39 (8), 1812-1826. doi:10.1016 / j.cor.2010.02.005
^ Cherkasskiy, Boris V.; Goldberg, Endryu V.; Radzik, Tomasz (1996). "Eng qisqa yo'l algoritmlari: nazariya va eksperimental baholash". Matematik dasturlash. Ser. 73 (2): 129–174.

Tashqi havolalar

Yen algoritmini amalga oshirish
Yen va eng tez k eng oddiy oddiy yo'llar algoritmlarini amalga oshirish
http://www.technical-recipes.com/2012/the-k-shortest-paths-algorithm-in-c/#more-2432
K - eng qisqa yo'l algoritmidan foydalangan holda bir nechta ob'ektlarni kuzatish texnikasi: http://cvlab.epfl.ch/software/ksp/
Kompyuterni ko'rish laboratoriyasi: http://cvlab.epfl.ch/software/ksp/

[1] Maykl Gyunter va boshq.: "Ning ramziy hisobi k- stokastik jarayon algebra vositasi CASPA bilan eng qisqa yo'llar va tegishli choralar ". In: Xatolarga chidamli tizimlar uchun ishonchlilik modellarining dinamik jihatlari bo'yicha xalqaro seminar (DYADEM-FTS), ACM Press (2010) 13-18.

[Eppstein-2] Eppshteyn, Devid (1998). " k Eng qisqa yo'llar " (PDF). SIAM J. Comput. 28 (2): 652–673. doi:10.1137 / S0097539795290477.

[Yen-3] v Yen, J. Y. (1971). " k-Tarmoqdagi eng qisqa ilmoqsiz yo'llar ". Menejment fanlari. 1 7 (11): 712–716. doi:10.1287 / mnsc.17.11.712..

[Bouillet-4] v ^d ^e ^f Boule, Erik; Ellinas, Georgios; Leyboret, Jan-Fransua; Ramamurti, Ramu (2007). "Yo'lni yo'naltirish - 2-qism: Evristika". Mesh optik tarmoqlarida yo'llarni yo'naltirish. John Wiley & Sons. 125-138 betlar. ISBN 9780470015650.

[5] Fox, B. L. (1975). "Kehtimollik tarmoqlariga eng qisqa yo'llar va ilovalar ". ORSA / TIMS qo'shma milliy yig'ilishi. 23: B263. CiNii National Article ID: 10012857200.

[6] Xershberger, Jon; Maksel, Metyu; Suri, Subhash (2007). " k Eng qisqa yo'llar: yangi algoritm va uni amalga oshirish " (PDF). Algoritmlar bo'yicha ACM operatsiyalari. 3 (4). 45-modda (19 bet). doi:10.1145/1290672.1290682.

[7] Akuba, Takuya; Xayashi, Takanori; Nori, Nozomi; Ivata, Yoichi; Yoshida, Yuichi (2015 yil yanvar). "Samarali Top-k Yirik tarmoqlarda eng qisqa masofali so'rovlar "Belgilangan belgi yorlig'i bilan". Sun'iy intellekt bo'yicha AAAI yigirma to'qqizinchi konferentsiyasi materiallari. Ostin, TX: Sun'iy intellektni rivojlantirish assotsiatsiyasi. 2-8 betlar.

[8] Xu, W., He, S., Song, R., & Chaudhry, S. (2012). Topish k jadvalga asoslangan tranzit tarmog'idagi eng qisqa yo'llar. Kompyuterlar va operatsiyalarni tadqiq qilish, 39 (8), 1812-1826. doi:10.1016 / j.cor.2010.02.005

[9] Cherkasskiy, Boris V.; Goldberg, Endryu V.; Radzik, Tomasz (1996). "Eng qisqa yo'l algoritmlari: nazariya va eksperimental baholash". Matematik dasturlash. Ser. 73 (2): 129–174.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]