我只是想知道 TSP 的所有算法是否都会给出相同的最佳路线？我认为会是这种情况，但我实现了分支和绑定以及 A*，它们都对相同的输入给出了非常不同的结果，我只是想知道这是否正常？
问问题
388 次
2 回答
2
我的路线不同，但所有最佳解决方案的成本应该是相同的。
如果您的 A* 解决方案更昂贵，则说明您的启发式方法是错误的。查看wikipedia A* algorithm以证明它总能找到最佳解决方案。
于 2013-01-17T18:13:34.570 回答
1
不会。如果存在不止一条最优路径，不同的算法不一定会找到相同的路径。这将取决于实现，我假设它还取决于您如何标记图形，因此不同的标记将使相同的算法找到不同的路线。
于 2013-01-17T18:14:12.920 回答