引言
TSP(Traveling Salesman Problem)即旅行商问题，是数学领域中著名问题之一。这个问题是这样的：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。TSP是一个典型的组合优化问题，且是一个NP完全难题，关于NP的这个概念本文就不做详细介绍了，但简单的说就是：TSP问题目前尚不能找到一个多项式时间复杂度的算法来求解。
问题分析
1.识别本质
这个问题乍一看，有那么一点像“最短路径问题”，然后我们就会自然地想到用Dijkstra算法去求得“从某一个城市出发，到其他所有剩余城市的最短路径”，再或者如果是个真实地图，我们可以用启发式的“A星算法”快速搜索出“从某一个城市到另一个指定城市间的最短路径”。的确，如果是这样真的挺好，但仔细想，这个问题并非单纯这么简单，它还要求去寻找“从某个城市开始，分别经过其它城市一次且仅一次，最后再回到这个出发城市的最短巡回路径”。
2.深入分析
所以该怎么求解呢，我们很容易想到一种类似于穷举的思路：现在假设我们要拜访11个城市，从城市1出发，最后回到城市1。显然，从城市1出来后，我们随即可以选择剩余的10个城市之一进行拜访（这里所有城市都是连通的，总是可达的，而不连通的情况属于个人特殊业务的装饰处理，不是本文考虑范畴），那么很显然这里就有10种选择，以此类推，下一次就有9种选择…总的可选路线数就是：10!。也就是说需要用for循环迭代10!次，才能找出所有的路线，进而筛选出最短的那条来。如果只拜访个10个城市或许还好的话（需要迭代3628800次），那要拜访100个城市（需要迭代9.3326215443944 * 10^157）简直就是计算机的噩梦！更多个城市的话，计算的时间开销可想而知！
更一般地，如果要拜访n+1个城市，总的可选路线数就是n!，进而时间复杂度就是O(n!)，从这里我们同理也可以看出，这个算法的时间复杂度是非多项式的，它的开销大是显而易见的。所以问题的关键不在于寻找两两城市间的最短路径，而在于去寻找一那条最短的巡回路径，换句话说，就是寻找一组拜访城市的先后次序序列 n1n2n3…nini+1…nnn1。
解决方案
这是个NP完全问题，穷举算法的效率又不高，那我们该如何通过一个多项式时间复杂度的算法快速求出这个先后次序呢？目前比较主流的方法是采用一些随机的、启发式的搜索算法，比如遗传算法、蚁群算法、模拟退货算法、粒子群算法等。但这些算法都有一个缺点，就是不一定能求出最优解，只能收敛于（近似逼近）最优解，得到一个次优解，因为他们本质都是随机算法，大多都会以类似“一定概率接受或舍去”的思路去筛选解。各算法的实现思路都有不同，但也或多或少有互相借鉴的地方，有的与随机因子有关、有的与初始状态有关、有的与随机函数有关、有的与选择策略有关……本文主要讲述遗传算法和蚁群算法的求解思路，关于其他更多类型的搜索算法可以在网上查阅，都有很多资料哒。
所以，综合上述分析，我们不难看出TSP问题的求解大概是由两步构成的：
- 计算两两城市间的最短路径：利用类似Dijkstra、Flord、A星的算法求出最短路线。
- 计算最短巡回路径：利用类似遗传算法、蚁群算法的搜索算法求巡回拜访的次序。
关于1中需要说明一点，就是现实生活中我们的地图往往不是一个完全图，而是一个非完全图，甚至有些节点仅仅是道路的分岔口，而不是城市节点。
-
完全图：两两城市间都有直达的路线，这条路线不需要经过中间其他节点；
-
非完全图：偶尔有两个城市间的路线需要经过其他中间节点。
由于本文着重叙述步骤2)，更侧重于搜索算法本身，所以后续文章一律将地图简化为一个完全图。因为就算是非完全图，我们也完全可以事先地、离线地采用步骤1)中的算法求解，得到两两城市间的最短路线，存入数据库，作为持久数据提供给后续在线的、需由用户指定拜访的城市的步骤2)使用，所以简化成完全图是合乎情理的。
结语
本章就先讲到这啦，下一篇会着重讲述“遗传算法”，因为它在算法思想、最优解准确率、适用面等各方面表现都比较好（一方面是我自己的感受，一方面很多论文也这样写到），所以我选择把它的设计与实现过程分享给大家作为参考（如果不嫌弃的话）。
网友评论