旅行商问题的解法

解决旅行商问题的解法有几类。我们首先说说精确解法。精确解法能够保证找到旅行商问题的最优的路线，但是很显然，这些算法都不是多项式时间的。能够解决旅行商问题的一类经典算法，被称为线性规划方法（linear programming）。还记得我们之前提到过解决48个城市的旅行商问题的兰德公司的三位数学家嘛？这三位数学家之一，乔治·丹齐格（George Dantzig），被誉为线性规划之父。

线性规划，不仅可以用来解决旅行商问题，而且是解决一类数学问题的通用方法。数学家们解决一个实际问题的思路，和我们小时候做应用题有点像。对于一个实际问题，数学家们首先会对该问题建模，也就是把该问题抽象成一个数学模型，然后就可以脱离开实际问题，围绕该数学模型，通过数学工具，找到最后问题的答案。丹齐格提出线性规划，针对的是一类特殊的数学模型。这个模型是要找到一组变量的最优值，在满足一些规定条件的约束下，让某一个目标函数取最大值或最小值。特别注意的是，这个约束条件和目标函数，都是关于变量的线性函数。这就是“线性规划”的由来。针对线性规划模型，丹齐格在1947年提出了单纯形法（Simplex algorithm），单纯形法标志着线性规划理论的正式建立和广泛应用。

丹齐格有一个精彩的故事，这个故事后来被好莱坞改编成了电影《心灵捕手》。1939年，年轻的丹齐格在美国加州大学伯克利分校读研究生一年级。有一天，他上课迟到了，这门课的授课教师是杰尔日·内曼（Jerzy Neyman）。内曼教授当时在黑板上写了两道统计学领域著名的未解难题。丹齐格进了教室，看到这两道题目，以为是课后作业，便匆匆忙忙抄下来。过了一段时间，丹齐格把自己的解答交了上去，让内曼大吃一惊。最后这两道“作业题”的解答，成为丹齐格博士毕业论文的主要内容。丹齐格从伯克利毕业时正值二战。二战期间，他在美国空军研究规划问题，也就是如何快速地计算兵力部署、人员训练、后勤补给等方案。战争结束时，丹齐格在美国国防部工作，开始针对如何实现军队规划流程的自动化展开研究，由此在1947年创立了线性规划，并提出了解决线性规划模型的单纯形法。

有这样一个故事。虽然现在看来单纯形法已经成为解决线性规划模型的基础方法，但是回到当年，丹齐格在提出了这个方法之后，自己并不那么自信。1948年，在威斯康星大学的一场会议上，丹齐格公开了通用线性规划模型及其求解所用的单纯形法。但在一大群德高望重的数学家和经济学家面前，他只是个年轻后生，因此内心忐忑不安。在报告后的讨论环节，哈罗德·霍特林（Harold Hotelling），当时已经是数学界成名已久的重量级人物，站起身来，只说了一句话：“可我们都知道世界不是线性的。”面对这么狠的批评，丹齐格一下子无言以对。突然听众中又有一人举起了手，那是著名的冯·诺依曼（John von Neumann）。他说：“主席，主席，如果报告者不介意的话，我愿意替他回答。”丹齐格当然求之不得。冯·诺依曼接着说：“报告者把题目定为‘线性规划’，陈述原理的时候也很谨慎。你的应用要是满足他的原理，那就用他的模型；要是不满足，那就不用呗。”

丹齐格在往后的几十年里，对这个故事津津乐道。据丹齐格在斯坦福大学的同事表示，他在自己办公室外面挂了一幅漫画，配图文字写道：“幸福就是假设世界是线性的。”线性规划在工业界用途极广，令人惊叹，你说得上来的任何部门几乎都有它的用武之地。显然，通过线性规划安排生产，每天能节省数不清的自然资源。线性规划还能省钱，《纽约时报》就曾专门针对线性规划发表过文章，“解决工业上的线性规划问题，是涉及每年上百亿美元的大事业”。回到旅行商问题，这个问题是线性规划中的一个特殊分支：整数规划。因此解决整数规划的方法基本上都可以用于解决旅行商问题。如何找到效率更高的旅行商问题的算法，是众多研究者一个明确的目标。在这条“没有最快，只有更快”的道路上，包括本书的作者在内的科学家开始了竞赛。从动态规划算法，到割平面法、分支定界法，各种算法被不断提出。尽管我们知道，这些算法都不是多项式时间算法，但是在很多问题中，它们已经表现得很好，因此在各个领域中都得到了广泛地应用。

除了精确解法之外，数学家们还有另外一种思路：抛开必须找到绝对最优解的念头，转而关注如何尽快求一个还不错的解。放弃最优解带来的好处是可以让计算速度大大加快，让多项式时间的算法成为可能。在这条道路上，最早期的算法，叫做启发式算法。所谓的启发式，是靠人类的经验总结出来算法的规则。例如，在从头开始构建旅行商的路线时，最容易想到的方法就是每次都在没有到过的城市中选择最近的一个。这种算法称为最近邻算法（nearest-neighbor algorithm），这个算法得到的路线虽然通常不是最短的，但是速度非常快。除了启发式算法之外，还有一类算法，叫做元启发式算法（metaheuristic），即用来设计启发式算法的启发式算法。

元启发式算法的代表包括爬山法、模拟退火算法、遗传算法、蚁群算法等。在这里我们来介绍一下遗传算法。遗传算法是从生物角度出发，把路线当成能够逐渐变异和进化的生命有机体。遗传算法解决旅行商问题的思路大致如下。首先形成路线的初始“种群”，可以通过反复从随机城市出发使用最近邻算法获取大量的可能路线。然后在种群中选取若干对比较好的路线，让它们“交配”“变异”（即综合这些路线），得到一批子代路线，再从中选出比较好的子代路线中重复之前的步骤，最后最优秀的路线最终将脱颖而出，成为唯一的生存赢家。