TSP优化旅游

我写了一个细菌进化算法来解决TSP问题。我选择了XQF131实例（http://www.math.uwaterloo.ca/tsp/vlsi/index.html）来测试我的算法。 Concorde解决了这个问题，最佳旅程是564.但是我计算了所示的最佳旅程长度，它是567,2029。（http://www.math.uwaterloo.ca/tsp/vlsi/xqf131.tour.html）用我的算法，我找到了更好的解决方案566,4142。我的问题是：协和式算法如何工作？它会计算最优解或近似值？TSP优化旅游

感谢您的答案！

来源

2015-04-28 knorbika

您的计算是否正确？如果文学说564，他们不可能犯了一个迄今为止还没有发现的错误。你确定他们的巡演时间比他们声称的要长吗？ – IVlad

我计算了其他实例（ch130）的最佳游览。我的计算值与给定值相等。所以我想我的计算是正确的。 – knorbika

根据wikipedia,this页面以及您发布的网站上的字词，您链接的内容应该是最佳导览，而不是近似值，协和广告应该提供最佳解决方案。

我会检查我的计算结果，以确保报告长度时确实出错。如果是的话，你可以发布这个。

即使没有，你的算法可能只会非常糟糕。如果它比协和式更快，或者至少比其他进化方法更好，那么你大概仍然可以发布一些东西。

干得好，祝你好运！

来源

2015-04-28 09:47:49 IVlad

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

希望您的算法仍能找到最佳解决方案...

来源

2015-04-28 11:18:05 vib

回答

相关问题