我正在寻找具有已知完美解决方案的完整图上的欧几里德 TSP 问题（多个点之间的最短路径）的实例。有没有人遇到过这样的例子？或者是否有一个简单的算法来生成这样的实例，肯定不会有比生成的更短的路线？
问问题
834 次
1 回答
2
我很确定这有很多问题。看着http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/TSPFAQ.html我明白了
问：给定的解决方案值是否只有已知的最佳值？
答：不，对于每个问题，都列出了可证明的最优解的值或由最知名的下限和上限给出的区间。解决方案的最优性已通过分支切割或分支定界算法得到证明。
另见http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html
当我在 10 多年前发布 TSPLIB 时，我预计至少将大型问题实例解决到已证明的最优性将成为未来几年的挑战。
然而，由于算法的巨大进步，所有问题现在都已解决到最优！
于 2013-01-19T21:01:27.343 回答