查字典图书网
查字典图书网
兰德小组的研究工作解决了环游美国48 州的难题，却没有彻底解决TSP。他们取得了一次巨大的成功，并不意味着就能搞定规模更大的题目。事实上，如果拉斯维加斯赌场把TSP 的最终结果作为一项赌博项目，那么在数学家看来，把赌注押在“TSP 永远无法彻底解决”上会有更大的胜算。对此，必须明确一点：我们要找的所谓解法（solution），实际上是算法（algorithm），也就是要求对于任何一道实例，只要按照算法一步一步计算，一定能求出最优路线。单单找到周游美国或者周游其他某国的最优路线是不够的。 所以，为一般形式的TSP 找到通用解法的难度可想而知。CharlesStross 在科幻小说《抗体》（Antibodies）①中就写到了这一点。在这篇小说中，有人找到了旅行商问题的高效算法，结果就像世界末日一样，种种事件接踵而来。我们只能希望，TSP 真相大白的那一刻不会宣告所谓的世界末日。无论如何，这件事一旦发生，必然会让世界天翻地覆。为什么？让我们先看看前人是怎么说的。 要想成功解决该问题，很可能需要另辟蹊径，使用前所未有的新方法。事实上，该问题的通用解法很可能压根不存在，若能证实这个结论也是很有价值的。——Merrill Flood，1956 年②依我猜想，旅行商问题没有好的算法。——Jack Edmonds，1967 年③我们在本文中给出了一些定理。它们有力地暗示（尽管不足以证明）：该问题像许多别的问题一样，也将是一道永恒的难题。——Richard Karp，1972 年④ ①英文版见G. Dozois 编辑的“The Year’s Best Science Fiction”（2000 年度最佳科幻小说），2001 年由St. Martin’s Press 出版。中文版刊登于《科幻世界》2010 年7 月刊第54~64 页。 ——译者注 ②Flood, M. M. 1956. Operations Research 4, 61–75. ③Edmonds, J. 1967. J. Res. Nat. Bur. Stand. Sec. B 71, 233–240. ③ Karp (1972). 以上评论者是旅行商问题研究领域的三位大师。Merrill Flood 在20世纪40 年代呼吁人们支持研究TSP，并使它成为基础性研究课题，在这方面，他的贡献无人能及。1956 年，他在讨论该问题的研究现状时，首次提出高效解法根本不存在的可能性。10 年后，Jack Edmonds 重申这一看法，当时他和别人为通用解法是否存在而打赌，而他认为不存在。谈起自己这样想的根据，他谦虚地说：“我对数学提出任何猜想，都是基于如下两条理由：第一，数学上有合理的可能性；第二，我并不确定。”不过，这只是他的玩笑话，因为对于20 世纪的数学，他学识渊博，思考深邃，在世界上是数一数二的，所以他如此下注必然有他的道理。5年后，伟大的计算机科学家Richard Karp 终于揭晓了这个赌的本质。他在一篇文章中把TSP 和许多其他计算问题联系到了一起。具体理论细节留到第9 章再讲，现在只稍做解释。相信这一节内容足以让读者理解，为何在小说《抗体》中，宣告发现TSP的高速算法会让每个人都不寒而栗。 1.2.1 好算法，坏算法 Edmonds 在写下“好的算法”一词的时候，对于“好”的理解和我们一样：如果一个算法能够在我们满意的时间内解决问题，那么它就是好的。然而，他必须把“好”定义为正式的概念，才能让它有合理的数学意义。显然，我们不能指望TSP 的每道题目都能在固定时间（比如一分钟）内通过人力或计算机解决，至少在城市数量增加时应该允许求解时间也相应增加。关键是要确定，时间按照什么速度增长才能得到我们的认可。① 我们用字母n 表示问题的规模，在TSP 中就是城市的数量。由于读取目标城市列表所需的时间与n 成正比，所以可能有些强势的老板就只给我们正比于n 的解题时限。这样的人看问题过于乐观了。就连Edmonds 本人都允许运行时间以更快的速度增加，用更明智的方式划分算法的好 坏。好的算法能保证在至多正比于nk 的时间内完成运算，其中，指数k 可以是任意值，比如取2、3 或者更大的数，但必须是固定值，不能随着n 的增加而增加。于是，算法的运行时间若是以n3 的速度增加，那么它就是好的，若是以nn 或2n 的速度增加，就是坏的。表1-1列出了每秒运算10 亿次的计算机在n 取不同值时相应的运算时间，以便让你感受到好坏之间的差距。可以看到，如果n=10，坏算法也够用了；但如果n 取值达到100 左右，2n 阶的算法会算个没完没了，你肯定不希望出现这种结果。 ① 可能有人会说，考虑问题规模时，城市距离数据的精度也是影响因素。假如我们读取A 城市和B 城市之间的距离（或者旅行费用）时，需要读取几百万位数字，那么确实有影响。但是，即使每段路程都是小于常数K 的整数，TSP 依然相当困难，而这种复杂度是最重要的。我们关心的是TSP 的本质复杂度，因此完全可以放心地忽略数据精度这样的细节。 表1-1 每秒运算109 次的计算机在不同条件下的运行时间 Edmonds 对“好”的正式定义未必总是符合我们的直觉。在一道100 座城市的TSP 面前，我们不会对需要执行n1000 步的算法感兴趣。尽管如此，Edmonds 的想法还是彻底改变了计算数学。算法可以明确地分成“好”与“坏”两种类别，从此数学家有了确定的目标，对计算问题的兴趣也更加浓厚。在应用方面，一旦有人证明某道问题存在好的算法，研究人员便纷纷全力以赴，竞相寻找更低的指数k，通常能把运行时间界限降低到正比于n2、n3 或n4 的程度，最终的计算机代码足以处理规模很大的问题。 我要告诉TSP 的爱好者一个遗憾的消息——TSP 的好算法至今不为人知。迄今为止得到的最好结果发现于1962 年，算法的运行时间正比于n22n。尽 管这不是个好的算法，但是与经过n 点的路线总数(n-1)!/2相比，运算时间增长得已经相当慢了，或许Menger 的好奇心可以由此得到满足。 1.2.2 复杂度类P与NP 按照Edmonds 划分算法的方式，计算问题也可同样分为两类，一类存在好的算法，另一类则不存在。我们喜欢第一类问题，将它们统称为P 类。 为什么用字母P，而不用“G”（good）？这是因为研究人员认为“good”这个词带有主观情感，不太喜欢这种用法，所以多项式时间算法（polynomial-time algorithm）就成为了标准术语。P 就是多项式（polynomial）。 P 类问题的定义清晰明确，但是，有时却很难判断某道给定的问题是不是这一类“好的问题”。没准TSP 也属于P 类，只是我们还没找到好的算法来证明这一点而已。至少，我们看到最优路线时总能判断出来，这为我们保留了一线希望。事实上，假如我们面临的挑战是要找一条短于100 英里的路线，那么，只要别人给我们一个答案，我们就可以轻松验证它的长度是否满足要求。由于这种性质，我们把TSP 归为另一类问题，称为NP 类。对于此类问题，我们总可以在多项式时间内验证某一个解是否正确。这里，两个字母NP 来自非确定性多项式（nondeterministicpolynomial）。“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 的益处更大，足以使整个互联网变成历史上微不足道的脚注。”①他的理由是，最优化将因此变得轻而易举，旅行商能找到最短的路线，工厂能达到最大的生产能力，航班也能安排得当、避免延误，诸如此类问题都能得到解决。一言以蔽之，我们会更好地利用可用资源。 科学界、经济界、工程界将出现更加强大的工具和方法，重大突破源源不断。接下来的数年内，诺贝尔奖委员会将忙得不可开交。那是一个如花似锦的美好世界，可是多数人都认为它不会实现。 显然，解决P 与NP 问题是当代最重大的难题之一。在探讨TSP这样的NP 完全问题的过程中，对于好的解法可能带来的种种后果，一定不要过分纠结。若不考虑其深远的影响，归结起来，TSP 原本只是简单地为旅行商寻找路线而已。平凡与非凡只在天才的一念之间。 ① Fortnow, L. 2009. Communications of the ACM 78, 78–86.