9.2 Jack Edmonds的奋战

David Hilbert呼吁提出算法的理论，而图灵出色地作出了回答。然而，自从数字计算机问世以后，效率问题便很快成为最基本、最重要的问题。知道一个问题能由图灵机求解是一码事，但是知道能在有生之年看到图灵机给出问题之解就完全是另一码事了。

有关算法效率的早期讨论围绕TSP等整数规划模型展开。下面这段话颇能代表这段时期的讨论情况。它摘自一篇1953年的论文，作者是Martin Beckmann和诺贝尔奖得主Tjalling Koopmans。¹

^{1. Beckmann, M., T. C. Koopmans. 1953. Cowles Commission: Econ. No. 2071.}

应该加上一点，在所有讨论的指派问题中，当然存在显而易见的暴力求解法，即枚举所有指派方案，分别计算最大化目标的值，选出给出最大值的指派方案。对于大多数具有实际意义的情形，这种方法的成本都太高。而所谓解法，指的是能把更多情形的计算工作量降低到可控范围的求解过程。

Beckmann和Koopmans考虑了一组问题，其中既有TSP，也有将若干工作分配给若干工人的标准指派问题。次年，即1954年，Merrill Flood为高效解法提出了支持的理由。²

^{2. Flood (1954).}

有传言说海军在搭建一台计算机，以解决各种形式的油轮调度问题。这台计算机将带来重大优势，不在于节约执行计算的成本，而在于缩短对运算进行验算所需的时间。这一点，怎么强调都不过分……使用高速计算机可能确实会多花一些钱，但是会使计算具有时间上的可行性。

Flood考虑到这种速度需求，继续评论道，对于TSP，“迄今没有可接受的计算方法”。计算的有穷性不够令人满意，那么判定算法品质时，我们的目标是什么呢？虽然这个问题亟待解决，可是在20世纪50年代却没有出现明确的答案。

现在，轮到Jack Edmonds登场了。我们在本节标题里用了“奋战”一词，没错，就是这个意思——当时人们普遍认为，优于有穷的事情就不该归数学界解决了，而Edmonds不得不与这种舆论作战。他本人在1954年说过：“对于理论数学家而言，利用现有计算机器求出切实可用的解，往往并不是个有趣的问题。”这正是困难所在。诚然，Flood、Koopmans、Kuhn等人对实用求解方法产生了兴趣，单纯形算法在求解线性规划问题方面取得了惊人的成功，可是这或许也妨碍了人们直接讨论优于有穷的算法。之所以造成这种麻烦，是因为单纯形算法似乎能够解决遇到的一切线性规划问题，虽然未能证明它每次都会高效运行。这就导致，算法即使没有性能保证，也能得到人们过分放心的认可。

图9-2　1964年美国国家标准局研讨会，右一为Jack Edmonds，照片由William Pulleyblank提供

Edmonds当时面临的工作非常困难。他的游说活动始于1961年夏天的兰德公司，那一年，他和一群年轻研究者受邀参加研讨会，与会人士还包括该领域的重要人物，比如Dantzig、Fulkerson、Hoffman，等等。Edmonds在兰德公司作了报告，讨论了寻找图中最优匹配的问题。研讨会期间，他成功提出了该问题的一个好算法，换言之，算法步骤数的增长速率至多正比于n⁴，其中n是图中顶点的个数。这个深刻的结果成为了Edmonds的奋战重点，他的数学运算非常美妙，动摇了他人的观点。但是，Edmonds一路上也经历过许多艰难险阻。他有一篇非常值得阅读的回忆录，其中写有下面这段话。³

^{3. Edmonds (1991).}

当年，我在大肆宣扬这件事的时候——我还记得自己着了魔，不遗余力地谈论它——遇到的最大反应就是：“呃，指望出现这种情况有点傻吧，而且我看它好像没什么实际意义，哦对了，如果是n的28次方怎么办，你知道的，那就不……”诸如此类。

今天，没有人质疑他的理论。Edmonds成为了算法和计算复杂性领域的英雄领袖。

有一样东西没有沿用下来，就是“好”这个词的用法。当时，如果一个算法保证能在至多正比于n^k的时间内完成，就称之为好算法，这里n是问题规模的量度，k是某个固定的幂次。第1章已经提到，如今的标准术语是“多项式时间算法”。这可能是个不错的改动，毕竟像单纯形方法这么成功的算法，如果也要说成坏算法，实在有些残酷，让人于心不忍。