在过去的几天里，我注意到一些web 网站展示了使用遗传算法解决TSP问题。

哪种方法能在TSP问题中产生更短的路径：最近邻算法还是遗传算法？

回答：

由于这两种技术都不能保证找到最优解，所以结果会因情况而异。 运气好的话，任何一种技术都可能胜过另一种。这两种技术各有优缺点。

最近邻算法：+速度快，+简单，-通常不是最优解

遗传算法：-速度较慢，-更复杂，+随着时间的推移，解会趋向于最优

最大的区别在于，像模拟退火和遗传算法这样的随机算法可能会随着时间的推移而不断改进——你让它们运行的时间越长，获得最优解的机会就越多（尽管没有保证）。

由于最近邻算法速度很快，没有什么能阻止你结合使用这两种技术。运行最近邻算法来找到一个可能比随机解更好的起始解。然后，将该解输入到你的遗传算法中，并让它运行你认为合适的时间。

如果你对最优解感兴趣，可以看看Lin-Kernighan启发式算法和线性规划。 这两种方法都被用来找到大型旅行路线的最优解，包括这个解，它解决了85,900个城市的旅行路线，以及24,978个城市的瑞典旅行路线。

佐治亚理工学院的TSP网站是一个很好的资源。