Все пары кратчайшего пути - теплый перезапуск?

Можно ли запустить любой из известных алгоритмов (Dijkstra/Floyd-Warshall и т. д.) для задачи APSP, чтобы иметь возможность уменьшить временную сложность и, возможно, время вычислений?

Допустим, граф представлен матрицей NxN. Я рассматриваю только изменения в одном или нескольких элементах матрицы (‹‹ N), то есть расстояние между соответствующими вершинами, между любыми 2 вызовами процедуры алгоритма. Можем ли мы использовать решение из первого вызова и только дополнительные изменения в матрице, чтобы ускорить вычисления при втором вызове алгоритма? В первую очередь я смотрю на плотные матрицы, но если есть известные методы для разреженных матриц, поделитесь ими. Спасибо.


algorithm shortest-path dijkstra floyd-warshall
person user3282279    schedule 07.02.2014    source источник
comment
Меня тоже интересуют ответы на этот вопрос, но я думаю, что лучше опубликовать его на cs.stackexchange.com . Возможно, вы захотите предоставить более подробную информацию, например, смотрите ли вы на один и тот же источник и приемник для разных вызовов (в этом случае я думаю, что можно было бы повторно использовать некоторые значения)   -  person yanhan    schedule 07.02.2014
comment
Спасибо за совет - я также опубликую его на cs stackexchange. Меня больше интересует общий случай определения расстояний между всеми парами узлов/вершин в каждом вызове (и, если возможно, путь с наименьшей стоимостью).   -  person user3282279    schedule 07.02.2014
comment
К вашему сведению: я заметил следующее обсуждение cs stackexchange по теме динамических графов: cs.stackexchange.com/q/7250/14479   -  person user3282279    schedule 07.02.2014

Ответы (2)


arrow_upward
2
arrow_downward

Я не знаю инкрементного алгоритма для APSP. Однако существует инкрементная версия A* для решения SSSP, называемая Lifelong Planning A* (также известная как LPA*, редко называемая также «Incremental A*»), которая, похоже, является тем, что вам нужно. вопрос во втором абзаце.

Здесь находится ссылка на исходную статью. Дополнительную информацию об этом можно найти в этом сообщении о вариантах A*.

person BlueRaja - Danny Pflughoeft    schedule 07.02.2014

arrow_upward
1
arrow_downward

Интересный исследовательский документ: Experimental Analysis of Dynamic All Pairsestest Алгоритмы пути [Деметреску, Эмилиоцци, Итальяно]:

Мы представляем результаты обширного вычислительного исследования динамических алгоритмов для всех пар задач поиска кратчайшего пути. Мы описываем наши реализации недавних динамических алгоритмов Кинга [18] и Деметреску и Итальяно [7] и сравниваем их с динамическим алгоритмом Рамалингама и Репса [25] и со статическими алгоритмами на случайных, реальных и жестких экземплярах. . Наши экспериментальные данные показывают, что некоторые динамические алгоритмы и их алгоритмические приемы могут иметь практическую ценность во многих ситуациях.

Еще одним интересным распределенным алгоритмом является разработка Новый алгоритм для распределенных кратчайших путей в динамических сетях [Чицерон, Д'Анджело, Ди Стефано, Фриджиони, Маурицио]:

Мы изучаем проблему динамического обновления кратчайших путей для всех пар в распределенной сети, когда в сети выполняются операции обновления границ. Мы рассматриваем практический случай динамической сети, в которой обновление границы может происходить в то время, когда одно или несколько других обновлений границы находятся в процессе обработки.

Вы можете найти дополнительные ресурсы по запросу Кратчайшие пути для всех пар в динамических сетях.

person Lior Kogan    schedule 07.02.2014