algorithm - 旅行推销员小贴士

Question

我正在开发一个应用程序，在该应用程序中我必须面对旅行推销员问题。我做了自己的尝试，但我得到的时间真的很糟糕。我正在搜索一些优化解决方案，但我没有得到任何明确的信息。

开始优化此过程或算法的任何提示？我目前的算法是基本的回溯算法。

我的图表满足 TSP 图表中的所有典型条件（无方向、等距、圆锥）...

谢谢

Answer 1

如果您的度量满足三角不等式，我可以建议您寻找 christofides 算法。它有保证在最佳解决方案之内。IMO christofides 算法的难点在于完美匹配。如果您不关心保证，您可以寻找 google map tsp 求解器。它对大型路线使用蚁群优化。如果您想要真正快速求解并降低精度，您可以寻找一条怪物曲线，例如希尔伯特曲线或摩尔曲线。