Создайте путь с наименьшей стоимостью между двумя вершинами

Question

У меня есть взвешенный неориентированный график. Учитывая две вершины в этом графе, у которых нет пути между ними, я хочу создать путь между ними, добавляя ребра в граф, увеличивая общий вес графа как можно меньше. Есть ли известный алгоритм определения того, какие ребра добавить?

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

Вот небольшая иллюстрация; красный и зеленый - это вершины, которые я хочу соединить, черные линии - это существующие ребра, а синяя линия - путь, которым я хочу существовать.

Есть ли известный алгоритм, который дает ребра, отсутствующие на этом пути?

Answer 1

Вы можете использовать алгоритм A * с нулевым весом для существующих ребер и расстояния (или любой другой стоимости, которая имеет смысл) для отсутствующих ребер.

https://en.wikipedia.org/wiki/A*_search_algorithm

Answer 2

На самом деле Dijkstra с некоторой предварительной обработкой - лучший друг для вас.

Я ответил на проблему, которая может быть похожа на эту: Какова временная сложность, если требуется пересмотреть посещенные узлы в BFS?

Что я вижу общего - вы хотите использовать как можно больше существующих дорог. Также вам иногда нужно сломать это и построить новую дорогу. Суть в том, чтобы установить правильные веса для существующих и для «возможно новых».

Каков будет мой подход - допустим, что каждый 1 км существующей дороги имеет стоимость 1. Вы можете суммировать все существующие дороги на своем графике и предположить, что в общей сложности 1000 км. Затем я предварительно обработал бы весь граф, и из каждого узла (города) я бы создал путь ко всем другим городам, не связанным напрямую, и каждый из них стоил бы 1000 + 1000 за километр, а затем запустил на нем Дейкстру.

Он будет автоматически использовать как можно больше существующих дорог и создавать как можно меньше новых дорог.

Также вы можете немного поиграть с этими настройками, чтобы достичь желаемого.

Представьте, что есть два города, которые находятся всего в 100 метрах друг от друга. А между существующими дорогами есть путь, который занимает 20 000 км. С настройками, которые я предложил, вы получите 20000 км пути как лучший (который удовлетворяет потребности «не строить никаких новых дорог, если в этом нет необходимости»). Иногда вы действительно этого хотите. Иногда нет. Если вы этого не сделаете, вы можете подумать: «Хорошо, если я строю, как немного лишней дороги, и это резко уменьшает расстояние, это еще лучшее решение». Если это так, вы можете подумать о снижении цены на новые дороги (например, удаление первоначальной стоимости, или стоимости за километр, или того и другого - это зависит от того, что вы выберете в качестве наилучшего результата).

Answer 3

Я не думаю, что есть принятый алгоритм. Но вы можете попытаться сделать следующее. Сначала запустите триангуляцию Виттерби, а затем выполните поиск в глубину на этом полностью связанном графике. Возьмите сумму новых ссылок в пути от A -> B. Удалите самую длинную новую ссылку и повторите. Как только путь из A -> B не может быть достигнут, проверьте предыдущие решения, чтобы увидеть, какое из решений имело наименьшую сумму новых ссылок.