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

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

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

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


graph-theory graph-algorithm directed-graph traveling-salesman
person Alk    schedule 03.10.2016    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

person LarrySnyder610    schedule 07.10.2016

arrow_upward
1
arrow_downward

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

person Codor    schedule 03.10.2016
comment
Спасибо за это объяснение. Я думаю, что это довольно часто встречающаяся проблема, я попытаюсь объяснить ее на простом примере: допустим, у нас есть школьный автобус, который уезжает из школы, высаживает детей в их дома и возвращается в школу, когда все дети упал. Предположим, у нас в автобусе есть дети A, B, C. Автобус может высадить ребенка B, затем проследовать к дому ребенка C, теперь, если есть прямой путь от C к дому A, но путь к дому A, который проходит рядом с домом B, короче, мы должны выбрать путь C - ›B -› A, а не C - ›A. - person Alk; 03.10.2016