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

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

обнаружение k кратчайшие пути возможны путем расширения Алгоритм Дейкстры или Алгоритм Беллмана-Форда и расширьте их, чтобы найти более одного пути.

История

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

Алгоритм

В Алгоритм Дейкстры можно обобщить, чтобы найти k кратчайшие пути.

Определения:
  • G (V, E): взвешенный ориентированный граф, с набором вершины V и набор направленных края E,
  • ш (и, в): стоимость направленного ребра от узла ты узел v (затраты неотрицательны).
Ссылки, не удовлетворяющие ограничениям на кратчайший путь, удаляются с графа.
  • s: исходный узел
  • т: целевой узел
  • K: количество кратчайших путей для поиска
  • пты: путь от s к ты
  • B это структура данных кучи, содержащая пути
  • п: набор кратчайших путей из s к т
  • считатьты: количество найденных кратчайших путей к узлу ты

Алгоритм:

п = пусто,
считатьты = 0 для всех u в V
вставить путь пs = {s} в B со стоимостью 0
в то время как B не пусто и считатьт < K:
- позволять пты быть кратчайшим путем затрат в B со стоимостью C
– B = B − {Пты }, считатьты = считатьты + 1
- если ты = т тогда п = п U {Пты}
- если считатьты ≤ K тогда
  • для каждой вершины v рядом с ты:
- позволять пv быть новым путем с ценой C + ш (и, в) образованный конкатенацией края (u, v) к пути пты
- вставлять пv в B
вернуть п

Вариации

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

Петлевой вариант

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

Вариант без петель

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

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

Пример # 1

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

Сеть из 15 узлов, содержащая комбинацию двунаправленных и однонаправленных каналов

Пример # 2

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

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

Пример # 3

Другое использование k Алгоритмы кратчайших путей - это разработка транспортной сети, которая расширяет возможности пассажиров в системах общественного транспорта. Такой пример транзитной сети можно построить, если учесть время в пути. Помимо времени в пути, могут быть приняты другие условия в зависимости от экономических и географических ограничений. Несмотря на вариации параметров, k Алгоритмы кратчайшего пути находят наиболее оптимальные решения, удовлетворяющие практически все потребности пользователей. Такие приложения k алгоритмы кратчайшего пути становятся распространенными, недавно Xu, He, Song и Chaudry (2012) изучали k проблемы кратчайшего пути в системах транзитных сетей. [8]

Приложения

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

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

Черкасский и др.[9] предоставить больше алгоритмов и связанных оценок.

Смотрите также

Заметки

  1. ^ Михаэль Гюнтер и др.: «Символический расчет k-короткие пути и связанные меры с помощью инструмента алгебры стохастических процессов CASPA ». В: Международный семинар по динамическим аспектам моделей надежности для отказоустойчивых систем (DYADEM-FTS), ACM Press (2010) 13–18.
  2. ^ а б Эппштейн, Дэвид (1998). "Поиск k Кратчайшие пути » (PDF). SIAM J. Comput. 28 (2): 652–673. Дои:10.1137 / S0097539795290477.
  3. ^ а б c Йен, Дж. Й. (1971). "Поиск k-Короткие пути без петель в сети ». Наука управления. 1 7 (11): 712–716. Дои:10.1287 / mnsc.17.11.712..
  4. ^ а б c d е ж Булье, Эрик; Эллинас, Георгиос; Лабурдетт, Жан-Франсуа; Рамамурти, Раму (2007). «Маршрутизация пути - часть 2: эвристика». Маршрутизация пути в ячеистых оптических сетях. Джон Уайли и сыновья. С. 125–138. ISBN  9780470015650.
  5. ^ Фокс, Б. Л. (1975). "KКратчайшие пути и приложения к вероятностным сетям ». Совместное национальное совещание ORSA / TIMS. 23: B263. Национальный идентификатор статьи CiNii: 10012857200.
  6. ^ Хершбергер, Джон; Максель, Мэтью; Сури, Субхаш (2007). "Поиск k Кратчайшие простые пути: новый алгоритм и его реализация » (PDF). ACM-транзакции на алгоритмах. 3 (4). Статья 45 (19 страниц). Дои:10.1145/1290672.1290682.
  7. ^ Акуба, Такуя; Хаяси, Таканори; Нори, Нозоми; Ивата, Йоичи; Ёсида, Юичи (январь 2015). «Эффективный топ-k Запросы по кратчайшему пути в больших сетях с помощью сокращенной маркировки ориентиров ". Материалы двадцать девятой конференции AAAI по искусственному интеллекту. Остин, Техас: Ассоциация развития искусственного интеллекта. С. 2–8.
  8. ^ Сюй, В., Хе, С., Сонг, Р., и Чаудри, С. (2012). Нахождение k кратчайшие пути в транзитной сети по расписанию. Компьютеры и исследования операций, 39 (8), 1812-1826. Дои:10.1016 / j.cor.2010.02.005
  9. ^ Черкасский, Борис В .; Гольдберг, Эндрю В.; Радзик, Томаш (1996). «Алгоритмы кратчайших путей: теория и экспериментальная оценка». Математическое программирование. Сер. А 73 (2): 129–174.

внешняя ссылка