Блог

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

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

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

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

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

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

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