迷茫的旅行商：一个无处不在的计算机算法问题(txt+pdf+epub+mobi电子书下载)

作者：William J.Cook

出版社：人民邮电出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

迷茫的旅行商：一个无处不在的计算机算法问题试读：

在Geoff Mack的歌曲《我的足迹遍布四方》（I've Been Everywhere。）中，主人公曾经去过以下城市：里诺、芝加哥、法戈、布法罗、多伦多、温斯洛、萨拉索塔、威奇托、塔尔萨、渥太华、俄克拉荷马、坦帕、巴拿马、马特瓦、拉帕洛马、班戈、巴尔的摩、萨尔瓦多、阿马里洛、托卡皮罗、巴兰基亚、帕迪亚。

1988年2月的一天晚上，我和朋友Vašek Chvátal下定决心追随数学大师的脚步，试着寻找周游多个目的地的最短路线。次日，我们约在曼哈顿下城的一家计算机销售商店碰头，那家店名为Tri-State Camera。店里的技术人员一听说我们是数学家，还想买一台速度快的计算机，便盯着我们的眼睛，告诫道：“你们俩不是想解决那道旅行商问题吧？是不是啊？”他颇有先见之明。在之后的20年里，我们把大部分时光都用在了求解这道题上。期间，有很多台计算机在我们手下逐渐停止运转，就像最初的这一台一样。

这道“臭名昭著”的题是这样的：给定一系列城市，试求出经过所有城市并回到出发地的最短路线。以Geoff Mack歌里唱到的那位旅行者为例，经过那22座城市的路线总共有51 090 942 171 709 440 000条。可以想到，逐一检验所有路线就是一种解题思路。在这样的计算量面前，速度最快的超级计算机也要“挽起袖子”准备辛苦干上一整天。若有足够的耐心，便有希望找到最短路线。然而，假如城市数目变成100座，那么就算征用地球上所有的计算机，也不可能通过逐一检验所有路线找出最短的一条。

最后这句评论针对的是枚举路线的做法，但如果要说旅行商问题确实难解，这理由绝对不足以让人信服。有一些类似的问题其实很容易解决，而它们可供枚举的情形比旅行商的路线还要多。旅行商问题的与众不同之处在于，尽管世界各地的一流应用数学家已经研究了几十年，但人们如今依然不知道，对于一般性的旅行商问题，如何才能得出远远优于简单暴力枚举检验的通用解法。很有可能根本就没有一种高效解法能保证解决该问题的所有具体题目。高效解法是否存在？这是一道严肃的数学问题，涉及可行计算的界限，因此触及复杂性理论的核心。对于想努力求出通用解法的勇士，克雷数学研究所准备了一份大奖——任何人只要能够提出高效解法或者证明不存在高效解法，便会得到100万美元的奖金。

在旅行商问题研究领域，克雷大奖关注的复杂性问题就像圣杯一样。我们也许连解法的影子都看不到，但这并不意味着数学家至今的研究都一无所获。事实上，这道问题带来了许多美妙而深刻的结论和猜想。在精确计算领域，一道包含85 900座城市的难题于2006年宣告破解。该题的最优路线经过计算脱颖而出，若是对数目异常庞大的所有路线逐一检验，需要用顶尖计算机工作站连续运转136年。在实际应用领域，人们使用该问题的解法，每天可以对大量应用题目计算出最优路线或近优路线。

旅行商问题之所以具有永恒的力量，原因之一在于，它是应用数学领域以及运筹学与数学规划方向的驱动力，对新发现起到了有目共睹的带动作用。而且，更多的发现可能就在前方不远处。本书的一大目标就是鼓励有意求解这道难题的读者，希望你们能追随自己的见解和思路。

在写作本书的过程中，我有幸得到了许多人的帮助和支持。首先，我要感谢同事David Applegate、Robert Bixby和Vašek Chvátal。感谢我们在二十多年的岁月里，分享欢乐，共同工作，为揭开旅行商问题的部分奥秘而努力。

我还要感谢Michel Balinsky、Mark Baruch、Robert Bland、Sylvia Boyd、William Cunningham、Michel Goemans、Timothy Gowers、Nick Harvey、Keld Helsgaun、Alan Hoffman、David Johnson、Richard Karp、Mitchel Keller、Anton Kleywegt、Bernhard Korte、Harold Kuhn、Jan Karel Lenstra、George Nemhauser、Gary Parker、William Pulleyblank、Andre Rohe、Lex Schrijver、Bruce Shepherd、Stan Wagon、David Shmoys、Gerhard Woeginger和Phil Wolfe。感谢他们对旅行商问题及其历史的讨论。

书中使用的图片和史料来自Hernan Abeledo、Leonard Adleman、David Applegate、Masashi Aono、Jessie Brainerd、Robert Bixby、Adrian Bondy、Robert Bosch、John Bartholdi、Nicos Christofides、Sharlee Climer、James Dalgety、Todd Eckdahl、Daniel Espinoza、Greg Fasshauer、Lisa Fleischer、Philip Galanter、Brett Gibson、Marcos Goycoolea、Martin Grötschel、Merle Fulkerson Guthrie、Nick Harvey、Keld Helsgaun、Olaf Holland、Thomas Isrealsen、David Johnson、Michael Jünger、Brian Kernighan、Bärbel Klaaßen、Bernhard Korte、Drew Krause、Harold Kuhn、Pamela Walker Laird、Ailsa Land、Julian Lethbridge、Adam Letchford、Panagiotis Miliotis、J. Eric Morales、Randall Munroe、Yuichi Nagata、Denis Naddef、Jaroslav Nešetřil、Manfred Padberg、Elias Pampalk、Rochelle Pluth、Ina Prinz、William Pulleyblank、Gerhard Reinelt、Giovanni Rinaldi、Ron Schreck、Éva Tardos、Mukund Thapa、Michael Trick、Marc Uetz、Yushi Uno、Günter Wallner、Jan Wiener和Uwe Zimmermann。感谢他们所有人的热情帮助。

