k маршрутизация по кратчайшему пути

Задача k маршрутизации по кратчайшему пути является обобщением задачи маршрутизации по кратчайшему пути в данной сети. Он запрашивает не только кратчайший путь, но и следующие k−1 кратчайших путей (которые могут быть длиннее кратчайшего пути). Разновидностью проблемы являются k кратчайших путей без петель.

Найти k кратчайших путей можно путем расширения алгоритма Дейкстры или алгоритма Беллмана-Форда . ^{[ нужна ссылка ]}

История

С 1957 года было опубликовано множество статей по проблеме маршрутизации k кратчайшего пути. Большинство фундаментальных работ было выполнено в период с 1960-х по 2001 год. С тех пор большая часть исследований была посвящена приложениям проблемы и ее вариантам. В 2010 году Михаэль Гюнтер и др. опубликовал книгу « Символическое вычисление k -кратчайших путей и связанных с ними мер с помощью инструмента алгебры стохастических процессов CASPA» . ^[1]

Алгоритм

Алгоритм Дейкстры можно обобщить для поиска k кратчайших путей. ^{[ нужна ссылка ]}

Определения : G(V, E) : взвешенный ориентированный граф с набором вершин V и набором направленных ребер E , w(u, v) : стоимость направленного ребра от узла u до узла v (стоимость неотрицательна). Ссылки, не удовлетворяющие ограничениям на кратчайший путь, удаляются из графа. s : исходный узел t : узел назначения K : количество кратчайших путей, которые нужно найти. p _u : путь от s до u B — это структура данных кучи, содержащая пути P : набор кратчайших путей от s до t count _u : количество найденных кратчайших путей к узлу u Алгоритм: P = пусто, посчитайте _u = 0, для всех u в V вставить путь p _s = {s} в B со стоимостью 0 в то время как B не пусто и посчитайте _t < K : – пусть p _u – кратчайший путь стоимости в B со стоимостью C – B = B − {p _ты } , кол _и = кол _и + 1 – если u = t , то P = P U {p _u } – если count _u ≤ K , то для каждой вершины v, смежной с u : – пусть p _v — новый путь со стоимостью C + w(u, v), образованный путем объединения ребра (u, v) в путь p _u – вставьте p _v в B вернуть Р

Вариации

Существует два основных варианта задачи маршрутизации k кратчайшего пути. В одном варианте путям разрешено посещать один и тот же узел более одного раза, создавая таким образом петли. В другом варианте пути должны быть простыми и не иметь циклов . Зацикленную версию можно решить с помощью алгоритма Эппштейна. ^[2] а вариант без цикла разрешим с помощью алгоритма Йена . ^[3]^[4]

Зацикленный вариант

В этом варианте проблема упрощается, поскольку не требуется, чтобы пути были без циклов. ^[4] Решение было дано Б. Л. Фоксом в 1975 году, в котором k -кратчайшие пути определяются с O ( m + kn log n ) асимптотической временной сложностью (с использованием big O) обозначения . ^[5] В 1998 году Дэвид Эппштейн сообщил о подходе, который поддерживает асимптотическую сложность O ( m + n log n + k ) путем вычисления неявного представления путей, каждый из которых может быть выведен за O ( n ) дополнительного времени. ^[2]^[4] В 2015 году Акиба и др. разработал метод индексации как значительно более быструю альтернативу алгоритму Эппштейна, в котором структура данных, называемая индексом, создается из графа, а затем можно быстро получить расстояния top- k между произвольными парами вершин. ^[6]

Безпетлевой вариант

В варианте без циклов путям запрещено содержать циклы, что добавляет дополнительный уровень сложности. ^[4] Ее можно решить с помощью алгоритма Йена. ^[3]^[4] найти длины всех кратчайших путей от фиксированного узла ко всем остальным узлам в n -узловой сети с неотрицательными расстояниями, метод, требующий всего 2 n ² дополнения и н ² сравнению, меньше, чем нужно другим доступным алгоритмам кратчайшего пути . Сложность времени выполнения является псевдополиномиальной и составляет O ( kn ( m + n log n )) (где m и n представляют количество ребер и вершин соответственно). ^[3]^[4] В 2007 году Джон Хершбергер и Субхаш Сури предложили алгоритм замены путей, более эффективную реализацию алгоритма Лоулера. ^[7] и алгоритм Йена с улучшением O ( n ) во времени для большого количества графов, но не для всех (поэтому не меняя асимптотическую границу алгоритма Йена). ^[8]

Некоторые примеры и описание

Пример 1

