1.2 不可能的任务吗

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

所以，为一般形式的TSP找到通用解法的难度可想而知。Charles Stross在科幻小说《抗体》（Antibodies）¹中就写到了这一点。在这篇小说中，有人找到了旅行商问题的高效算法，结果就像世界末日一样，种种事件接踵而来。我们只能希望，TSP真相大白的那一刻不会宣告所谓的世界末日。无论如何，这件事一旦发生，必然会让世界天翻地覆。为什么？让我们先看看前人是怎么说的。

_{1. 英文版见G. Dozois编辑的“The Year's Best Science Fiction”（2000年度最佳科幻小说），2001年由St. Martin's Press出版。中文版刊登于《科幻世界》2010年7月刊第54~64页。——译者注}

要想成功解决该问题，很可能需要另辟蹊径，使用前所未有的新方法。事实上，该问题的通用解法很可能压根不存在，若能证实这个结论也是很有价值的。

——Merrill Flood，1956年²

_{2. Flood, M. M. 1956. Operations Research 4, 61–75.}

依我猜想，旅行商问题没有好的算法。

——Jack Edmonds，1967年³

_{3. Edmonds, J. 1967. J. Res. Nat. Bur. Stand. Sec. B 71, 233–240.}

我们在本文中给出了一些定理。它们有力地暗示（尽管不足以证明）：该问题像许多别的问题一样，也将是一道永恒的难题。

——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. 可能有人会说，考虑问题规模时，城市距离数据的精度也是影响因素。假如我们读取A城市和B城市之间的距离（或者旅行费用）时，需要读取几百万位数字，那么确实有影响。但是，即使每段路程都是小于常数K的整数，TSP依然相当困难，而这种复杂度是最重要的。我们关心的是TSP的本质复杂度，因此完全可以放心地忽略数据精度这样的细节。}

图1-4　Jack Edmonds（2009年摄，Marc Uetz提供）

表1-1 每秒运算10⁹次的计算机在不同条件下的运行时间

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

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

图1-5　旅行商问题（xkcd.com的Randall Munroe供图）

我要告诉TSP的爱好者一个遗憾的消息——TSP的好算法至今不为人知。迄今为止得到的最好结果发现于1962年，算法的运行时间正比于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来自非确定性多项式（nondeterministic 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. Fortnow, L. 2009. Communications of the ACM 78, 78–86.}

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