两所院校为我提供了极好的写作环境，分别是佐治亚理工大学的米尔顿·斯图尔特工业与系统工程学院和普林斯顿大学的运筹学与金融工程系。我对旅行商问题的研究工作得到了美国国家科学基金会（CMMI-0726370）和美国海军研究办公室（N0014-09-1-0048）的资助，也收到了A. Russel Chandler III的慷慨捐赠。感谢他们一直以来的支持。

最后，我要感谢我的家人Monika、Benny和Linda。感谢他们多年来耐心听我讲述旅行商的故事。第1章难题大挑战它产生于三个人求解一道经典数学问题的研究工作。这个历史悠久的问题叫做“旅行商问题”，无论靠人工计算还是借助最快的计算机都一直无法解决。1——IBM新闻稿，1964年1. 摘自IBM公司发布于1964年1月2日的新闻稿。“它”表示一个新的计算机程序，能够解决小规模的旅行商问题，由Michael Held、Richard Karp和Richard Shareshian三人编写完成。

1962年春天，宝洁公司发起了一场广告宣传活动，在应用数学家中引起了不小的反响。活动的重头戏是一项竞赛，奖金高达1万美元，在当时足以买下一座房子。参赛规则如下：假设Toody和Muldoon打算开车环游美国，地图上用点标出的33个地点都要游览，并且要走满足条件的路线中最短的一条。请你为他们规划一条旅行路线，以伊利诺伊州的芝加哥市为旅途的起点和终点，依次用线连接各地点，并使得总里程最短。图1-1　“54号车”竞赛题。（宝洁公司供图）2

Toody和Muldoon是当时一部美国热门电视剧中的人物。他们是驾驶54号车的两名警官。这项游遍33座城市的任务是旅行商问题。（traveling salesman problem，简称TSP。）的一个具体例子。TSP的一般形式为：给定一组城市及它们两两之间的距离，求经过每座城市并返回出发地的最短路线。2. 即1961～1963年播出的美国电视喜剧Car 54, Where Are You。。——译者注

求解一般形式的TSP，是容易，还是困难，抑或无法求解？对此，最简单的回答就是谁也不知道。这道计算数学领域的知名难题之所以神秘莫测而又引人入胜，正是因为这一点。为此陷入困境的也不只是一名纠结的旅行商而已，因为在计算复杂度的本质与人类认识的可能限度这一高深论题中，TSP正是讨论的焦点。

若你已跃跃欲试，那么只需要一支削尖的铅笔和一张干净的草稿纸，就可以向旅行商伸出援手。或许我们对于整个世界的认识也会因为你而发生飞跃。1.1 环游美国之旅

TSP虽然公认棘手，但从某一方面来看却相当容易：经过给定一组城市的全部可能路线总数是有限的，因此1962年的某位数学家只需检验每条可能的路线，将最短的一条记录下来寄给宝洁公司，便可坐等一万美元支票寄到家中。这个解题策略堪称简单而完美，但有一点潜在的困难。由于路线总数极其庞大，根本不可能逐一检验。

1930年，奥地利数学家、经济学家Karl Menger已注意到TSP存在这种困难。最初正是因为他的工作，数学界才开始关注TSP这道难题。他写道：“该问题当然可以在有限多次试验内解决，但是尚未发1现能够给出比给定点的全排列数更低的试验次数的解法。”一条路线可以通过到达各城市的顺序来唯一确定。我们依次用字母A～Z及数字1～7表示Toody和Muldoon的33个目的地，即A代表芝加哥市，B代表维奇托市，以此类推。如此，一条可能的路线便可以记作ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567

或以上符号排成其他任一序列的形式。每一个这样的序列都是这33个符号的一个排列。（permutation）。1. Menger (1931).

由于旅行的起点和终点相同，每个排列对应的路线实际都是一条环形路线，在这条环形路线上选择另外一座城市作为起点就能得到另一个不同的序列，因此同一条环形路线对应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

条不同的路线。

现在，我们当然会把检验所有路线的任务都交给计算机完成。那么，让我们选一台大家伙——IBM“走鹊”（Roadrunner）超级计算机集群。它属于美国能源部，造价1.33亿美元，含有129 600个计算核心，运算速度可达每秒1457万亿次，高居2009年全球最快超级计2算机五百强榜单首位。假设检验每条路线只需要一次算术运算，那么用这台超级计算机解决含有33座城市的TSP，估计需要超过28 000

3亿年，耗时漫长得可怕。要知道，宇宙从诞生至今也不过140亿年而已。难怪Menger对于TSP的暴力枚举解法并不满意。2. 该榜单发布于2009年6月。但是在2012年11月的最新榜单上，Roadrunner已经退至第22位，而榜首的超级计算机Titan每秒运算速度已达到27 112万亿次。——译者注3. 原文为大约28万亿年（28 trillion），但实际计算结果应为28 600亿年（2.86 trillion）。——译者注

上述估算简短而引人思考，但是请务必牢记，Menger只是说更4快的解法尚未发现，并没有否定它们存在的可能性。John Little等人在宝洁公司的赛后评论里对此总结得很到位：“有些人可能学过太多知识，所以写信告诉宝洁公司该问题不可解。这种想法是对目前科技水平的一种很有意思的误解。”在评论中，Little等人还描述了在TSP的解法研究方面取得的突破。不过计算机代码改进得不够，对于33座城市的情形还无法真正解出答案。看起来，当时似乎全美国没有一个人有能力为Toody和Muldoon设计一条路线，并确保它就是满足条件的路线中最短的一条。4. Little, J. D. C., et al. 1963. Operations Research 11, 972–989.

