graph-algorithm - 可以多次访问顶点的 TSP

Question

我想解决一个问题，我有一个加权有向图，我必须从原点开始，至少访问所有顶点一次，然后以尽可能短的路径返回原点。从本质上讲，这将是 TSP 的一个经典示例，除了我不有每个顶点只能访问一次的约束。在我的例子中，任何不包括原点的顶点都可以沿着路径访问任意次数，如果这会使路径更短的话。因此，例如在包含顶点 V1、V2、V3 的图中，这样的路径是有效的，因为它是最短路径:

起源 -> V1 -> V2 -> V1 -> V3 -> V1 -> 起源

因此，我有点纠结于采用什么方法来解决这个问题，因为通常用于解决指数时间 TSP 问题的经典动态规划算法方法并不适用。

Answer 1

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

现在只需求解距离为 d(i,j) 的经典 TSP。您的 TSP 不“知道”所遵循的实际路线可能涉及多次访问节点。同时保证车辆在每个节点都停靠。

现在，关于效率:正如@Codor 指出的那样，TSP 是 NP-hard，您的变体也是 NP-hard，因此您不会找到可证明的最佳多项式时间算法。但是，TSP 仍然有很多很多好的算法(启发式和精确算法)，其中大部分应该适合您的问题。 (一般来说，DP 不是 TSP 的方式。)