我正在寻求解决一个问题，其中我有一个加权有向图，并且必须从原点开始，至少访问所有顶点一次并以尽可能最短的路径返回原点。本质上，这将是 TSP 的一个经典示例，除了我DO NOT具有每个顶点只能被访问一次的约束。在我的例子中，除了原点之外的任何顶点都可以沿着路径被访问任意次数，如果这使得路径更短的话。例如在包含顶点的图中V1, V2, V3考虑到它是最短路径，这样的路径是有效的：
ORIGIN -> V1 -> V2 -> V1 -> V3 -> V1 -> ORIGIN
因此，我有点不知道该采取什么方法来解决这个问题，因为通常用于在指数时间内解决 TSP 问题的经典动态规划算法方法并不合适。
典型的方法是创建一个距离矩阵，给出任意两个节点之间的最短路径距离。所以d(i,j)= 最短路径（沿着网络的边缘）i to j。这可以使用 Dijkstra 算法来完成。
现在只需求解具有距离的经典 TSPd(i,j)。您的 TSP 不“知道”实际遵循的路线可能涉及多次访问某个节点。同时，也会保证车辆在每个节点都停下来。
现在，至于效率：正如 @Codor 指出的，TSP 是 NP 难的，你的变体也是 NP 难的，所以你不会找到一个可证明最优的多项式时间算法。然而，对于 TSP 来说，仍然有很多很多好的算法（启发式算法和精确算法），并且其中大多数应该适合您的问题。 （一般来说，DP是notTSP 的出路。）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
