求TSP问题的算法

Question

波波老师是我听过的、所有讲算法的（包括其他课），最好的老师，没有之一，非常赞！👍
我的问题是:
1.老师能否给提供一下TSP问题的解决思路，比如:遗传算法等。
2.是否有一些比较好的例子，或者算法库，给推荐一下？最好是JAVA版本的。
谢谢！

Answer 1

liuyubobobo 2020-03-14 07:37:26

实在抱歉，TSP 的解决思路远远超过这个课程的讨论范畴了。

实际上，这个课程在第九章会提及 TSP 问题，看完第九章，或许会让你对 TSP 的思考更深入。

而进一步，TSP 算法本身因为是 NP 难的问题，所以，大部分解决问题的讨论，都是在求近似解。

在这里，推荐一本书，专门从半科普的角度介绍 TSP 相关的解决算法，穿插了对这个算法介绍的历史演进：https://book.douban.com/subject/25713498/

而更进一步，对于这些算法，比如你说的遗传算法，其实都属于人工智能领域讨论的范畴，因为他们都不是确定性的最优算法。注意，是人工智能，不是机器学习。

当下人工智能最权威的教材，应该是这一本：https://book.douban.com/subject/6730363/

第三版貌似没有中文版（也可能是我没搜到），但第二版有中文版。

当然，应该还有一些其他不错的教材，不过我不了解了。

最后，关于遗传算法的算法库，我确实不了解。实际上，近十年，遗传算法是一种“没落的算法”，无论是学术界，还是出版界，遗传算法的相关资料越来越少。这是因为再近十年，遗传算法确实没有大的突破，也没有解决更多的问题。

但遗传算法在十几二十年前，还是非常火的。不过那个时候开源项目还不像现在这么发达，我不确定有没有比较好的开源工具包，你可以自己搜搜看。

加油！：）

• 提问者 春秋文武 #1

  老师，如果最多只有9个节点，能否用某个最短路径算法，直接求出最优解？如果可以，求推荐一种适合的算法，谢谢！

• liuyubobobo 回复 提问者 春秋文武 #2

  穷举就可以。只有 9! 个可能。

• 提问者 春秋文武 #3

  非常感谢！