к ең қысқа маршруттау - k shortest path routing - Wikipedia

The к ең қысқа маршруттау проблема - жалпылау ең қысқа жолды бағыттау проблемасы берілген желі. Ол қысқа жол туралы ғана емес, келесі жол туралы да сұрайды k − 1 ең қысқа жолдар (олар қысқа жолдан ұзын болуы мүмкін). Мәселенің вариациясы - бұл ілмексіз к ең қысқа жолдар.

Іздеу к ең қысқа жолдар кеңейту арқылы мүмкін болады Dijkstra алгоритмі немесе Bellman-Ford алгоритмі және оларды бірнеше жолды табу үшін кеңейтіңіз.

Тарих

1957 жылдан бастап көптеген мақалалар жарық көрді к ең қысқа жолды бағыттау проблемасы. Іргелі жұмыстардың көпшілігі 1960 жылдар мен 2001 жылдар аралығында жасалды. Содан бері зерттеулердің көп бөлігі проблеманы қолдану және оның нұсқалары бойынша жүргізілді. 2010 жылы Майкл Гюнтер және басқалар. туралы кітап шығарды Символдық есептеу к- CASPA стохастикалық алгебра құралының ең қысқа жолдары және онымен байланысты шаралар.^[1]

Алгоритм

The Dijkstra алгоритмі табу үшін жалпылауға болады к ең қысқа жолдар.

Анықтамалар: G (V, E): жиынтығымен өлшенген бағытталған график төбелер V және бағытталған шеттері E, w (u, v): түйіннен бағытталған жиектің құны сен түйінге v (шығындар теріс емес). Ең қысқа жолдағы шектеулерді қанағаттандырмайтын сілтемелер графиктен алынып тасталады с: бастапқы түйін т: тағайындалған түйін Қ: табуға болатын ең қысқа жолдар саны P_сен: бастап жол с дейін сен B жолдарды қамтитын үйінді деректер құрылымы P: бастап ең қысқа жолдар жиынтығы с дейін т санау_сен: түйінге табылған ең қысқа жолдар саны сен Алгоритм: P = бос, санау_сен = 0, V ішіндегі барлық үшін кірістіру жолы P_с = {с} B құны бойынша 0 уақыт B бос емес және санау_т < Қ: - рұқсат етіңіз P_сен ең қысқа шығындар жолы B құны бойынша C – B = B − {P_сен }, санау_сен = санау_сен + 1 - егер сен = т содан кейін P = P U {P_сен} - егер санау_сен ≤ Қ содан кейін әр төбе үшін v іргелес сен: - рұқсат етіңіз P_v өзіндік құны бар жаңа жол болыңыз C + w (u, v) жалғау шетінен түзілген (u, v) жолға P_сен - кірістіру P_v ішіне B қайту P

Вариациялар

Екі негізгі вариация бар к ең қысқа жолды бағыттау проблемасы. Бір вариацияда жолдарға бір түйінге бірнеше рет кіруге рұқсат етіледі, осылайша циклдар жасалады. Басқа вариацияда жолдар болуы керек қарапайым және циклсыз. Дөңгелек нұсқаны қолдануға болады Эппштейннің алгоритмі^[2] және циклсіз вариация арқылы шешіледі Йен алгоритмі.^[3]^[4]

Loop нұсқасы

