迷茫的旅行商——1.1　环游美国之旅

它产生于三个人求解一道经典数学问题的研究工作。这个历史悠久的问题叫做“旅行商问题”，无论靠人工计算还是借助最快的计算机都一直无法解决。——IBM 新闻稿，1964 年① 1962 年春天，宝洁公司发起了一场广告宣传活动，在应用数学家中引起了不小的反响。活动的重头戏是一项竞赛，奖金高达1 万美元，在当时足以买下一座房子。参赛规则如下：假设Toody 和Muldoon 打算开车环游美国，地图上用点标出的33 个地点都要游览，并且要走满足条件的路线中最短的一条。请你为他们规划一条旅行路线，以伊利诺伊州的芝加哥市为旅途的起点和终点，依次用线连接各地点，并使得总里程最短。 Toody 和Muldoon 是当时一部美国热门电视剧②中的人物。他们是驾驶54 号车的两名警官。这项游遍33 座城市的任务是旅行商问题（traveling salesman problem，TSP）的一个具体例子。TSP 的一般形式为：给定一组城市及它们两两之间的距离，求经过每座城市并返回出发地的最短路线。 求解一般形式的TSP，是容易，还是困难，抑或无法求解？对此，最简单的回答就是谁也不知道。这道计算数学领域的知名难题之所以神秘莫测而又引人入胜，正是因为这一点。为此陷入困境的也不只是一名纠结的旅行商而已，因为在计算复杂度的本质与人类认识的可能限度这一高深论题中，TSP 正是讨论的焦点。若你已跃跃欲试，那么只需要一支削尖的铅笔和一张干净的草稿纸，就可以向旅行商伸出援手。或许我们对于整个世界的认识也会因为你而发生飞跃。 ①摘自IBM 公司发布于1964 年1 月2 日的新闻稿。“它”表示一个新的计算机程序， 能够解决小规模的旅行商问题， 由Michael Held、Richard Karp 和Richard Shareshian 三人编写完成。 ②即1961 ～ 1963 年播出的美国电视喜剧Car 54, Where Are You。 ——译者注 1.1　环游美国之旅 TSP 虽然公认棘手，但从某一方面来看却相当容易：经过给定一组城市的全部可能路线总数是有限的，因此1962 年的某位数学家只需检验每条可能的路线，将最短的一条记录下来寄给宝洁公司，便可坐等一万美元支票寄到家中。这个解题策略堪称简单而完美，但有一点潜在的困难。由于路线总数极其庞大，根本不可能逐一检验。 1930 年，奥地利数学家、经济学家Karl Menger 已注意到TSP 存在这种困难。最初正是因为他的工作，数学界才开始关注TSP 这道难题。他写道：“该问题当然可以在有限多次试验内解决，但是尚未发现能够给出比给定点的全排列数更低的试验次数的解法。”①一条路线可以通过到达各城市的顺序来唯一确定。我们依次用字母A ～ Z 及数字1 ～ 7表示Toody 和Muldoon 的33 个目的地，即A 代表芝加哥市，B 代表维奇托市，以此类推。如此，一条可能的路线便可以记作 ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567或以上符号排成其他任一序列的形式。每一个这样的序列都是这33 个符号的一个排列（permutation）。 由于旅行的起点和终点相同，每个排列对应的路线实际都是一条环形路线，在这条环形路线上选择另外一座城市作为起点就能得到另一个不同的序列，因此同一条环形路线对应33 个不同的线性排列。为避免重复计数，不妨固定城市A 为每条路线的起点，则第二座城市有32 种可能选择，第三座城市有31 种可能选择，以此类推。最后，可以得到环形路线的总数为32×31×30×…×3×2×1。这个数字记作32!，读作32 的阶乘，表示32 个不同物体总共有多少种排列情况，也称为全排列数。 在“54 号车”竞赛题中，注意到从芝加哥到维奇托的距离等于从维奇托到芝加哥的距离，并且对于任意两座城市来说都是如此，所以我们可以减少一部分工作量。根据对称性，对于同一条路线，总路程与旅行方向无关。因此，字符串 ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567和它的逆序字符串 7654321ZYXWVUTSRQPONMLKJIHGFEDCBA虽然写法不同，但对应同一条环形路线。 这样一来，问题的可能路线数便可以减半，只剩下32!/2 种排列等待我们检验。先别急着拿笔，请注意，这个数字也就意味着我们要考察 131 565 418 466 846 765 083 609 006 080 000 000条不同的路线。 ① Menger (1931). 现在，我们当然会把检验所有路线的任务都交给计算机完成。那么，让我们选一台大家伙——IBM“走鹊”（Roadrunner）超级计算机集群。它属于美国能源部，造价1.33 亿美元，含有129 600 个计算核心，运算速度可达每秒1457 万亿次，高居2009 年全球最快超级计算机五百强榜单首位①。假设检验每条路线只需要一次算术运算，那么用这台超级计算机解决含有33 座城市的TSP，估计需要超过28 000 亿年②，耗时漫长得可怕。要知道，宇宙从诞生至今也不过140 亿年而已。难怪Menger 对于TSP 的暴力枚举解法并不满意。 上述估算简短而引人思考，但是请务必牢记，Menger 只是说更快的解法尚未发现，并没有否定它们存在的可能性。John Little 等人③在宝洁公司的赛后评论里对此总结得很到位：“有些人可能学过太多知识，所以写信告诉宝洁公司该问题不可解。这种想法是对目前科技水平的一种很有意思的误解。”在评论中，Little 等人还描述了在TSP 的解法研究方面取得的突破。不过计算机代码改进得不够，对于33 座城市的情形还无法真正解出答案。看起来，当时似乎全美国没有一个人有能力为Toody 和Muldoon 设计一条路线，并确保它就是满足条件的路线中最短的一条。 事实并非如此。尽管这道题确实是块难啃的骨头，但是若我们退回到1954 年，就会发现，那时已经有一组人有这个能力。他们几乎一定能找到所求的最短路线，还能写出保证书一并寄去参赛。因为他们此前已经攻克了一道规模更大的类似问题，题目条件是环游美国，游览首府华盛顿和另外48 座城市（分别属于当时美国的48 个州）。20 世纪30年代中期以来，这道难题在数学界内广为流传。《新闻周刊》报道了它的解决。④ ①该榜单发布于2009 年6 月。但是在2012 年11 月的最新榜单上，Roadrunner 已经退至第22 位，而榜首的超级计算机Titan 每秒运算速度已达到27 112 万亿次。 ——译者注 ②原文为大约28 万亿年（28 trillion），但实际计算结果应为28 600 亿年（ 2.86 trillion）。 ——译者注 ③Little, J. D. C., et al. 1963. Operations Research 11, 972–989. ④Newsweek, July 26, 1954, page 74.图1-2　推销员之喜，《新闻周刊》，1954 年7 月26 日第74 页 给定一组城市，有一名旅行商要从指定的某座城市出发，经过其他所有城市，最终返回出发地。为他寻找最短路线的问题，并不只是一道晚饭后的智力题。数年来，它不但难倒了规划运货路线和商旅路线的商人，而且让数学家也束手无策。举个例子，假如一个推销员要拜访50 座城市，那他可选的路线就有1062 种，这个数字是1 后面连着62 个0。目前的任何一台电子计算机都无法在这么多路线中理清头绪，选出最短的那条。 在美国加利福尼亚州的兰德公司，三位数学家终于提供了一种解法。线性规划方法是最近用来解决生产计划管理问题的一种新的数学方法。他们巧妙地运用了这一方法，只用了几星期时间就通过“手工”计算得到了周游华盛顿和其他48 座城市的最短路线，其长度为12 345 英里（约19 867 千米）。他们计算使用的各城市相距里程数据取自兰德麦克纳利道路地图（Rand McNally road-map）。 这三位数学家是George Dantzig、Ray Fulkerson 和Selmer Johnson。他们所在的研究中心实力雄厚，影响力极大，专门研究数学规划这一新兴学科。该中心位于加利福尼亚州圣莫尼卡市，属于兰德公司。 在他们给出的保证书里，有一些运算过程完成得很漂亮，将在本书后面的章节进行讨论。现在，最好暂时把这份保证书理解为数学证明，和我们在几何课上学过的那种证明一样。首先，Dantzig 等人证明了，在这道环游美国48 州问题中，周游49 座城市的路线长度不可能短于123 45 英里；然后，他们又提供了一条路线，其长度刚好等于12 345英里。论证与构造相结合，便彻底解决了这道题。 虽然他们没有参加那场奖金高达一万美元的广告竞赛，但是我们可以确定，按照他们的思路，用计算机解决33 座城市的TSP 已变得轻而易举。图1-3 中画出了Toody 和Muldoon 的最短路线。回到1962 年，尽管没有人能肯定这就是正确答案，然而确实有一些参赛者提交了这条路线，因此暂时并列第一，其中包括两位数学家Robert Karg 和GeraldThompson。他们两人发明了一种启发式试探策略①，从而找到了最短的路线。这个故事的结局很美好，至少对数学界来说是如此，因为决胜题要求写一篇短文赞美宝洁公司的某项产品，而Gerald Thompson 凭借一篇赞颂肥皂的散文脱颖而出，最终赢得了大奖。 ① Karg, R. L., G. L. Thompson. 1964. Management Science 10, 225–248.