我正在开发一个必须面对旅行商问题的应用程序。我做了自己的尝试,但我得到的时间真的很糟糕。我正在搜索一些优化解决方案,但我没有得到任何明确的信息。
开始优化此过程或算法的任何提示?我当前的算法是基本的回溯算法。
我的图满足 TSP 图中的所有典型条件(无方向性、对称性、锥形)...
谢谢
最佳答案
如果您的指标满足三角不等式,我建议您寻找 christofides 算法。它保证在最优解内。 IMO 关于 christofides 算法的困难部分是完美匹配。如果您不关心保证,您可以寻找谷歌地图 tsp 求解器。它对大型路线使用蚁群优化。如果你想要真正快速的求解和较低的精度,你可以寻找一条怪物曲线,例如希尔伯特曲线或摩尔曲线。
关于algorithm - 旅行商小贴士,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9462475/