可以多次访问顶点的 TSP
TSP Where Vertices Can be Visited Multiple Times
我想解决一个问题，我有一个加权有向图，我必须从原点开始，至少访问所有顶点一次，然后 return 以尽可能短的路径到达原点。本质上这将是 TSP 的经典示例，除了我 DO NOT 有每个顶点只能访问一次的约束。在我的例子中，任何不包括原点的顶点都可以沿着路径访问任意次数，如果这会使路径更短的话。因此，例如在包含顶点 V1, V2, V3 的图中，这样的路径是有效的，因为它是最短路径：
ORIGIN -> V1 -> V2 -> V1 -> V3 -> V1 -> ORIGIN
因此，我有点纠结于采用什么方法来解决这个问题，因为通常用于解决指数时间 TSP 问题的经典动态规划算法方法并不适用。
为了部分回答问题，问题中描述的问题不承认多项式时间算法，除非 P=NP 通过以下论证。显然，所提出的问题包括欧几里德的实例。然而，欧几里德实例的最优解没有重复的节点，因为这样的解决方案可以通过使用三角不等式删除额外的节点来改进。然而，根据 TSP 上的 Wikipedia article，欧几里德 TSP 仍然是 NP-hard。这意味着问题中的任何多项式时间算法都能够将欧几里德 TSP 求解到多项式时间的最优性，这是不可能的，除非 P=NP.
典型的方法是创建一个距离矩阵，给出任意两个节点之间的最短路径距离。所以 d(i,j) = 从 i 到 j 的最短路径（沿着网络的边缘）。这可以使用 Dijkstra 算法来完成。
现在只需求解距离为 d(i,j) 的经典 TSP。您的 TSP 不会 "know" 实际遵循的路线可能涉及多次访问节点。同时保证车辆在每个节点都停
现在，关于效率：正如@Codor 指出的那样，TSP 是 NP-hard，您的变体也是 NP-hard，因此您不会找到可证明的最佳多项式时间算法。但是，TSP 仍然有很多很多好的算法（启发式和精确算法），其中大部分应该适合您的问题。 （一般来说，DP 不是 TSP 的方法。）
我想解决一个问题，我有一个加权有向图，我必须从原点开始，至少访问所有顶点一次，然后 return 以尽可能短的路径到达原点。本质上这将是 TSP 的经典示例，除了我 DO NOT 有每个顶点只能访问一次的约束。在我的例子中，任何不包括原点的顶点都可以沿着路径访问任意次数，如果这会使路径更短的话。因此，例如在包含顶点 V1, V2, V3 的图中，这样的路径是有效的，因为它是最短路径：
ORIGIN -> V1 -> V2 -> V1 -> V3 -> V1 -> ORIGIN
因此，我有点纠结于采用什么方法来解决这个问题，因为通常用于解决指数时间 TSP 问题的经典动态规划算法方法并不适用。
为了部分回答问题，问题中描述的问题不承认多项式时间算法，除非 P=NP 通过以下论证。显然，所提出的问题包括欧几里德的实例。然而，欧几里德实例的最优解没有重复的节点，因为这样的解决方案可以通过使用三角不等式删除额外的节点来改进。然而，根据 TSP 上的 Wikipedia article，欧几里德 TSP 仍然是 NP-hard。这意味着问题中的任何多项式时间算法都能够将欧几里德 TSP 求解到多项式时间的最优性，这是不可能的，除非 P=NP.
典型的方法是创建一个距离矩阵，给出任意两个节点之间的最短路径距离。所以 d(i,j) = 从 i 到 j 的最短路径（沿着网络的边缘）。这可以使用 Dijkstra 算法来完成。
现在只需求解距离为 d(i,j) 的经典 TSP。您的 TSP 不会 "know" 实际遵循的路线可能涉及多次访问节点。同时保证车辆在每个节点都停
现在，关于效率：正如@Codor 指出的那样，TSP 是 NP-hard，您的变体也是 NP-hard，因此您不会找到可证明的最佳多项式时间算法。但是，TSP 仍然有很多很多好的算法（启发式和精确算法），其中大部分应该适合您的问题。 （一般来说，DP 不是 TSP 的方法。）