В следующем примере модель Йена используется для поиска k кратчайших путей между сообщающимися конечными узлами. То есть он находит кратчайший путь, второй кратчайший путь и т. д. до K. ^й кратчайший путь. Более подробную информацию можно найти здесь .Код, представленный в этом примере, пытается решить задачу маршрутизации по кратчайшему пути для сети из 15 узлов, содержащей комбинацию однонаправленных и двунаправленных каналов:

Пример 2

Другим примером является использование алгоритма k кратчайших путей для отслеживания нескольких объектов. Этот метод реализует систему отслеживания нескольких объектов на основе алгоритма маршрутизации k кратчайших путей. В качестве входных данных используется набор вероятностных карт занятости. Детектор объектов обеспечивает ввод.

Полную информацию можно найти в « Лаборатории компьютерного зрения – CVLAB».

Пример 3

Еще одно применение алгоритмов k кратчайших путей — это проектирование транзитной сети, которая улучшает качество обслуживания пассажиров в системах общественного транспорта. Такой пример транзитной сети можно построить, приняв во внимание время в пути. Помимо времени в пути, могут быть приняты и другие условия в зависимости от экономических и географических ограничений. Несмотря на вариации параметров, k алгоритмов кратчайшего пути находит наиболее оптимальные решения, удовлетворяющие практически всем потребностям пользователя. Такие приложения k алгоритмов кратчайшего пути становятся обычным явлением: недавно Сюй, Хе, Сонг и Чаудри (2012) изучили k задач кратчайшего пути в системах транзитных сетей. ^[9]

Приложения

Маршрутизация по кратчайшему пути является хорошей альтернативой для:

Планирование географического пути
Сетевая маршрутизация, особенно в оптических ячеистых сетях , где существуют дополнительные ограничения, которые невозможно решить с помощью обычных алгоритмов поиска кратчайшего пути .
Генерация гипотез в компьютерной лингвистике
Выравнивание последовательностей и поиск метаболических путей в биоинформатике
Отслеживание нескольких объектов, как описано выше.
Дорожные сети: дорожные развязки — это узлы (вершины), а каждое ребро (ссылка) графа связано с сегментом дороги между двумя перекрестками.

Связанные проблемы

Алгоритм поиска в ширину используется, когда поиск ограничен только двумя операциями.
Алгоритм Флойда – Уоршалла находит все пары кратчайших путей.
Алгоритм Джонсона решает кратчайшие пути всех пар и может быть быстрее, чем Флойд-Уоршалл на разреженных графах .
Теория возмущений находит (в худшем случае) локально кратчайший путь.

Cherkassky et al. ^[10] предоставить больше алгоритмов и связанных с ними оценок.

См. также

Ограниченная маршрутизация по кратчайшему пути

Примечания

^ Гюнтер, Михаэль; Шустер, Иоганн; Сигл, Маркус (27 апреля 2010 г.). «Символический расчет k-кратчайших путей и связанных с ними мер с помощью инструмента алгебры стохастических процессов CASPA». Символическое вычисление k -кратчайших путей и связанных с ними мер с помощью инструмента алгебры стохастических процессов CASPA . АКМ. стр. 13–18. дои : 10.1145/1772630.1772635 . ISBN 978-1-60558-916-9 .
^ Перейти обратно: ^а ^б Эппштейн, Дэвид (1998). «Нахождение k кратчайших путей» (PDF) . СИАМ Дж. Компьютер. 28 (2): 652–673. дои : 10.1137/S0097539795290477 .
^ Перейти обратно: ^а ^б ^с Йен, JY (1971). «Поиск k -кратчайших безпетлевых путей в сети». Наука управления . 1 7 (11): 712–716. дои : 10.1287/mnsc.17.11.712 . .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Булье, Эрик; Эллинас, Георгиос; Лабурдетт, Жан-Франсуа; Рамамурти, Раму (2007). «Маршрутизация пути – Часть 2: Эвристика» . Маршрутизация путей в ячеистых оптических сетях . Джон Уайли и сыновья . стр. 125–138. ISBN 9780470015650 .
^ Фокс, Б.Л. (1975). « К -я кратчайшие пути и приложения к вероятностным сетям». Совместное национальное совещание ORSA/TIMS . 23 : В263. Национальный идентификатор статьи CiNii : 10012857200.
^ Акиба, Такуя; Хаяси, Таканори; Нори, Нозоми; Ивата, Ёичи; Ёсида, Юичи (январь 2015 г.). «Эффективные запросы на расстояние кратчайшего пути Top - k в больших сетях с помощью сокращенной маркировки ориентиров» . Материалы двадцать девятой конференции AAAI по искусственному интеллекту . Остин, Техас: Ассоциация по развитию искусственного интеллекта . стр. 2–8.
^ Лоулер, Юджин Л. (1 марта 1972 г.). «Процедура вычисления K лучших решений задач дискретной оптимизации и ее применение к задаче о кратчайшем пути» . Наука управления . 18 (7): 401–405. дои : 10.1287/mnsc.18.7.401 . ISSN 0025-1909 .
^ Хершбергер, Джон ; Максель, Мэтью; Сури, Субхаш (2007). «Нахождение k кратчайших простых путей: новый алгоритм и его реализация» (PDF) . Транзакции ACM на алгоритмах . 3 (4). Статья 45 (19 страниц). дои : 10.1145/1290672.1290682 . S2CID 10703503 .
^ Сюй, Вангту; Он, Шивэй; Сон, Руи; Чаудри, Сохаил С. (2012). «Нахождение k кратчайших путей в транспортной сети, основанной на расписании». Компьютеры и исследования операций . 39 (8): 1812–1826. дои : 10.1016/j.cor.2010.02.005 . S2CID 29232689 .
^ Черкасский Борис Владимирович; Гольдберг, Эндрю В .; Радзик, Томаш (1996). «Алгоритмы кратчайших путей: теория и экспериментальная оценка». Математическое программирование . 73 (2): 129–174. дои : 10.1007/BF02592101 . ISSN 0025-5610 . S2CID 414427 .