事实并非如此。尽管这道题确实是块难啃的骨头，但是若我们退回到1954年，就会发现，那时已经有一组人有这个能力。他们几乎一定能找到所求的最短路线，还能写出保证书一并寄去参赛。因为他们此前已经攻克了一道规模更大的类似问题，题目条件是环游美国，游览首府华盛顿和另外48座城市（分别属于当时美国的48个州）。20世纪30年代中期以来，这道难题在数学界内广为流传。《新闻周刊》5报道了它的解决。5. Newsweek。, July 26, 1954, page 74.图1-2　推销员之喜，《新闻周刊》，1954年7月26日第74页。给定一组城市，有一名旅行商要从指定的某座城市出发，经过其他所有城市，最终返回出发地。为他寻找最短路线的问题，并不只是一道晚饭后的智力题。数年来，它不但难倒了规划运货路线和商旅路线的商人，而且让数学家也束手无策。举个例子，假如一个推销员要拜访50座城62市，那他可选的路线就有10种，这个数字是1后面连着62个0。目前的任何一台电子计算机都无法在这么多路线中理清头绪，选出最短的那条。在美国加利福尼亚州的兰德公司，三位数学家终于提供了一种解法。线性规划方法是最近用来解决生产计划管理问题的一种新的数学方法。他们巧妙地运用了这一方法，只用了几星期时间就通过“手工”计算得到了周游华盛顿和其他48座城市的最短路线，其长度为12 345英里（约19 867千米）。他们计算使用的各城市相距里程数据取自兰德麦克纳利道路地图（Rand McNally road-map）。

这三位数学家是George Dantzig、Ray Fulkerson和Selmer Johnson。他们所在的研究中心实力雄厚，影响力极大，专门研究数学规划这一新兴学科。该中心位于加利福尼亚州圣莫尼卡市，属于兰德公司。

在他们给出的保证书里，有一些运算过程完成得很漂亮，将在本书后面的章节进行讨论。现在，最好暂时把这份保证书理解为数学证明，和我们在几何课上学过的那种证明一样。首先，Dantzig等人证明了，在这道环游美国48州问题中，周游49座城市的路线长度不可能短于12 345英里；然后，他们又提供了一条路线，其长度刚好等于12 345英里。论证与构造相结合，便彻底解决了这道题。

虽然他们没有参加那场奖金高达一万美元的广告竞赛，但是我们可以确定，按照他们的思路，用计算机解决33座城市的TSP已变得轻而易举。图1-3中画出了Toody和Muldoon的最短路线。回到1962年，尽管没有人能肯定这就是正确答案，然而确实有一些参赛者提交了这条路线，因此暂时并列第一，其中包括两位数学家Robert Karg和6Gerald Thompson。他们两人发明了一种启发式试探策略，从而找到了最短的路线。这个故事的结局很美好，至少对数学界来说是如此，因为决胜题要求写一篇短文赞美宝洁公司的某项产品，而Gerald Thompson凭借一篇赞颂肥皂的散文脱颖而出，最终赢得了大奖。6. Karg, R. L., G. L. Thompson. 1964. Management Science 10, 225–248.图1-3　“54号车”竞赛题的答案。1.2 不可能的任务吗

兰德小组的研究工作解决了环游美国48州的难题，却没有彻底解决TSP。他们取得了一次巨大的成功，并不意味着就能搞定规模更大的题目。事实上，如果拉斯维加斯赌场把TSP的最终结果作为一项赌博项目，那么在数学家看来，把赌注押在“TSP永远无法彻底解决”上会有更大的胜算。对此，必须明确一点：我们要找的所谓解法（solution），实际上是算法。（algorithm），也就是要求对于任何一道实例，只要按照算法一步一步计算，一定能求出最优路线。单单找到周游美国或者周游其他某国的最优路线是不够的。

所以，为一般形式的TSP找到通用解法的难度可想而知。1Charles Stross在科幻小说《抗体》（Antibodies。）中就写到了这一点。在这篇小说中，有人找到了旅行商问题的高效算法，结果就像世界末日一样，种种事件接踵而来。我们只能希望，TSP真相大白的那一刻不会宣告所谓的世界末日。无论如何，这件事一旦发生，必然会让世界天翻地覆。为什么？让我们先看看前人是怎么说的。1. 英文版见G. Dozois编辑的“The Year's Best Science Fiction”（2000年度最佳科幻小说），2001年由St. Martin's Press出版。中文版刊登于《科幻世界》2010年7月刊第54~64页。——译者注要想成功解决该问题，很可能需要另辟蹊径，使用前所未有的新方法。事实上，该问题的通用解法很可能压根不存在，若能证实这个结论也是很有价值的。2——Merrill Flood，1956年2. Flood, M. M. 1956. Operations Research 4, 61–75.依我猜想，旅行商问题没有好的算法。3——Jack Edmonds，1967年3. Edmonds, J. 1967. J. Res. Nat. Bur. Stand. Sec. B 71, 233–240.我们在本文中给出了一些定理。它们有力地暗示（尽管不足以证明）：该问题像许多别的问题一样，也将是一道永恒的难题。4——Richard Karp，1972年4. Karp (1972).

以上评论者是旅行商问题研究领域的三位大师。Merrill Flood在20世纪40年代呼吁人们支持研究TSP，并使它成为基础性研究课题，在这方面，他的贡献无人能及。1956年，他在讨论该问题的研究现状时，首次提出高效解法根本不存在的可能性。10年后，Jack Edmonds重申这一看法，当时他和别人为通用解法是否存在而打赌，而他认为不存在。谈起自己这样想的根据，他谦虚地说：“我对数学提出任何猜想，都是基于如下两条理由：第一，数学上有合理的可能性；第二，我并不确定。”不过，这只是他的玩笑话，因为对于20世纪的数学，他学识渊博，思考深邃，在世界上是数一数二的，所以他如此下注必然有他的道理。5年后，伟大的计算机科学家Richard Karp终于揭晓了这个赌的本质。他在一篇文章中把TSP和许多其他计算问题联系到了一起。具体理论细节留到第9章再讲，现在只稍做解释。相信这一节内容足以让读者理解，为何在小说《抗体》中，宣告发现TSP的高速算法会让每个人都不寒而栗。1.2.1 好算法，坏算法

