graph-theory - 如何找到从预定顶点开始至少一次访问无向加权图中每个顶点的最低成本？

Question

所采取的路径不必在预定顶点处结束。基本上是旅行商问题，除了一个顶点可以被访问不止一次。

编辑：最多有 10,000 个顶点和边

Answer 1

由于在标准 TSP 定义中，解决方案是哈密顿循环（或巡回），因此它不必是最优的。实际上，正如您所描述的，TSP 是一个寻找最短路径的优化问题。

问题仍然是NP-hard，并且可以通过找到接近最优解的算法来解决。这是您搜索“旅行推销员问题的启发式”（pdf）时得到的结果之一。

Answer 2

不确定，但我认为它是最优的（也许不是最有效的想法）：计算每对点之间的最小路径，然后在此图上应用旅行推销员。