2

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

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

4

2 回答 2

1

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

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

于 2011-09-18T12:27:48.417 回答
1

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

于 2011-09-02T23:09:50.543 回答