算法之道—形而之上谓之道

文 / 邹恒明

1966年3月的一天，美国加州大学洛杉矶分校的Andrew J. Viterbi教授在给研究生讲解缠绕编码的时序译码算法SDCD。但不管他如何讲解，学生就是听不明白。思来想去，Viterbi觉得学生不能理解的原因是该算法的证明过于复杂。于是他开始考虑如何简化这个证明。在经历了持久的烦躁和困惑后，他灵感顿现：需要简化的不是算法的证明，而是算法本身。于是Viterbi对SDCD算法进行了少许修改，提出了基于Trellis的概率译码算法。这个算法就是后来著名的CDMA技术的基石。Viterbi也因此而身价暴涨（创立了高通公司，赚取了数十亿美元）。

一种新算法引来革命性的技术和财富的暴涨，算法的作用不可谓不大。但理解算法、改变人生，或者以算法的思维来进行思考，却对很多人来说是镜中花、水中月，难以触摸。

从广义上定义，算法就是求解问题的步骤（指令）。由于计算机的程序是一条指令接一条指令（步骤）地进行，它实际上就是算法的逐步展开。因此，算法弥漫在所有的软件程序里，堪称计算机的灵魂。

理解灵魂当然不是件容易的事情。除了高度抽象外，算法背后的逻辑也非常缠绕。在看过一个问题的算法解答后，人们感到的不一定是轻松，反而可能是困惑。这些算法是如何被发现或发明的呢？这些问题的解答者是如何想到特定的算法呢？在某些情况下，人们还不一定问得出这样的问题，因为对算法本身可能还没有看懂。其实，深刻掌握算法的人并不多见。尽管很多人会在各种场合指点江山、激扬文字，俨然一副大师的架势，但他们对算法的理解可能十分肤浅。很多经常需要使用算法的人，也不过停留在自发，而不是自觉的阶段：对于见过的问题或者与见过的问题类似的问题知道如何作答，而对于那些与见过的问题没有相似性或相似性很少或相似性不容易看出的新问题就一筹莫展了。

而各种算法书籍中的内容堆积、枯燥陈述、逻辑凌乱甚至理解错误等现象则加剧了人们对算法的畏惧。

市场上的算法书籍琳琅满目，但存在共同的问题：讲述一大堆问题，罗列诸多算法，但从根本上却是就事论事；各种算法设计或分析战略之间没有什么逻辑递进或层次关系，算法各种战略的顺序在安排上非常随意，与它们之间存在的因果关联不相符合。比如，这些书籍在讲动态规划、静态规划、贪婪选择、近似算法等时，没有考虑到不同战略之间的逻辑递进关系，只是随意安排章节，用一些具体问题来讲解这些战略而已。结果就是没有逻辑主线贯通，读起来费力、分散，不能形成有机的整体。看这些书的唯一收获是获得各种具体问题的解答，但在见到一个新问题时，对到底应该使用何种设计战略和分析战略，或者应该以何种顺序来尝试各种战略却模糊不清甚至不得章法。此外，这些算法书对算法战略并没有进行提炼，而是凌乱地分散在各种问题的具体解答中，形不成一种高度，形散神更散，无法系统性地训练读者的算法思维。

这些书作为工具书查阅倒也可以，但作为训练算法思维的读物或者教材显然力有不敌。

那么如何培养算法思维呢？答案就是算法背后的逻辑。不同的算法战略看似不同，实则一脉相承，甚至从更高的层次上看就是同一种思维。所有的算法战略如分而治之、动态规划、贪婪选择、随机化、近似算法等只不过是同一思维的不同方面而已！它们之间存在逻辑和效率的递进关系。明白了这一点，对算法的把握就会达到一个新的境界。我们用众所周知的最小生成树问题为例来加以说明。

图1 最小生成树问题，图中粗线组成一棵最小生成树

最小生成树问题的定义如下。

给定输入为：带权重的连通无向图，每条边的权重为。

要求输出：一棵连接所有节点的树，并且为最小。

例如，图1里面的粗线条组成了该图的一棵最小生成树。

我们是如何获得这棵最小生成树的呢？或者最小生成树问题该用什么方法来解决呢？

最简单的办法当然是暴力战略，即将所有的生成树找出来，计算它们的权重，取出最小的树即可。但此种战略的成本高昂，其数量级为，这里代表图中的边的条数，代表图的节点数量。而这是一个难以令人兴奋起来的阶乘级。显然，我们需要对算法进行改进。那么如何改进呢？

在面临复杂问题时，人类通常选择将问题简化，即将复杂的大问题分解为简单的小问题。在解决了小问题后，再将小问题的解合并为大问题的解。这就是所谓的“分而治之”。由于小问题比大问题更易解决，分治就成了上策，并演化为算法设计的基础战略。对最小生成树问题来说，就是将整个图分解为两（也可以是其他数量）个尺寸（节点数）相等或相近的子图，分别在这两个子图上寻找最小生成树，然后将寻找出的两个最小生成树合并起来即可。显然，分解的成本为线性，但合并的成本是，这样我们得到分治算法的成本递归式为。按照大师解法，该递归式的解为。

这是最优解法吗？仔细分析上述分治算法的成本构成可以发现，在分解个子问题时会出现很多重复的下级子问题，重复解决这些相同的子问题显然不是明智之举。改进的办法就是将重复的子问题解决一次，然后将结果存起来供以后使用，这就是动态规划战略。采用此种战略后，最保守也可以将成本降低至（实际上，在略为优化后可将成本降低到）。

