TSP Где вершины могут быть посещены несколько раз

Question

Я ищу решение проблемы, когда у меня есть взвешенный ориентированный граф, и я должен начать с начала координат, по крайней мере один раз посетить все вершины и вернуться к началу координат по кратчайшему пути. По сути, это был бы классический пример TSP, за исключением того, что у нет. В моем случае любая вершина, исключая начало координат, может посещаться любое количество раз по пути, если это делает путь короче. Так, например, в виде графа, содержащего вершины V1, V2, V3 путь, как это было бы в силе, учитывая, что это самый короткий путь:

ORIGIN -> V1 -> V2 -> V1 -> V3 -> V1 -> ORIGIN

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

Answer 1

Типичный подход заключается в создании матрицы расстояния, которая дает кратчайшее расстояние между любыми двумя узлами. Таким образом, d(i,j) = кратчайший путь (по краям сети) от i до j. Это можно сделать с использованием алгоритма Дейкстры.

Теперь просто решите классический TSP с расстояниями d(i,j). Ваш TSP не «знает», что фактический маршрут должен включать посещение узла несколько раз. В то же время он гарантирует, что транспортное средство останавливается на каждом узле.

Теперь, что касается эффективности: как указывает @Codor, TSP NP-hard, и поэтому ваш вариант его, поэтому вы не найдете доказуемо оптимального алгоритма с полиномиальным временем. Тем не менее, для TSP все еще существует много хороших алгоритмов (как эвристических, так и точных), и большинство из них должно быть подходящим для вашей проблемы. (В общем, DP не путь для TSP.)

Answer 2

Чтобы ответить на вопрос частично, проблема, описанная в вопросе, не допускает алгоритм полиномиального времени, кроме P=NP, следующим аргументом. Очевидно, что предлагаемая проблема включает примеры, которые являются евклидовыми. Однако ни одно оптимальное решение для евклидова экземпляра не имеет повторяющихся узлов, так как такое решение можно улучшить, удалив дополнительные узлы, используя неравенство треугольника. Однако, согласно Wikipedia article на TSP, Euclidean TSP по-прежнему NP -hard. Это означает, что любой алгоритм полиномиального времени для задачи в вопросе сможет решить евклидову TSP до оптимальности по полиномиальному времени, что невозможно, если P=NP.