Edmonds在写下“好的算法”一词的时候，对于“好”的理解和我们一样：如果一个算法能够在我们满意的时间内解决问题，那么它就是好的。然而，他必须把“好”定义为正式的概念，才能让它有合理的数学意义。显然，我们不能指望TSP的每道题目都能在固定时间（比如一分钟）内通过人力或计算机解决，至少在城市数量增加时应该允许求解时间也相应增加。关键是要确定，时间按照什么速度增长1才能得到我们的认可。1. 可能有人会说，考虑问题规模时，城市距离数据的精度也是影响因素。假如我们读取A城市和B城市之间的距离（或者旅行费用）时，需要读取几百万位数字，那么确实有影响。但是，即使每段路程都是小于常数K的整数，TSP依然相当困难，而这种复杂度是最重要的。我们关心的是TSP的本质复杂度，因此完全可以放心地忽略数据精度这样的细节。图1-4　Jack Edmonds。（2009年摄，Marc Uetz提供）9

表1-1 每秒运算10次的计算机在不同条件下的运行时间。复杂度n=10n=25n=50n=10030.000001秒0.00002秒0.0001秒0.001秒nn0.000001秒0.03秒13天40万亿年2

我们用字母n。表示问题的规模，在TSP中就是城市的数量。由于读取目标城市列表所需的时间与n。成正比，所以可能有些强势的老板就只给我们正比于n。的解题时限。这样的人看问题过于乐观了。就连Edmonds本人都允许运行时间以更快的速度增加，用更明智的方k式划分算法的好坏。好的算法。能保证在至多正比于n。的时间内完成运算，其中，指数k。可以是任意值，比如取2、3或者更大的数，但必须是固定值，不能随着n。的增加而增加。于是，算法的运行时n3n。间若是以n。的速度增加，那么它就是好的，若是以n。或2的速度增加，就是坏的。表1-1列出了每秒运算十亿次的计算机在n。取不同值时相应的运算时间，以便让你感受到好坏之间的差距。可以看到，n。如果n。=10，坏算法也够用了；但如果n。取值达到100左右，2阶的算法会算个没完没了，你肯定不希望出现这种结果。

Edmonds对“好”的正式定义未必总是符合我们的直觉。在一道1000100座城市的TSP面前，我们不会对需要执行n。步的算法感兴趣。尽管如此，Edmonds的想法还是彻底改变了计算数学。算法可以明确地分成“好”与“坏”两种类别，从此数学家有了确定的目标，对计算问题的兴趣也更加浓厚。在应用方面，一旦有人证明某道问题存在好的算法，研究人员便纷纷全力以赴，竞相寻找更低的指数k。，通常234能把运行时间界限降低到正比于n。、n。或n。的程度，最终的计算机代码足以处理规模很大的问题。图1-5　旅行商问题。（xkcd.com的Randall Munroe供图）

我要告诉TSP的爱好者一个遗憾的消息——TSP的好算法至今不为人知。迄今为止得到的最好结果发现于1962年，算法的运行时间n2。正比于n。2。尽管这不是个好的算法，但是与经过n。点的路线总数(n。-1)!/2相比，运算时间增长得已经相当慢了，或许Menger的好奇心可以由此得到满足。1.2.2 复杂度类P与NP

按照Edmonds划分算法的方式，计算问题也可同样分为两类，一类存在好的算法，另一类则不存在。我们喜欢第一类问题，将它们统称为P类。。

为什么用字母P，而不用“G”（good）？这是因为研究人员认为“good”这个词带有主观情感，不太喜欢这种用法，所以多项式时间算法。（polynomial-time algorithm）就成为了标准术语。就是多项式。（polynomial）。

P类问题的定义清晰明确，但是，有时却很难判断某道给定的问题是不是这一类“好的问题”。没准TSP也属于P类，只是我们还没找到好的算法来证明这一点而已。至少，我们看到最优路线时总能判断出来，这为我们保留了一线希望。事实上，假如我们面临的挑战是要找一条短于100英里的路线，那么，只要别人给我们一个答案，我们就可以轻松验证它的长度是否满足要求。由于这种性质，我们把TSP归为另一类问题，称为NP类。。对于此类问题，我们总可以在多项式时间内验证某一个解是否正确。这里，两个字母NP来自非确定性多项式。（non-deterministic polynomial）。“NP类”这个奇特的名称暂且抛开不提，这类问题本身是很自然的：我们提出计算需求时，理应有办法验证结果是否满足要求。1.2.3 终极问题

P类和NP类有没有可能只是同一类问题的两个不同名字？有可能。1971年，Stephen Cook取得了突破性成果，提供了一种证明思路。（我们都姓Cook，但并没有亲戚关系，虽然我因为这样的误会享受过好几顿免费的大餐。）他的理论指出，NP类中存在一道题，只要我们能找到这一道NP题的好的算法，就能证明每一道NP题都存在好的算法。根据Cook、Karp和其他学者的工作，我们现在知道，这样的题其实不止一道。它们称为NP完全问题。（NP-complete problem）。TSP就是最著名的NP完全问题。

若能对一个NP完全问题找到一个好算法，就足以证明P类和NP类是等价的问题类，即P=NP。。因此，第一个找到TSP的通用解法的人，得到的财富将远远多于宝洁公司当年的大奖——克雷数学研究所悬赏100万美元，奖给能够证明或证否P=NP的人。

