旅行推销员的提示

我正在开发一个应用程序，我必须面对旅行推销员的问题。我做了我自己的尝试，但是我得到的时间非常糟糕。我正在寻找一些优化解决方案，但是我没有弄清楚什么。旅行推销员的提示

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

My图表满足所有在TSP图形（无方向性，simetric，CONEX）典型的条件......

感谢

来源

2012-02-27 FrioneL

很难优化你看不到的东西。你目前的算法做什么？ – Nanne 2012-02-27 09:14:30

对不起。我现在的算法是基本的回溯算法，所以我向所有节点跳跃...但是当实际路径比我已经保存的最小路径更重时，我会对其进行预测。 – FrioneL 2012-02-27 09:16:22

你知道距离吗？他们是否遵守三角形不等式（也就是说，从a到c的距离最多是从a到b的距离加上从b到c的距离）？或者他们完全是武断的？ – templatetypedef 2012-02-27 10:21:42

如果你的指标满足三角不等式我可以建议你去寻找christofides算法。它有一个保证在最佳解决方案之内。国际海事组织关于christofides算法的困难部分是完美的匹配。如果你不关心保证，你可以寻找google map tsp solver。它将蚁群优化用于大型路线。如果你想真正快速求解，精度较低，你可以寻找一个怪物曲线，例如希尔伯特曲线或摩尔曲线。

来源

2012-02-27 10:45:25 Bytemain

谢谢。这是一个android gps应用程序，我必须访问一些点...也许我必须使用较少的准确性，因为其他人可能会消耗大量电池... – FrioneL 2012-02-27 11:09:14

旅行推销员的提示

回答

相关问题