algorithm - 大量顶点的旅行商问题

Question

我需要以良好的准确性和足够的时间（如 1-2 天）解决大量顶点（30-100）的 TSP。我的图可以包含不对称边（g[i][j] 不等于 g[j][i]）。

我尝试了贪婪，很少（也许是我的坏事，但这显示出比贪婪更糟糕的结果），简单的遗传算法（几乎比贪婪好），动态 O(2^n*n) （内存快耗尽）。

标签： algorithmtraveling-salesman

Answer 1

嗯，30-100 并不是很多顶点。你错过了一些零吗？或者您正面临一些特殊的难以解决的案例，例如来自 TSPLIB 的 p43？

无论如何，如果您正在寻找一个好的启发式算法，我曾经使用 Ant Colony Optimization for Asymmetric TSP。它很容易实现并且提供了相当好的性能。

你可以看看我的旧实现：https ://github.com/aligusnet/optimer/tree/master/src/heuristics/aco