人们一般认为，P类和NP类并不等价，但是并没有充分的理论依据，只是感觉不应该奢求P=NP而已。因为P=NP的成立就意味着，只要能把一道题写成可以验证的形式，便立即得知它存在高效解法。而人们正是假设某些NP问题难以求解，并以此为基础建立了现行的密码体系，所以假如这些NP问题都有快速算法，那么网络贸易将陷入停滞。对于破解密码、入侵系统的黑客来说，这就像送给他们一把用来窃取数据的瑞士军刀一样。

与加密系统失败相比，小说《抗体》中的崩溃危机潜伏得更深。故事里，人工智能程序突然效率大增，从而推翻了有生命的主人并取而代之。但是，我们大概不用担心这些可怕的机器，P=NP带来的好处也可能远远大于不良后果。2009年，Lance Fortnow在一篇综述中写道：“很多人只关注问题的负面，认为P=NP会让公开密钥加密技术完全失效。确实如此。但是P=NP的益处更大，足以使整个互联网1变成历史上微不足道的脚注。”他的理由是，最优化将因此变得轻而易举，旅行商能找到最短的路线，工厂能达到最大的生产能力，航班也能安排得当、避免延误，诸如此类问题都能得到解决。一言以蔽之，我们会更好地利用可用资源。科学界、经济界、工程界将出现更加强大的工具和方法，重大突破源源不断。接下来的数年内，诺贝尔奖委员会将忙得不可开交。那是一个如花似锦的美好世界，可是多数人都认为它不会实现。1. Fortnow, L. 2009. Communications of the ACM 78, 78–86.

显然，解决P与NP问题是当代最重大的难题之一。在探讨TSP这样的NP完全问题的过程中，对于好的解法可能带来的种种后果，一定不要过分纠结。若不考虑其深远的影响，归结起来，TSP原本只是简单地为旅行商寻找路线而已。平凡与非凡只在天才的一念之间。1.3 循序渐进，各个击破

将来或许会有人一举攻破终极的复杂性问题，给出惊天动地的答案。在那之前，我们能做什么？直面旅行商问题，目标非常明确：求解更大规模、更难解决的情形。1

TSP是算法工程。（algorithm engineering）的代表问题。这门研究学科重视实用性，以不达目的誓不罢休为理念。理论上，TSP的规模一旦大到一定程度，求解某些实例的计算量就可能高得离谱。但这并不代表只要看到规模很大的具体问题，就只能退而求其次，选择粗略估计作为结果。研究人员正是在这种绝不妥协的态度的推动下，不断改进计算机代码和技术方法，如今已能解决复杂度惊人的大问题。1. “算法工程”这个名词至少可以追溯到1997年，当年在意大利威尼斯举行了首届算法工程研讨会。一个课题组得到了德国科学基金会的资助，致力于算法工程的研究，并把这门学科的内容描述为“实用算法的设计、分析、实现与实验评估”。Petra Mutzel是课题领导者之一，同时也是多特蒙德大学的算法工程学教授。

在TSP研究领域，如果有人攻克了一道未解难题，消息会迅速流传开来，就像登顶喜马拉雅山脉某座处女峰或者打破百米短跑的纪录一样轰动。这并不是因为我们迫切渴望知道这道题目答案的具体细节，而是因为我们迫切需要知道TSP的研究能够继续推进，哪怕只是一小步。也许最终我们注定会败在旅行商手下，但是至少我们曾经拼搏过。1.3.1 从49到85 900

兰德公司的Dantzig、Fulkerson和Johnson是TSP领域的三位英雄人物。虽然计算机时代已经拉开序幕，持续出现大批新人参与研究，但是Dantzig等人通过手工计算得到的49座城市的纪录始终无人能及。算法推陈出新，计算机代码反复编写，研究报告不断发表，然而年复一年，他们的纪录依然屹立不倒。终于，IBM研究员Michael Held和Richard Karp打破了Dantzig等人的垄断局面。Karp正是我们之前提到过的那位计算机科学家。他研究过TSP无法解决的可能性，但是显然并不满足于空谈理论。他们测试的范例是正方形区域内随机分布的64个点，以每两点之间的直线距离代表旅行费用。

接下来的好几年里，尽管有些研究小组对算法稍加改进，试图挤出一点提升的空间，但没有人能打破Held和Karp的绝对领先地位。直到1975年，由Dantzig等人提出的方法重出江湖。这次，Panagiotis Miliotis对他们的想法做了一些改动，并计算出经过80个随机点的最短路线，使Held和Karp的纪录黯然失色。图1-6　TSP的新纪录，包含3038座城市，《发现》（Discover）杂志，1993年1月。

由Miliotis的研究看来，Dantzig等人的方法可能具有极大的威力，远远超出人们对TSP计算极限的预期。此后不久，Martin Grötschel和Manfred Padberg所做的理论研究进一步证实了这一点。这两位数学家在TSP的舞台上叱咤风云长达15年之久，为TSP基本方法的重大推广奠定了基础。他们的成功始于1977年，当时Grötschel在博士论文中构造了周游德国120座城市的路线。随后，Padberg和IBM研究员Harlan Crowder合作，解决了一道出自电路板钻孔问题的实例，对318座城市的情形算出了结果。

尽管这两个结果本身都非常出色，但是直到1987年他们陆续宣布一系列惊人发现的时候，人们才发现，原来之前只是牛刀小试而已。1987年是TSP历史上的丰收年。Grötschel和Padberg两人的研究小组分别在大西洋两岸独立展开研究，很快解决了一道又一道实例：周游美国532座城市，环游世界666个地点，分别含有1002座城市和2392座城市的电路板钻孔问题……Grötschel当时在德国波恩大学和博士生Olaf Holland合作研究，而Padberg则在美国纽约大学与意大利数学家Giovanni Rinaldi共事。

