可以多次访问顶点的TSP

Question

我正在寻找解决一个问题，其中我有一个加权有向图，我必须从原点开始，至少访问一次所有顶点并以最短路径返回原点。本质上这将是TSP的一个典型例子，除了我不要有限制，每个顶点只能访问一次。在我的情况下，除了原点以外的任何顶点都可以沿路径访问任意次数，如果这样可以缩短路径的话。因此，例如在包含顶点V1, V2, V3这样的路径将是有效的，因为它是最短的路径图：

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

结果，我被困在采取什么办法有点为了解决这个问题，作为通常用于解决指数时间TSP问题的经典动态规划算法方法并不适合。

Answer 1

典型的方法是创建一个距离矩阵，给出任意两个节点之间的最短路径距离。所以d(i,j) =从i到j的最短路径（在网络边缘之后）。这可以使用Dijkstra算法完成。

现在只需要解决一个距离为d(i,j)的古典TSP。您的TSP不会“知道”所遵循的实际路线可能涉及多次访问节点。同时，它将确保车辆停在每个节点。

至于效率：正如@Codor指出的那样，TSP是NP难的，你的变体也是NP难题，所以你不会找到一个可证明的最优多项式时间算法。但是，对于TSP，仍然有许多很好的算法（启发式和精确算法），并且大多数算法都适合您的问题。 （一般来说，DP是而不是要走TSP的路。）

Answer 2

要回答这个问题的部分原因，除非P=NP通过以下参数，问题中描述的问题不承认多项式时间算法。显然，所提出的问题包括欧几里得的例子。然而，欧几里得实例的最优解没有重复的节点，因为这样的解决方案可以通过使用三角形不等式来删除额外的节点来改进。但是，根据TSP上的Wikipedia article，欧几里德TSP仍然是硬件。这意味着问题的任何多项式时间算法都能够解决欧几里德TSP在多项式时间上的最优性，除非P=NP，否则这是不可能的。