Внешние ссылки

Реализация алгоритма Йена
Реализация алгоритмов Йена и быстрейшего 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] Гюнтер, Михаэль; Шустер, Иоганн; Сигл, Маркус (27 апреля 2010 г.). «Символический расчет k-кратчайших путей и связанных с ними мер с помощью инструмента алгебры стохастических процессов CASPA». Символическое вычисление k -кратчайших путей и связанных с ними мер с помощью инструмента алгебры стохастических процессов CASPA . АКМ. стр. 13–18. дои : 10.1145/1772630.1772635 . ISBN 978-1-60558-916-9 .

[Eppstein-2] Перейти обратно: ^а ^б Эппштейн, Дэвид (1998). «Нахождение k кратчайших путей» (PDF) . СИАМ Дж. Компьютер. 28 (2): 652–673. дои : 10.1137/S0097539795290477 .

[Yen-3] Перейти обратно: ^а ^б ^с Йен, JY (1971). «Поиск k -кратчайших безпетлевых путей в сети». Наука управления . 1 7 (11): 712–716. дои : 10.1287/mnsc.17.11.712 . .

[Bouillet-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж Булье, Эрик; Эллинас, Георгиос; Лабурдетт, Жан-Франсуа; Рамамурти, Раму (2007). «Маршрутизация пути – Часть 2: Эвристика» . Маршрутизация путей в ячеистых оптических сетях . Джон Уайли и сыновья . стр. 125–138. ISBN 9780470015650 .

[5] Фокс, Б.Л. (1975). « К -я кратчайшие пути и приложения к вероятностным сетям». Совместное национальное совещание ORSA/TIMS . 23 : В263. Национальный идентификатор статьи CiNii : 10012857200.

[6] Акиба, Такуя; Хаяси, Таканори; Нори, Нозоми; Ивата, Ёичи; Ёсида, Юичи (январь 2015 г.). «Эффективные запросы на расстояние кратчайшего пути Top - k в больших сетях с помощью сокращенной маркировки ориентиров» . Материалы двадцать девятой конференции AAAI по искусственному интеллекту . Остин, Техас: Ассоциация по развитию искусственного интеллекта . стр. 2–8.

[7] Лоулер, Юджин Л. (1 марта 1972 г.). «Процедура вычисления K лучших решений задач дискретной оптимизации и ее применение к задаче о кратчайшем пути» . Наука управления . 18 (7): 401–405. дои : 10.1287/mnsc.18.7.401 . ISSN 0025-1909 .

[8] Хершбергер, Джон ; Максель, Мэтью; Сури, Субхаш (2007). «Нахождение k кратчайших простых путей: новый алгоритм и его реализация» (PDF) . Транзакции ACM на алгоритмах . 3 (4). Статья 45 (19 страниц). дои : 10.1145/1290672.1290682 . S2CID 10703503 .

[9] Сюй, Вангту; Он, Шивэй; Сон, Руи; Чаудри, Сохаил С. (2012). «Нахождение k кратчайших путей в транспортной сети, основанной на расписании». Компьютеры и исследования операций . 39 (8): 1812–1826. дои : 10.1016/j.cor.2010.02.005 . S2CID 29232689 .

[10] Черкасский Борис Владимирович; Гольдберг, Эндрю В .; Радзик, Томаш (1996). «Алгоритмы кратчайших путей: теория и экспериментальная оценка». Математическое программирование . 73 (2): 129–174. дои : 10.1007/BF02592101 . ISSN 0025-5610 . S2CID 414427 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]