TSP最优巡游

Question

我写了一个细菌进化算法来解决TSP问题。我选择XQF131实例(http://www.math.uwaterloo.ca/tsp/vlsi/index.html)来测试我的算法。这个问题是用协和算法解决的，最优路径是564。但我计算了显示的最优线路长度，它是567,2029。(http://www.math.uwaterloo.ca/tsp/vlsi/xqf131.tour.html)使用我的算法，我找到了更好的解决方案566,4142。我的问题是:协和算法是如何工作的?它计算最优解或近似值？

谢谢你的回答！

Answer 1

你确定你计算的距离正确吗？看起来你应该得到一个整数距离。实际上，从你引用的网站上看，“在这些例子中，城市之间的旅行费用是由四舍五入到最接近的整数的欧几里德距离来确定的”。

希望你的算法还能找到一个最优解。

Answer 2

根据wikipedia，this页面和你发布的网站上的措辞，你链接的应该是最优浏览，而不是近似值，协和应该给出最优解决方案。

我会检查我的计算，以确保他们在报告长度时确实犯了错误。如果是，你可以发布这篇文章。

即使不是这样，你的算法可能也只是稍微差一点而已。如果它比协和式方法更快，或者至少比其他进化方法更好，你可能仍然可以发布一些东西。

干得好，祝你好运！