1988年初，乘着这股热潮，Vašek Chvátal和我也决定加入TSP计算的竞争中。前面有Grötschel和Holland、Padberg和Rinaldi的杰出工作，奋起直追的我们没有丝毫优势。不过我们很幸运，因为同时期有那么多来自世界各地的研究人员，他们非常活跃，对该问题的理论方面开展了前所未有的深入钻研。我们仅仅通过筛一遍日益增加的相关研究，就能获取可以用来解决计算问题的强大工具。不过，在正式动手之前，我们迈出了所有工作中最重要的一步——招收David Applegate和Robert Bixby为小组成员，他们两位是当代实力最强的计算数学家。研究起初进度缓慢，好几次走错了方向。1992年，我们成功利用计算机网络并行计算，解决了一道来自电路板钻孔的问题，其规模为3038座城市，创下当时纪录。此时，方法已经成形。在此基础上，我们又在1998年计算得出了周游美国13 509座城市的最优路线，于2004年得到了周游瑞典24 978座城市的最优路线，最终在2006年解决了一道来自实际应用的问题，其规模达到85 900座城市。1我们使用的计算机代码名为“Concorde”，网上到处都可以找得到。1. Concorde代码是用C语言编写的，源代码和程序都公开提供下载。读者如果想深入学习，可以访问http://www.tsp.gatech.edu/concorde/index.html获得相关资源。——译者注

在最后一道创纪录的问题里，85 900座城市代表的是一枚计算机芯片上的不同位点。为了加工定制芯片，需要用激光切割这些位点，而激光光头在各点之间的移动顺序便可转化为TSP模型。尽管每次移动距离只是毫米量级，但总移动时间对芯片生产成本的影响却很大。图1-7和图1-8分别是激光移动的最优路线图和路线局部放大图。图1-7　包含85 900座城市的TSP路线，题目出自计算机芯片应用。图1-8　包含85 900座城市的TSP路线局部放大图。1.3.2 世界旅行商问题

在包含85 900座城市的芯片问题和其他一些电路板钻孔的应用实例中，各点都具有类似网格点的分布形式。早年环游美国48州的题目开启了TSP的漫长研究，而这些例子显然没有真正体现当初那种旅行的精神。不过，仔细观察图1-9所示的三条周游德国的路线，还是很容易体会到，现代的结果在复杂度上的确有所提高。图中规模最小的路线经过33座城市，简称为《指南手册》路线，出自1832年的一本旅行商指南小册子。蓝色路线经过120座城市，是当年Grötschel破纪录的成果。背景里的那条路线则是2001年由Concorde代码对15 112座城市计算得到的最优路线。图1-9　周游德国的三条路线。

也许对德国之旅来说，这条包含15 112座城市的路线就是最完满的路线了。但如果我们将世界上所有城市、区县、乡镇都囊括在内，就连南极的几处科考基地也算上，构造出一个总共包含1 904 711座“城市”的终极旅行挑战，这条路线便远远不够了。这道世界旅行商问题诞生于2001年。来自世界各地的计算机代码纷纷在它面前败下阵来，Concorde也不例外。如果克雷数学研究所的百万悬赏不合你胃口，或许这道世界级难题能点燃你的斗志。截至本书出版之时，本题最著名的路线是由丹麦计算机科学家Keld Helsgaun于2010年10月10日发现的，长度为7 515 790 345米。我们几乎可以肯定，这并非最好的结果，但也已由Concorde计算得知，不存在长度短于7 512 218 268米的路线。这样一来，Helsgaun给出的解最多只比真正的最短路线长0.0476%。两者已经很接近，不过依然有充足的余地让我们再抄几条近道。1.3.3 《蒙娜丽莎》一笔画

为上面那道世界旅行商问题找到最优路线将是了不起的成就，但是求解需要用到的工具方法很可能要在10年以后才会出现。幸好，在征服世界的途中，从来不缺有趣的问题。一个漂亮的例子就是如图1-10所示的《蒙娜丽莎》TSP，总共包含100 000座城市。图1-10　根据列奥纳多·达·芬奇的画作《蒙娜丽莎》设计的TSP，路线由永田裕一发现。

Robert Bosch于2009年2月提出了这道题目的数据集，希望用一条连续曲线画成达·芬奇的这幅名画。日本北陆先端科学技术大学院大学（JAIST）的永田裕一（Yuichi Nagata）取得了迄今为止最好的结果。他的路线最多只比最优路线长0.003%。差距如此之小，令人迫不及待，但毕竟还没有真正完成。有一项1000美元的奖金将颁发给第一个突破永田裕一结果的人，以激励有意参与这道题目的研究者。奖金不错，但是请你铭记在心：问题挑战之所以一道接一道，真正的目的在于积累思路，以便在TSP的通用解法研究以及更大范围的应用领域派上用场。解决问题的新途径才是关键所在。1.4 本书路线一览

图1-11的T恤衫图案出自Jessie Brainerd之手，她曾参加2007年1的布达佩斯数学项目。在应用数学专业或者计算机科学专业，每一名毕业不久的合格本科生都能一眼看出这幅图的主题就是TSP。按照许多大学的课程设置，学习旅行商问题都是必经之路。最近，甚至连美国的中学课本里都有该问题的简单介绍。图1-11　2007年万圣节的TSP。（照片由Jessie Brainerd提供）1 照片上身着T恤衫的男生是Bill Kay。他是Jessie Brainerd的同学，当时他们在布达佩斯参加万圣节晚会。Jessie Brainerd在博客上写了一篇日志，提到晚会上还有两名学生化装成P和NP，手持飞镖枪玩具互相打斗。

对TSP的介绍既然已经如此普及，我写作本书的目的何在？很简单，我希望能让本书读者对它更加了解，不止步于最简单的认识，而是远远深入问题，接触最近的理论进展与最先进的解法。我的终极目标是鼓励你们，希望你们也能踏上对旅行商的追踪之路。也许就在某个未知的拐角处，你们将迈出最终一步，迎来彻底的成功。