但这是最优解法吗？其实还不是。仔细分析可以发现，由于构建的是最小生成树，我们可以依次选择图里面最小的边作为最小成树的边，条件是新选择的边不与已经选择的边构成环路，直到有条边入选为止。而这正是贪婪选择战略。由于将所有的边排序的时间复杂性为，检查一条边被选中后是否与前面选择的边形成环路的时间复杂性为线性，因此整个算法的时间成本为。如果，此算法的效率将高于前面讨论的标准分治战略的效率。如果再使用改进的数据结构来支持贪婪选择战略，则该时间复杂性可以降低到（使用斐波拉契堆的摊销时间）。

但贪婪选择战略还不是最优战略。仔细分析上面最小生成树的构造算法，我们发现它的成本在于边的选择（排序是为选择做的准备），而构造最小生成树本身的成本只有。我们为什么要花多于构造本身成本的成本来构造最小生成树呢？假如我们知道哪些边属于一棵最小生成树，则构造起来就不费力气了。但要想知道哪些边属于最小生成树，不是需要与其他边进行比对吗？也许我们并不需要。我们可以用一个随机数来告诉我们一条边是否属于最小生成树。准确地说，我们用抛硬币来决定一条边是否应该被纳入到最小生成树里。这样就可以将时间成本降低到线性。这就是随机化战略。

表1 算法战略递进中的最小生成树构建成本

这样，随着算法战略的递进，寻找最小生成树的成本不断降低，且在随机化战略达到线性的最低点（表1）！

不过，细心的读者可能会产生诸多问题。例如，贪婪选择战略下，为什么会想到使用斐波拉契堆呢？斐波拉契堆的摊销分析结果是如何得出的？在随机化战略下，如何保证所选的边确实是最小生成树的边呢？另外，表1中的贪婪选择战略似乎与随机化战略不相上下：和不是一个数量级吗（通常是大于的）？怎么说随着算法战略的递进，成本不断降低呢？

在贪婪选择战略下，我们每次选择权重最小的边加入到一棵初始为空的最小生成树里，被加入的边不能与已加入的边形成环路。在这种战略下，算法的最大成本在每次选择最小的边上。而堆是支持此种操作的最佳数据结构。但对普通的二叉堆来说，每次删除堆顶（我们当然使用最小堆）元素时，需要对堆进行调整以保持堆的属性，从而为后续的取最小边操作打下基础。由于此种调整的时间为对数级，使得整个最小生成树的操作成本为。但如果我们改变思维，取消二叉堆要求每个节点度数不超过2的限制，则调整堆的操作成本将降低到常数级。在这种情况下，每次删除堆顶元素后，直接将元素较大的子堆挂在元素较小的子堆下即可。这样，最小生成树的选边操作的总成本似乎为。加上降距操作的成本，整个最小生成树的成本就是。

等等，这似乎有一个问题：前面所述的堆调整操作为常数级的前提是删除堆顶元素后出现的子堆个数为常数。否则，在一大堆的子堆中间选出最小的元素（从而将别的子堆挂在其下）则可能不是常数时间。因此，问题的关键在于确保删除堆顶元素所产生的子堆个数为常数或者有限。而这种思路就导致了斐波拉契堆的出现。事实上，斐波拉契堆比这更进一步：合并操作也不是马上进行，而是留下这些子堆，在子堆数超出一定的限制时才进行合并操作。此外，出现度数相同的堆（堆顶元素具有同样子节点数）时也进行合并操作：将度数相同的堆合并成新的堆。由此，我们可以得出下面的斐波拉契堆的定义。

• 斐波拉契堆由一组普通的堆（非二叉堆）构成。

• 度为k的节点的任意一棵子树的规模最大为（每个节点的子节点数不能超过）。

• 所有子堆的度数都不相同。

图2给出的是一个斐波拉契堆。

图2 斐波拉契堆结构示意图

在斐波拉契堆下，删除一个堆顶所产生的子堆个数不会超过。因此，在留下来的子堆里面寻找最小元素的时间成本也不会超过。但这样似乎得不到我们想要的的时间。不过，仔细分析发现，在斐波拉契堆的限制下，不可能每个节点的子节点数都是。事实上，绝大部分节点的子节点数都很少。这样少数几个节点的高度数导致的高成本可以摊薄到大量的低度数节点的低操作成本上，从而将整个最小生成树的操作成本降低到每次选边操作为常数成本的境界。这就是摊销分析的中心思想。

对于随机化战略的最小生成树算法，不会因为边的选择是随机的，这条边就一定属于某棵最小生成树。因此，我们在随机挑选边的时候也需要进行某种测试，以衡量此边是否合适。而为了进行此种衡量，我们需要对边进行某种划分，但这种划分和测试本身必须在线性级别上。如何做到这一点呢？鉴于篇幅限制，有兴趣的读者请参阅《算法之道：从无有到无穷》。

对于数量级和的比较，在稠密图的情况下，它们确实是一个数量级。但如果图是稀疏的或者和是一个数量级，则归结为，归结为。如果节点数很多，将显著高于。而且，贪婪选择战略的时间成本是在使用复杂的斐波拉契堆结构情况下，而且是摊销时间！因此，从多方面考虑，随机化战略优于贪婪选择战略。

由本文可见，对最小生成树问题的反复推敲可以串起算法里面的全部设计战略。当这些战略被串起时，我们所看到的就不仅仅是独立分散的个体战略，而是一条平时所不见的算法之道！虽然若隐若现，但对慧眼来说，它确确实实存在。这就是“形而之上谓之道”的算法境界。

作者邹恒明，美国密歇根大学博士。曾任职于美国IBM、国家数据公司、朗讯、EMC公司。目前执教于上海交通大学，著有《算法之道》、《计算机的心智：操作系统之哲学原理》、《有备无患：信息系统之灾难应对》

本文选自《程序员》杂志2011年03期，更多精彩内容敬请关注03期杂志

《程序员》杂志订阅火热进行中