Бұл нұсқада мәселе жолдардың циклсіз болуын талап етпеу арқылы жеңілдетіледі.^[4] Шешімді 1975 жылы Б.Л.Фокс берді, онда к-қысқа жолдар анықталады O(м + кн журнал n) уақыттың асимптотикалық күрделілігі (қолдану үлкен O белгілеу.^[5] 1998 жылы, Дэвид Эппштейн асимптоталық күрделілігін сақтайтын тәсіл туралы хабарлады O(м + n журналn + к) әрқайсысы шығарылатын жолдардың жасырын көрінісін есептеу арқылы O(n) қосымша уақыт.^[2]^[4] 2007 жылы, Джон Хершбергер және Субхаш Сури ауыстыру жолдарының алгоритмін ұсынды, бұл Эппштейн алгоритмін неғұрлым тиімді жүзеге асырады O(n) уақытты жақсарту.^[6] 2015 жылы, Акуба т.б. Эппштейн алгоритмі үшін индекстеу әдісін ойлап тапты, онда индекс деп аталатын мәліметтер құрылымы графиктен құрастырылады, содан кейін жоғарыданк төбелердің ерлі-зайыптылары арасындағы қашықтықты тез алуға болады.^[7]

Ілмексіз нұсқа

Ілмексіз нұсқада жолдарға қосымша күрделілік деңгейін қосатын ілмектер кіруге тыйым салынады.^[4] Оны пайдаланып шешуге болады Йен алгоритмі^[3]^[4] барлық түйіндерден бастап барлық түйіндерге дейінгі барлық қысқа жолдардың ұзындықтарын табу n- теріс қашықтықты емес торап, тек 2 қажет ететін әдісn² толықтырулар және n² салыстыру, қол жетімдіге қарағанда азырақ ең қысқа алгоритмдер қажеттілік. Жұмыс уақытының күрделілігі жалған полином, болу O(кн(м + n журнал n)) (қайда м және n тиісінше жиектер мен төбелердің санын білдіреді).^[3]^[4]

Кейбір мысалдар мен сипаттама

№1 мысал

Келесі мысалда Yen моделін табу үшін қолданылады к соңғы түйіндерді байланыстыратын ең қысқа жолдар. Яғни, ол К-ге дейін ең қысқа жолды, екінші қысқа жолды және т.б.^мың ең қысқа жол. Толығырақ ақпаратты табуға болады Мұнда.Мысалда келтірілген код. Шешуге тырысады к бір түйінді және екі бағытты сілтемелердің тіркесімін қамтитын 15 түйінді желі үшін ең қысқа жолды бағыттау проблемасы:

Екі бағытты және бір бағытты байланыстардың тіркесімін қамтитын 15 түйінді желі

Мысал №2

Келесі мысал - пайдалану к бірнеше объектілерді бақылауға арналған қысқа жолдар алгоритмі. Техника негізделген бірнеше объектілік трекер к маршруттаудың ең қысқа жолдары. Кіріс ретінде ықтималдықты орналастыру карталарының жиынтығы қолданылады. Нысан детекторы кірісті қамтамасыз етеді.

Толық ақпаратты мына жерден таба аласыз «Компьютерлік көру зертханасы - CVLAB ».

Мысал №3

Тағы бір пайдалану к алгоритмдердің қысқа жолдары - бұл жолаушылардың қоғамдық көлік жүйесіндегі тәжірибесін арттыратын транзиттік желіні жобалау. Транзиттік желінің мұндай мысалын жол жүру уақытын ескере отырып құруға болады. Жол жүру уақытынан басқа, экономикалық және географиялық шектеулерге байланысты басқа да жағдайлар жасалуы мүмкін. Параметрлердің өзгеруіне қарамастан к ең қысқа алгоритмдер пайдаланушының барлық дерлік қажеттіліктерін қанағаттандыратын ең оңтайлы шешімдерді табады. Мұндай қосымшалар к ең қысқа алгоритмдер кең таралуда, жақында Xu, He, Song, and Chaudry (2012) к транзиттік желі жүйелеріндегі ең қысқа жол проблемалары. ^[8]

Қолданбалар

The к ең қысқа маршруттау:

Географиялық жолды жоспарлау
Желілік маршруттау, әсіресе торлы оптикалық желі қолдану арқылы шешілмейтін қосымша шектеулер бар жерде қарапайым қысқа алгоритмдер.
Есептеу лингвистикасындағы гипотеза генерациясы
Биоинформатикадағы реттілік және метаболикалық жолды табу
Нысанды бірнеше рет бақылау жоғарыда сипатталғандай
Жол тораптары: жол айырықтары - түйіндер (шыңдар) және графиктің әр шеті (сілтемесі) екі түйіспе арасындағы жол сегментімен байланысты.

Байланысты проблемалар

The бірінші іздеу алгоритмі іздеу тек екі операциямен шектелгенде қолданылады.
The Floyd – Warshall алгоритмі барлық жұптардың ең қысқа жолдарын шешеді.
Джонсонның алгоритмі барлық жұптардың ең қысқа жолдарын шешеді және Флойд-Уоршаллға қарағанда жылдамырақ болуы мүмкін сирек графиктер.
Пербуртация теориясы жергілікті жерде ең қысқа жолды (ең нашар жағдайда) табады.

Черкасский және басқалар.^[9] көп алгоритмдер мен байланысты бағалауды қамтамасыз етіңіз.

Сондай-ақ қараңыз

Шектелген қысқа маршруттау

Ескертулер

^ Майкл Гюнтер және басқалар. “. Символикалық есептеу к- стохастикалық алгебра құралының CASPA көмегімен ең қысқа жолдар және онымен байланысты шаралар ». In: Ақаулыққа төзімді жүйелер үшін сенімділік модельдерінің динамикалық аспектілері туралы халықаралық семинар (DYADEM-FTS), ACM Press (2010) 13-18.
^ ^а ^б Эппштейн, Дэвид (1998). «The к Ең қысқа жолдар » (PDF). SIAM J. Comput. 28 (2): 652–673. дои:10.1137 / S0097539795290477.
^ ^а ^б ^c Yen, J. Y. (1971). «The к-Желідегі ең қысқа циклсыз жолдар ». Менеджмент ғылымы. 1 7 (11): 712–716. дои:10.1287 / mnsc.17.11.712..
^ ^а ^б ^c ^г. ^e ^f Булье, Эрик; Эллинас, Георгиос; Лабуретт, Жан-Франсуа; Рамамурти, Раму (2007). «Жолды бағыттау - 2 бөлім: Эвристика». Торлы оптикалық желілердегі жолды бағыттау. Джон Вили және ұлдары. 125-138 беттер. ISBN 9780470015650.
^ Fox, B. L. (1975). «Қықтималдық желілеріне ең қысқа жолдар мен қосымшалар ». ORSA / TIMS бірлескен ұлттық кездесуі. 23: B263. CiNii ұлттық мақаласының идентификаторы: 10012857200.
^ Хершбергер, Джон; Максель, Матай; Сури, Субхаш (2007). «The к Қысқа қарапайым жолдар: жаңа алгоритм және оны жүзеге асыру » (PDF). Алгоритмдер бойынша ACM транзакциялары. 3 (4). 45-бап (19 бет). дои:10.1145/1290672.1290682.
^ Акуба, Такуя; Хаяси, Таканори; Нори, Нозоми; Ивата, Йоичи; Йошида, Юичи (қаңтар 2015). «Тиімді Top-к «Үлкен желілерде қашықтықтағы қысқа қашықтықтағы сұраулар кесілген бағдар белгісімен». Жасанды интеллект бойынша AAAI жиырма тоғызыншы конференциясының материалдары. Остин, Техас: Жасанды интеллектті дамыту ассоциациясы. 2-8 бет.
^ Xu, W., He, S., Song, R., & Chaudhry, S. (2012). Табу к кестеге негізделген транзиттік желідегі ең қысқа жолдар. Компьютерлер және операцияларды зерттеу, 39 (8), 1812-1826. дои:10.1016 / j.cor.2010.02.005
^ Черкасский, Борис V .; Голдберг, Эндрю В.; Радзик, Томаш (1996). «Қысқа жолдар алгоритмдері: теория және эксперименттік бағалау». Математикалық бағдарламалау. Сер. A 73 (2): 129–174.

Сыртқы сілтемелер

Йен алгоритмін жүзеге асыру
Йен және ең жылдам k ең қысқа қарапайым жолдар алгоритмдерін енгізу
http://www.technical-recipes.com/2012/the-k-shortest-paths-algorithm-in-c/#more-2432
K-қысқа жол алгоритмін қолдана отырып, бірнеше объектілерді қадағалау әдістемесі: http://cvlab.epfl.ch/software/ksp/
Компьютерлік көру зертханасы: http://cvlab.epfl.ch/software/ksp/

[1] Майкл Гюнтер және басқалар. “. Символикалық есептеу к- стохастикалық алгебра құралының CASPA көмегімен ең қысқа жолдар және онымен байланысты шаралар ». In: Ақаулыққа төзімді жүйелер үшін сенімділік модельдерінің динамикалық аспектілері туралы халықаралық семинар (DYADEM-FTS), ACM Press (2010) 13-18.

[Eppstein-2] а ^б Эппштейн, Дэвид (1998). «The к Ең қысқа жолдар » (PDF). SIAM J. Comput. 28 (2): 652–673. дои:10.1137 / S0097539795290477.

[Yen-3] а ^б ^c Yen, J. Y. (1971). «The к-Желідегі ең қысқа циклсыз жолдар ». Менеджмент ғылымы. 1 7 (11): 712–716. дои:10.1287 / mnsc.17.11.712..

[Bouillet-4] а ^б ^c ^г. ^e ^f Булье, Эрик; Эллинас, Георгиос; Лабуретт, Жан-Франсуа; Рамамурти, Раму (2007). «Жолды бағыттау - 2 бөлім: Эвристика». Торлы оптикалық желілердегі жолды бағыттау. Джон Вили және ұлдары. 125-138 беттер. ISBN 9780470015650.

[5] Fox, B. L. (1975). «Қықтималдық желілеріне ең қысқа жолдар мен қосымшалар ». ORSA / TIMS бірлескен ұлттық кездесуі. 23: B263. CiNii ұлттық мақаласының идентификаторы: 10012857200.

[6] Хершбергер, Джон; Максель, Матай; Сури, Субхаш (2007). «The к Қысқа қарапайым жолдар: жаңа алгоритм және оны жүзеге асыру » (PDF). Алгоритмдер бойынша ACM транзакциялары. 3 (4). 45-бап (19 бет). дои:10.1145/1290672.1290682.

[7] Акуба, Такуя; Хаяси, Таканори; Нори, Нозоми; Ивата, Йоичи; Йошида, Юичи (қаңтар 2015). «Тиімді Top-к «Үлкен желілерде қашықтықтағы қысқа қашықтықтағы сұраулар кесілген бағдар белгісімен». Жасанды интеллект бойынша AAAI жиырма тоғызыншы конференциясының материалдары. Остин, Техас: Жасанды интеллектті дамыту ассоциациясы. 2-8 бет.

[8] Xu, W., He, S., Song, R., & Chaudhry, S. (2012). Табу к кестеге негізделген транзиттік желідегі ең қысқа жолдар. Компьютерлер және операцияларды зерттеу, 39 (8), 1812-1826. дои:10.1016 / j.cor.2010.02.005

[9] Черкасский, Борис V .; Голдберг, Эндрю В.; Радзик, Томаш (1996). «Қысқа жолдар алгоритмдері: теория және эксперименттік бағалау». Математикалық бағдарламалау. Сер. A 73 (2): 129–174.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]