本书第2章将从数学和应用两方面追溯旅行商问题的由来，在回顾历史的过程中介绍TSP的基本研究题目，进一步讨论将留到后面各章进行。第3章继续介绍TSP的丰富应用，包括旅行规划、基因组测序、行星搜寻、乐曲编排等方面的内容。

第4章到第7章阐述求解TSP的技术方法，为核心内容。接下来在第8章讨论计算机代码如何解决大规模的TSP题目。

第9章将探讨一般形式的TSP是否存在多项式时间解法。这一理论问题价值百万美金，你若爱钱，这章内容正合你意。然而，即使你钱库空空，亟待现金入账，我也不建议你跳过前面的章节。因为在计算领域大显身手的方法里，很可能孕育着成功解决理论问题的种子。而你若打算证明不存在通用解法，也必须解释清楚为何前人的解法能实际应用却不合要求。

数学知识就介绍到这里。第10章将转向心理学和神经学的研究范畴，论述人类如何在不借助计算机的情况下求解TSP。第11章将带领读者欣赏艺术作品中的TSP路线，比如Julian Lethbridge笔下美妙的抽象画和Robert Bosch设计的简单曲线图案。最后，第12章将再次号召本书读者接受TSP的挑战，并以此结束全书。不屈不挠，前进到底

补充一点小建议。

如果面前有无数艰难险阻横空而降，爱尔兰作家J. P. Donleavy笔下的人物Rashers Ronald会发誓“不屈不挠，前进到底”。1Applegate等人在研究TSP计算时便将这句话作为战斗口号。我建议深入该问题的读者也能坚持这种态度。本书会介绍许多专家，他们的研究取得了重大进展，但仍然没有从根本上解决TSP。要想扭转局势，搞定旅行商，也许我们需要的恰恰只是一个新的思考角度。1 Rashers Ronald出现在J. P. Donleavy的作品The Destinies of Darcy Dancer, Gentleman。中，该书由Atlantic Monthly Press于1994年出版。图1-12　左图：1987年，W. Cook（本书作者，左一）和V. Chvátal（右一）向作家J. P. Donleavy赠送夜壶，由Adrian Bondy拍摄，照片所有权利保留；右图：1987年，J. P. Donleavy写给本书作者的明信片。第2章历史渊源多年来，数学家似乎一直都在数学会议上讨论这个问题，尽管它并不是正式议题。——George Dantzig，Ray Fulkerson，Selmer Johnson，11954年1. Dantzig, Fulkerson, and Johnson (1954).

旅行商问题流传甚广，在数学界颇负盛名，但是它发展成名的历程却迷蒙不清，鲜为人知。就连“旅行商问题”这个生动的名字究竟启用于哪个年代，我们都无法确定。即便如此，我们依然可以讲述这段故事的大部分内容，只不过时常要做一些合理的推测。TSP的历史故事可以作为铺垫，让我们在继续深入该问题之前，首先具备基本的认识和思考，从而更好地了解近年的具体研究工作。2.1 数学家出场之前

人类早就开始着手解决具体的TSP应用问题，而关于它的数学研究在很久以后才渐渐蔚然成风。无疑早在穴居人的年代，我们的祖先就在狩猎采集时解决了一些路线规划问题。这些规划问题的规模很小，可能不像长期规划那样有意义。然而，最近几百年来，在某些特定行业，精心规划的路线显然对从业人员很有帮助。我们的讨论不妨就从观察这些人的旅途开始。2.1.1 商人

说起旅行商问题的由来，须知旅行商确实是最早开始规划路线的人。图2-1是一张城市列表，来自旅行商H. M. Cleveland在1925年写1的书信。Cleveland在美国培基种子公司（Page Seed Company）上班，工作内容是收集玉米等农作物的订单。这张表摘自一份文件，全文共5页，列出了他在缅因州巡回的主要目的地。差旅从7月9日开始，一直持续到8月24日才结束，全程共经过350站，数目相当惊人。1. 这张表来自本书作者从eBay购买的一组藏品。这批收藏品数量很大，都是H. M. Cleveland寄给培基种子公司的账单和信件，能买到它们实在是运气不错。但我并不是总能买到有意思的东西，比如我还买过某个旅行商写了50年的日记，结果发现，他的“旅行”只限于纽约州雪城周围的五六座城市而已。图2-1　培基种子公司旅行商的缅因州目的地列表（全文共5页），1925年。

显然，Cleveland和培基种子公司当时很关心如何才能让旅途时间最短。我们有两个证据：第一，如图2-2所示，他的旅行路线明显效率很高，虽然有一些回头路，但都是限于当时的道路建设情况，个别城镇与外界之间只有一条路相通，所以只能选择原路返回；第二，请仔细阅读下面这封Cleveland写给其老板的信。尊敬的先生：我的路线乱得一团糟，从没见过这么乱的。又要花掉去年一半的工夫来整理路线了。我已经改了一部分，从斯托克顿斯普林斯开始，挨个经过法兰克福、温特波特、汉普登海兰兹、班戈、斯蒂尔沃特、奥罗诺、奥尔德敦、米尔福德、布拉德利、布鲁尔、南布鲁尔、奥灵顿、南奥灵顿、巴克斯波特，然后到了奥兰，再接着走原来的路线。希望您能将我1924年用过的单子寄给我，我想要从德克斯特开始的后半程路线。那个路线比手头这个好太多了。我不明白您到底为什么要让路线有那么大的跳跃，特别是从阿尔比恩居然一下子跳到麦迪逊，简直是从地图这一头跳到那一头。这部分我自己改了。从班戈开始，往南就没有桥能过河了，可您还把那里的城镇都列在单子上，就好像我有本事过去似的。上一季列出来的单子是最好的，我实在看不出为什么要改。我想我已经把话都说清楚了。您忠诚的H. M. Cleveland1925年7月15日

可见，Cleveland对部分路线非常不满，并且自己动手改进路线的设计。图2-2　培基种子公司旅行商的缅因州差旅路线图，1925年。旅行从基特里出发，最终回到斯普林韦尔。两座城市距离很近，均位于缅因州南部。

1925年，Cleveland去了很多地方，缅因州只是目的地之一。他的旅途还经过了康涅狄格州、马萨诸塞州、纽约州和佛蒙特州，总共到了一千多个目的地。他也绝不是唯一一个来回奔波的人。Timonthy Spear为美国旅行商写了一本书，名为100 Years on the Road: The Traveling Salesman in American Culture。（《百年奔波：美国文化中的旅行商》）。他在书中提到，据Commercial Travelers Magazine。（《旅行推销员杂志》）估计，1883年美国有20万旅行商；到了19世纪末20世纪初，估计有35万人；20世纪早期，这个数字仍在增长；到了Cleveland的年代，旅行商已经是大多数美国乡镇的常客了。

Spear也描述了这些旅行商如何参考L. P. Brockett的Commercial Traveller's Guide Book。（《旅行推销员指导手册》）之类的工具书，在自己工作的区域内设计路线。然而，多数情况下，路线是由总部预先制定好的，就像培基种子公司的做法一样。一种优化方法如图2-3所示，工作人员在地图上用图钉和细绳标出各条备选路线，并借此比较路线长度。图2-3　兰德·麦克纳利的地图收纳柜与标针地图，《秘书学》（Secretarial Studies。），1922年。

一本1832年出版的德国手册是这段故事的重要参考文献，这本书德语书名为Der Handlungsreisende — Von einem alten Commis-Voyageur。，翻译成中文就是《老推销员写给新旅行商的指南手册》2。简便起见，以后都称其为《指南手册》。手册里提到，好的路线3很有必要。Der Handlungsreisende — wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines 2. glücklichen Erfolgs in seinen Geschäften gewiss zu sein — Von einem alten Commis-Voyageur.。 B. Fr. Voigt, Ilmenau, 1832. 完整书名意为《老推销员写给新旅行商的指南手册：你该如何表现、如何工作、如何确保成功》3. 该书节选片段由Linda Cook从德文原文翻译为英文，后转译为中文。——译者注图2-4 　德国旅行商指南手册，1832年。由于商务需求，旅行商四处旅行。放之四海而皆准的好路线并不存在，但是通过有效的选取和分解路线，可以节省大量旅行时间，因此我们觉得有义务提供一些这方面的指导意见。只要这些建议对你们有帮助，你们就应当尽量采纳和实践。我们可以保证，对于穿行德国的旅途，由于距离遥远，再加上来回奔波（请格外注意这一点），其他路线都不可能比我们的做法更节约。要记住，重点是到达尽可能多的地点，同时避免重复经过同一个地点。

这里明确叙述了旅行商问题，而叙述者本人就是一名旅行商！《指南手册》提供了经过德国和瑞士境内不同地区的5条路线。在其中4条路线里，都出现了作为局部根据地的城市，因此这些城市都要到达不止一次。但是第5条路线如图2-5所示，是一条真正的旅行商路线，其旅行区域在德国所处的位置参见图1-9。正如《指南手册》所说，这条路线非常好，考虑到当时的道路情况，它甚至可能是最优路线。若以为推销员的生活没有艰难困苦与风波，你必然大错特错。因为他在泥泞中跋涉，冒着雨雪和冰雹工作。他拎起提包，勇敢上路，走南闯北寻顾客。

图2-5 《指南手册》提供的路线，1832年。

19世纪中后期，人们精挑细选美国、英国等国家的旅行路线，集结成册出版了大量书籍。旅行商的形象充满浪漫色彩，也在戏剧、电影、文学与歌曲中留下了身影。在19和20世纪之交的旅行商诗作中，下面这段很有代表性。它摘自一本作品汇编集，出版于1892

4年。若以为推销员的生活没有艰难困苦与风波，你必然大错特错。因为他在泥泞中跋涉，冒着雨雪和冰雹工作。他拎起提包，勇敢上路，走南闯北寻顾客。4. 这段诗是诗歌The Drummer（《推销员》）的开头部分。作品集：Marshall, G. L. A Compilation on the Commercial Traveler.1892. O'er Rail and Cross-ties with Gripsack. 。 New York, G. W. Dillingham。

推销员的辛苦工作与寻找路线的任务甚至出现在桌面游戏中。1890年，麦克劳克林兄弟公司（McLoughlin Brothers）发明了“旅行推销员游戏”（Commercial Traveller），玩家要在铁路系统里自己建造路线。

选择旅行商作为TSP的代言人，显然有理有据。图2-6　旅行推销员游戏，由麦克劳克林兄弟公司于1890年推出，Pamela Walker Laird供图。2.1.2 律师

虽然最先出场的是旅行商，但是也曾有一些从事其他职业的人需要四处奔波。早在15世纪，《牛津英语词典》里就收录了“circuit”一词，意为巡回旅行或巡回路线。这个词的由来与英国的司法管辖区制度有关。当时英国各地的法庭是每年定期开庭审理案件的，因此法官和律师都要在自己管辖的各城镇之间巡回。后来，美国也采用了这种制度。时至今日，虽然法官不再需要巡回奔波了，但美国人仍然把地方法庭称为巡回法庭。

美国历史上最著名的巡回律师很可能是青年时代的亚伯拉罕·林肯。林肯在成为美国第16任总统之前，曾经在法律界工作，参与伊利诺伊州第八法庭区的巡回，负责14个县的公务。Guy Fraker描述了1林肯的旅途。1. Fraker, G. C. 2004. Journal of the Abraham Lincoln Association 25, 76-97.

试读结束[说明：试读内容隐藏了图片]

下载完整电子书