第1章
算法设计导引
何谓算法? 算法是完成某项特定任务的具体步骤. 算法更是藏于程序背后的思想, 当然
这个程序本身至少要过得去才能谈及思想.
一个算法想要让人关注, 它一定要能解决一个有着清楚而且准确叙述的一般性问
题(problem). 要想精确地表述清楚一个算法问题, 我们得描述该算法问题所要处理算
例(instance)1的完备集合, 以及处理完任意一个算例之后所想要得到的输出. 分清一个问题
和问题的一个算例, 这点极其重要. 例如排序这个算法问题2可按如下方式来定义:
问题: 排序
输入: 一个由n个键(key)组成的序列a1, . . . , an.
输出: 输入序列的置换(即重新安排)a′
1, . . . , a′
n, 它满足a′
1 6 a′
2 6 · · · 6 a′
n.
排序的算例可以是存储姓名的一个数组, 例如{Mike, Bob, Sally, Jill, Jan}, 也可以是
存储数字的一个列表, 例如{154, 245, 568, 324, 654, 324}. 先搞清楚你是不是在处理一个一
般性的问题, 这才是你通向最终解决它的第一步.
接收满足问题要求的输入算例, 再将其转换成我们想要的输出, 算法(algorithm)就是
完成上述任务的具体步骤. 有许多不同的算法能求解排序问题. 例如插入排序(insertion
sorting)就是一种排序的方法, 它一开始会从序列中取出一个元素(从而形成一个平凡的有
序列表), 然后再将序列中余下元素按输入次序逐个插入到列表中, 并保证插入后列表仍然
有序. 以C实现的插入排序算法描述如下:
void insertion_sort(item s[], int n)
{
int i, j; /* 计数器*/
for (i = 1; i < n; i++){
j = i;
while ((j > 0) && (s[j] < s[j - 1])){
swap(&s[j], &s[j - 1]);
j = j - 1;
}
}
}
1 译者注: 为区别书中所举实例, 此处译为“算例”, 对算例的描述即规定了对输入数据的要求.
2 译者注: 需要特别注意, 问题和算例在本书算法体系中是两个特定的概念, 与我们通常对它们的认识略有不同.
因此作者又进行了强调, 下同.
4 第1章算法设计导引
图1.1给出了插入排序算法处理某个具体算例(单词“INSERTIONSORT”中的字母)时
数据逻辑关系变化的情况演示.
I N S E R T I O N S O R T
I N S E R T I O N S O R T
I N S E R T I O N S O R T
E I N S R T I O N S O R T
E I N R S T I O N S O R T
E I N R S T I O N S O R T
E I I N R S T O N S O R T
E I I N O R S T N S O R T
E I I N N O R S T S O R T
E I I N N O R S S T O R T
E I I N N O O R R S S T T
E I I N N O O R S S T R T
E I I N N O O R R S S T T
图1.1 插入排序运行情况演示(时间顺序自上而下)
注意此算法具有通用性. 只要能给出合适的比较操作(<)来测出两个键谁应排在前面,
这个算法就能像处理数字那样将姓名排好次序. 根据我们对排序问题的定义, 可以毫无困
难地证明该算法能将所有可能出现的输入算例正确地排序.
一个优秀的算法得具有三个理想的特性. 我们所追求的算法应该——正确(correct), 并
且高效(efficient), 同时易于实现(easy to implement). 这些目标也许无法全部实现. 不过对
于工业界所用的程序, 只要能对问题给出还算不错的答案并且不会让应用程序速度减慢,
通常都是可以接受的, 我们也不会再去管是否存在更好的算法. 在工业界, 通常只有出现性
能上或法律上的严重问题后, 才会引发“寻找最佳答案”或“达到最高性能”这样的议题.
我们在本章中将重点关注算法正确性的问题, 而将效率的相关讨论推迟到第2章. 我们
很少能立即判定某个算法能正确无误地解决所给的问题. 大多数情况下, 有了算法的正确
性证明才能知晓算法是正确的, 这种证明能解释为什么我们能确信该算法在输入问题的任
意算例情况下都肯定能得到所要的结果. 不过, 我们在进行深入讨论之前将先举例说明, 为
什么“这是显然的”绝不足以证明正确性, 反而这句话通常完全就是错的.
1.1 机器人巡游优化
让我们考虑一类常在制造业、运输业和测试应用中常会出现的问题. 假定给我们一个
机器臂, 它配有一件工具(比如烙铁). 在制造电路板时, 所有的芯片和其他电路元件必须焊
接固定到基片上. 更确切地说, 每个芯片都有一组触点(或焊线)要焊到电路板上. 要为机器
臂编制程序以完成此作业, 我们首先必须编制出一套触点的访问次序, 这样机器臂就可以先
访问(并焊接)第1个触点, 然后是第2个, 第3个· · · · · · 这样继续下去, 直到完成作业为止. 接
下来机器臂移回到第1个触点, 为下一块印刷板作准备, 这样使加工轨迹(tool-path)变成一
个封闭的巡游(或称为环).
1.1 机器人巡游优化5
机器人是很昂贵的设备, 因此我们希望装配电路板所花费的巡游时间最少. 机器臂移
动速度恒定是一个合理的假设, 因此在两点之间游历的时间与它们之间的距离成正比. 简
言之, 我们要求解下述算法问题:1
问题: 机器人巡游优化
输入: 集合P, 包含平面上的n个点.
输出: 能访问集合P中所有点的最短环状巡游是怎样的路线?
这个为机器臂编制程序的任务交给你了. 现在停止阅读, 花些时间想出一种求解此问
题的算法. 我会很乐意等到你找出一个方案· · · · · ·
? ? ?
能想到若干算法来求解此问题. 不过, 最为普遍的想法多半应该是最近邻(nearestneighbor)
启发式方法. 我们从某点p0开始, 首先走到离p0最近的邻居p1. 再从p1走到离p1最
近并且尚未访问过的那个邻居, 这样只会将点p0排除在候选点之外, 而不会影响别的点. 接
下来不断重复此过程, 直到跑遍所有未访问过的点为止. 停下来之后我们再回到p0从而让巡
游闭合成环. 将最近邻启发式方法以伪代码方式写出, 大概是这样的:
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
NearestNeighbor(P)
从P中选出一个初始点p0并访问它
p = p0
i = 0
while (还存在未访问过的点) do
i = i + 1
选择离pi?1最近并且尚未访问过的点将其设为pi
访问pi
从pn?1回到p0
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
上述算法有许多可取之处. 该算法易于理解和实现. 为降低遍历的总时间, 在访问更
远的点之前先访问附近的点是合乎情理的. 该算法能完全正确处理图1.2中所给出的实例.
最近邻准则的效率相当高, 因为每对点(pi, pj)至多会检查两次: 一次是在巡游路线中添
加pi时, 而另一次是在添加pj时. 不过, 只需一点即可驳倒上述所有优点——该算法是完全
错误的.
错了? 它怎么能错呢? 这个算法永远都能找到可以巡游所有点的路线, 但它找到的巡游
不一定最短, 甚至可能连接近最短都算不上. 考虑图1.3中的点集, 所有点沿直线依次排开.
图中的数值表示0号点左侧或右侧的各点与该点的距离. 我们从0号点开始, 如果每次向那
1 译者注: 为与后文算法伪代码保持一致, 下面将原文的“集合S”改为“集合P”.
6 第1章算法设计导引
0 0
1
2
3
4
5
6
7
8
图1.2 一个能用最近邻启发式方法成功解决的算例
个离当前点最近并且尚未访问过的点移动, 就会按照“左–右–左–右”这样的方式在0号点上
方不停地跳来跳去, 而此算法却对于打破僵局(break the tie)1束手无策. 在这些点上的另一
种巡游路线则是从最左边的点向右走, 一边走一边访问所遇到的点, 直到碰到最右边的点
后再跳回最左边, 这条路线要好得多, 实际上它是该算例的最优解.
-1 0 1 3 11
-21
-5
-1 0 1 3 11
-21
-5
图1.3 一个使用最近邻启发式方法会失效的算例(带有最优解图示)
现在试想你正对一个如此简单的印刷板做装配演示, 当你的老板看到机器臂像“跳房
子”游戏那样“左–右–左–右”跳着, 她会忍俊不禁的.
“等一下,” 你可能会说, “问题在于我们从0号点开始. 为什么不把最左边的点换作初始
点p0, 并从那里开始使用最近邻准则呢? 这样一来就能找到这个算例的最优解.”
那当然是百分之百正确, 至少在我们将此例旋转90度前确实如此. 现在所有点都处于
最左边. 如果将0号点的位置稍微朝左边挪一点, 这样它就会被选成初始点. 现在机器臂虽
1 译者注: 体育比赛中比分交替上升, 打成平局, 最后决胜称为“break the tie”. 作者将跳来跳去却无法跳出形象
地比喻成僵持不下的局势.
1.1 机器人巡游优化7
然不再“左–右–左–右”了, 却会改成“上–下–上–下”形式的“跳房子”, 而遍历时间几乎和之前
所用时间一样, 效果还是很差. 无论你对挑选初始点做何种改进, 最近邻准则注定会在某个
点集上失效.
或许我们所需要的是另外一种方案. 总是走向最邻近点的这种限制太死, 因为它总会
诱使我们跳进圈套, 即走到我们不希望去的点. 不妨换一种思路, 也许应该不断地将最接近
的那对端点1连起来, 并保证对端点的连接不会引起诸如环提前收尾这样的问题. 每个顶点
开始仅以自己形成顶点链. 当所有的一切合并完成时, 我们最后会得到一条包含所有点的
链. 最后仅存两个端点, 将它们连起来则会交给我们一个环. 在上述这种最近点对启发式方
法(closest-pair heuristic)执行的每一步, 我们都会得到一个集合(包含单顶点和不相交的顶
点链)2可供合并操作而用. 以伪代码方式写出就是:
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
ClosestPair(P)
令n为集合P中点的数目
for i = 1 to n ? 1 do
d = ∞
for each (从不同顶点链中取出的一对端点(s, t))
if (dist(s, t) 6 d) then
sm = s
tm = t
d = dist(s, t)
以边连接(sm, tm)
以边连接最后两个端点
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
这种最近点对准则在图1.3中的实例中能找到正确的巡游路线. 它从0号点开始并将其
连接到最近的邻居, 1或?1. 随后, 下一个最近点对将会左右交替连接, 每次连一条边从而最
终形成路线的主干部分. 最近点对启发式方法略为复杂, 且速度慢于最近邻启发式方法, 然
而不管怎样, 它给出了这个实例的正确解答.
但是它也不能正确求解所有的算例. 考虑在图1.4(左)点集上该算法的运行情况. 该点
集包含两行按列对齐排放且列距相等的点, 且行距(1 ? e)比列距(均为1 + e)稍小一些. 因
此前三个最近点对会穿过两行的间隔铺开, 而不是沿着边界连接. 当这些点配对之后, 余
下的两个最近点对将会交替地沿着边界将前面三个点对连起来. 最近点对巡游路线总长
为3(1?e)+2(1+e)+
√
(1 ? e)2 + (2 + 2e)2. 对比图1.4(右)所示的巡游, 在e ≈ 0时这种方
案比最小巡游多遍历了20%强. 还存在一些实例, 其中的损失远大于此.
这样第2个算法也是错的. 两个算法中哪个表现更好些呢? 你不能仅看到上述实例而做
出判断. 显然, 两种启发式方法都可能在一些看起来很简单的输入上以非常差的巡游路线
而告负.
1 译者注: 端点指当前与其相连的顶点数不超过1的那种顶点.
2 译者注: 顶点链可认为是顶点子集, 单顶点对应仅有一个顶点的子集, 这些子集都互不相交.
8 第1章算法设计导引
?
PPP PPP PPP PPP PPP PPP PPP PPP PPP PPP PP
1 ? e
? ?
1 ? e
1 + e
?
1 + e
? ?
?
1 ? e
? ?
1 ? e
1 + e
?
1 + e
? ?
图1.4 一个使用最近点对启发式方法会失效的算例(左)并附最优解图示(右)
此时, 你也许想知道解决这个问题的正确算法到底看起来像什么样子. 那好, 我们可尝
试枚举这个点集中所有可能出现的元素次序关系, 再选出能最小化总长度的次序.
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
OptimalTSP(P)
d = ∞
for each (点集的置换Pi(共n!个))
if (cost(Pi) 6 d) then
d = cost(Pi)
Pmin = Pi
return Pmin
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
由于所有可能的次序都考虑了, 我们可保证最后得到的就是最短巡游. 因为上述算
法是从所有可能的次序中挑出最好的, 所以该算法是正确的. 但这个算法极为缓慢. 就
算是世界上最快的计算机, 我们都不能指望它能在一天内枚举出20个点的全部排列(共
有20! = 2 432 902 008 176 640 000种). 对于现实中常见的一块印刷板来说, 它的触点数
为n ≈ 1000, 还是别考虑上述算法了. 世界上所有的计算机全天候工作到世界末日, 也无法
接近此问题快要解决的状态, 此时这个问题大概都没有意义了吧.
本节我们讨论的问题称为旅行商问题(traveling salesman problem, TSP), 对旅行商问
题高效求解算法的这种探索与追求将带我们游历本书的诸多章节. 如果你想知道这个故事
是怎么结尾的, 去查看便览中旅行商问题的词条(16.4节)吧.
所得教益: 算法和启发式方法之间有着根本性的不同: 算法总能获得正确的结果; 启发
式方法常常能得到很不错的结果, 但无法对正确性提供任何保证.
1.2 合理挑选工作
现在来考虑下述调度问题. 设想你是一位非常抢手的演员, 有n部正在筹拍的不同影片
都送来了邀你担任主演的片约. 拿到的每份片约都明确说明了拍摄的起始日期和终止日期.
1.2 合理挑选工作9
要接某份工作, 你得答应在整个拍摄期间随叫随到. 因此你不能同时接两个日期区间存在
重叠的工作.
对于像你这样的大明星, 是否接受某份工作的标准很清楚: 你要赚取尽可能多的钱. 这
些影片每部都支付同样的片酬, 所以这意味着你想要尽可能多地去接片, 还要确保任意两
个所接的影片互相不冲突.
例如, 考虑图1.5中那些可供你挑选的拍摄计划. 我们最多只能在其中4部影片里担
任主演, 即“Discrete” Mathematics, Programming Challenges, Calculated Bets和Halting
State或Steiner’s Tree取其一.
你(或你的经纪人)需要在算法意义下解决以下调度问题:
问题: 影片调度问题
输入: 集合I, 它包含直线上的n个区间.
输出: 从I中可选出互不重叠的区间构成一个子集, 那么满足这种条件的最大子集是什么?
The President’s Algorist
Halting State
‘‘Discrete’’ Mathematics Calculated Bets
Programming Challenges
Steiner’s Tree Process Terminated
Tarjan of the Jungle The Four Volume Problem
图1.5 影片无重叠调度问题的一个算例
交给你一份为上述任务研制调度算法的工作. 现在停止阅读, 试着去找出一种算法. 这
次我还是会很乐意等待.
? ? ?
能想到若干算法来求解此问题. 一种是基于以下观念: 只要有工作可做, 最好就去接受
这份工作. 这意味着你应该从起始日期最早的工作开始——毕竟现在没别的工作可接, 至
少在最开始的这段时间如此.
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
EarliestJobFirst(I)
接受I中与此前所接工作均无重叠且开始最早的那份工作j,
不断重复上述过程直到没有这种工作为止.
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
接受开始最早的工作这种想法初看是合乎情理的, 但是一旦意识到过长的首份工作可
能会阻碍我们接受许多其他工作时, 我们就知道该算法是错误的. 仔细看一下图1.6(a), 其
中War and Peace(《战争与和平》)这部史诗片最先开始, 但这部片子的时间却长到了破坏掉
所有其他工作机会的地步.
10 第1章算法设计导引
这个糟糕的实例自然会引出另一种想法. War and Peace的不足之处在于它太长了. 也
许我们应该一开始接受最短的工作, 然后再在每一轮不断寻找可接受的最短工作. 在某个
给定时段中最大化所完成任务的数量, 这种做法很容易让人联想到尽可能快地去大批量制
造劣质产品的场景, 应该会很赚钱吧. 上述想法可带来下面的启发式方法:
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
ShortestJobFirst(I)
while (I ?= ?) do
接受I中能接的最短工作j
删除j和I中所有与j相交的区间
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
这次的想法看起来似乎也是合乎情理的, 但你看看图1.6(b)就知道它也不对了, 接了最
短的工作就会阻碍我们接受另外两项工作. 尽管此处可能损失的片酬看上去小于使用前述
启发式方法的损失, 但它很容易扩展到更大的类似实例中, 并让你的片酬永远不会超过最
优选择情况下所得片酬的一半.
(a) (b)
War and Peace
图1.6 使用最早工作优先(a)或最短工作优先(b)会失效的算例
此时, 尝试所有可能性的蛮力算法开始让人觉得不那么糟糕了, 因为我们确信它是正
确的. 如果我们忽略如何测试一组区间是否确实互不相交的程序细节, 该算法大概应该是
这样:
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
ExhaustiveScheduling(I)
j = 0
Smax = ?
for each (区间集I的子集Si(共2n个))
if (Si中区间互不重叠) and (|Si| > j) then
j = |Si|
Smax = Si
return Smax
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
而它有多慢呢? 关键性的缺陷在于枚举一个由n项事物组成的集合的2n个子集. 好消
息是, 这比像机器人巡游优化问题中所提出的枚举n项事物的所有n!种排列次序好多了.
当n = 20时只有约一百万个子集, 在一台还过得去的计算机上能在1秒内全部清点完. 然
1.3 关于正确性的推理11
而要是给你提供n = 100部影片来选会如何呢? 2100比20!可是大太多了, 而前面那个问题
中20!已经让我们的机器臂投降了.
这个调度问题和机器臂问题的不同之处在于, 存在一种能正确且高效地解决影片调
度的算法. 考虑一下最先结束的工作——即在所有区间中, 其右端点位于最左的区间x. 在
图1.5中扮演此角色的是“Discrete” Mathematics. 其他工作很有可能在x之前开始, 但这些
工作中的任意两个都有一部分会相互重叠, 因此我们在这组工作中至多只能选择一个. 这
组相互重叠的工作中x最先结束, 这样一来剩下的其他工作都有可能会扼杀位于x右侧别的
工作机会. 很明显, 只要挑选了x我们就肯定不会吃亏. 这令我们想到下面这个正确并且高
效的算法:
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
OptimalScheduling(I)
while (I ?= ?) do
接受I中完工日期最早的工作j
删除j和I中所有与j相交的区间
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
确保算法在所有可能的输入情况下给出最优解, 这是一件很难的任务, 然而经过努力
之后我们又常常可以达到这个目标. 寻求反例以证明伪装成正确的那些算法有错, 这是算
法设计过程中一个重要组成部分. 高效算法通常潜伏在难以想到的地方; 而本书则试图培
养你捕获高效算法的各种能力.
所得教益: 看上去合理的算法多半可能是不正确的. 算法正确性是一个需要仔细论证
的特性.
1.3 关于正确性的推理
我们希望前面的实例已经使你对算法正确性的微妙之处有所了解. 我们需要工具去分
辨正确和不正确的算法, 而最主要的一件工具就是证明(proof ).
一个正确的数学证明包括下面几个部分: 第一, 你想证明的必须是一个有着清晰和准确
表达的命题. 第二, 已经有一组我们认为是正确的假设, 因此它可作为证明的一部分. 第三,
有一条推理链能将你从假设带到欲证命题. 最后, 末尾以小块( )或QED(代表拉丁短语“因
此它便得证”)以表示你完成证明(证毕).
本书不准备强调正确性的形式证明, 因为这种证明很难完成, 而且当你卡在中间
证不下去时, 它那让人非常迷惑的形式化推理根本无助于证明. 一个证明实际上是论
证(demonstration)——仅当某个证明可信时它才是有用的; 对于无法一眼看出的算法正确
性, 简明扼要的论据可以解释其原因. 这两点形式证明都不具备.
12 第1章算法设计导引
正确的算法需要精准的阐述, 还得努力来证明它既具备正确性又不含非正确
性(incorrectness). 为了完成上述工作, 我们将在下面几个小节对相关的工具展开讨论.
1.3.1 表述算法
如果不能仔细描述算法中所要执行的步骤序列, 关于算法的推理也就不可能进行. 最
通用的三种算法表达体系是: (1) 英语; (2) 伪代码; (3) 真实的程序设计语言. 这三者本书中
都将使用. 伪代码或许是这里面最难解释的词, 但它可以给出最佳定义——从不蹦出语法
错误提示的程序设计语言. 这三种方法都有用, 因为我们表述时很自然地就会去权衡: 是要
让算法表述更加容易, 还是要让算法描述更精确呢? 英语是最天然但精确性最低的程序设
计语言, 而Java和C/C++是虽然精确但难以编写和理解的程序设计语言. 通常最有用的则是
伪代码, 因为它体现了折中之道.
选择哪种表达体系最好, 这取决于你使用哪种方法最轻松. 我更喜欢使用英语描述某
个算法中的想法(idea), 而如果想将具有技巧性的细节阐述清楚, 我则会转向更形式化、更
像程序设计语言的伪代码甚至于更真实的代码.
我的学生常会犯这样一个通病: 他们用伪代码对算法给出了详尽的表述, 看起来挺像回
事, 可算法思想却压根没说清. 阐明想法应该才是目的. 例如, 前述ExhaustiveScheduling算
法可用英语1更好地写出:
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
ExhaustiveScheduling(I)
测试区间集I的所有子集Si(共2n个),
并将包含互不重叠区间的最大子集作为返回值.
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
所得教益: 任何算法的要点是其中的想法. 如果在表述算法时你的想法没有清晰地展
现, 那就得归咎于你描述算法所用的表达体系层级太低.
1.3.2 问题和特性
为论证算法的正确性, 我们所需要的不仅仅是一个算法描述, 同时还需要为待解决问
题给出一个细致的描述.
问题的规格包含两部分: (1) 允许的输入算例集, (2) 算法输出所要满足的特性. 我们不
可能证明某个算法能正确地求解一个描述含糊的问题. 换言之, 问错误的问题就会得到错
误的解答.
某些问题规格所允许的那种输入算例过于宽泛. 当影片调度问题中的拍摄计划具体实
施时, 假定我们允许它可以停一段时间再继续开拍(比如说在9月和11月拍摄, 中间的10月停
1 译者注: 我们已将该算法描述译为汉语.
1.3 关于正确性的推理13
工). 这样任意一部影片的拍摄计划都可能变为一个由拍摄区间所构成的集合. 我们的明星
可以随意接受互相交错但不重叠的两个计划(比如上面所提到的影片和一个8月与10月之间
进行拍摄的影片刚好可以拼到一起). 在经过此类推广之后的调度问题中, 最早结束算法将
不起作用. 事实上, 这个推广问题不存在高效算法.
所得教益: 在算法设计中, 一项非常重要而且广受赞誉的技术是: 不断将问题所允许的
算例集狭义化, 直到找出正确高效的算法为止. 例如我们可将一般性的图降到树来约
束图问题, 又比如可从二维降到一维以约束几何问题.
在详述问题输出所要求的规格时, 通常会有两种陷阱. 一种是问一个没有解释清楚的
问题. 在没解释“最佳”这个词表示什么意思之前, 要求给出地图上两点之间的最佳路线是
个愚蠢的问题. 你想找的是总距离最短的路线, 还是最快的路线, 抑或是转弯次数最少的那
个呢?
另一种陷阱是给算法定了一个复合目标. 上面提到的三种路径规划标准都定义了清晰
的目标, 因此会指引我们找出正确且高效的最优算法. 不过, 你只能挑一个标准. 例如找一
条从a到b且转弯次数不得超过最少转弯次数两倍的最短路线这样的目标虽然定义完全清
楚, 但它结构复杂, 因此难以推理和求解.
我强烈建议你去挨个查阅本书卷II算法问题便览中的75个问题陈述. 为你的问题找一
个确切的阐述形式, 是求解它的一个重要部分. 而且, 如果有人已经在你之前考虑过相似的
问题, 学习这些经典算法问题的释义将有助于你认出它.
1.3.3 论证非正确性
证明某算法是不正确的(incorrect), 最好的办法就是构造出一个算例让该算法得出不
正确的答案. 这样的算例称为反例(counter-examples). 发现算法的反例之后, 理智的人肯定
会很谨慎地去用这个算法. 非常简单的算例会立刻一针见血地宣布那些看上去合理的启发
式方法失效. 好的反例一般具有如下两条特性:
? 可证实性(verifiability)——为论证某个特定算例是某种算法的反例, 你必须要做到:
(1) 计算在此算例下你的算法会给出什么答案, (2) 展示一个更好的答案来证明该算
法没有找到它.
由于你必须在脑袋里装着这个特定的算例以供随时推演, 那么可证实性的一个重要
组成部分就是· · · · · ·
? 简明性(simplicity)——好的反例会压缩掉所有不必要的细枝末节. 它能使人确切地
明白为何所提出的算法失灵. 一旦找到某个反例, 应该将其精简到只剩下本质性的
要素为止, 这是非常有意义的. 例如, 图1.6(a)中的反例可以将重复的线段从5个降
到2个, 这样更简单而且更好.
14 第1章算法设计导引
搜寻反例的这种能力值得培养. 它与为计算机程序制定测试集的工作有着某种相似性,
但前者依赖灵感, 而后者倾向于穷尽所有可能情况. 这里是一些有助于你搜寻反例的技术:
? 小中见大(think small)——注意我所给出的机器人巡游反例已压缩到6个(“跳房
子”那个还可以用更少的点), 而调度反例仅为3个区间. 这意味着以下事实: 要是算
法失效, 我们常常都能找到一个非常简单的算例, 算法在该算例上运行会给出错误
结果. 不在行的算法工作者往往会拟出一个杂乱异常的算例, 然后不知所措地盯着
它. 专家则会仔细打量若干简单的算例, 因为它们易于验证和推理.
? 考虑周全(think exhaustively)——对于算例规模量的最小非平凡值n,1 要考虑的情
况不会很多. 例如, 两个区间在直线上只能以三种有实际意义的方式出现: (1) 作为
不相交的区间, (2) 作为相互重叠的区间, (3) 作为真嵌套区间, 即一个在另一个里
面. 以各种可能的方式在上述三种算例中分别加入一个区间, 三个区间情况下所有
算例(包括令两种影片调度启发式方法失效的反例)便可有条理地构造出来.
? 寻觅弱点(hunt for the weakness)——如果所提出的算法是“每次取出最大”(更为人
熟知的叫法是“贪心算法”)这样的形式, 想想为什么这种算法策略有可能被证明是
错的, 尤其是· · · · · ·
? 令其势均力敌(go for a tie)——要证明贪心启发式方法不对, 一种迂回的办法是给
出某种算例, 其中每个元素都一样大. 贪心启发式方法立刻就失去了基于序关系作
出决策的能力, 于是便可能随意选择最后导致它返回某个次优解.
? 寻找极端情况(seek extremes)——许多反例混合了巨大和微小、左和右、很少和许
多、近和远. 通常验证极端情况的实例比验证那种异常混杂的实例要容易(因为毫
无规律可言). 考虑两团极度密集的点, 这两团之间所隔距离d远大于团内点距. 无论
点的个数是多少, 最佳旅行商巡游长度基本上就是2d这个数值左右, 因为团内点的
情况对巡游几乎没有什么实质性影响力.
所得教益: 找反例是证明某个启发式方法不具备正确性的最好方法.
1.3.4 归纳与递归
寻找某个特定的反例失败, 这并不意味着我们可以说: “显然, 该算法是正确的.” 我们
需要给出算法正确性证明的论证过程. 通常, 数学归纳法是首选方案.
当我第一次了解数学归纳法时, 它看上去完全像魔术. 你先在1或2这样的基础情形下
证明一个像
Σn
i=1 = n(n + 1)/2的公式, 再预先假定从基础情形一直到n ? 1该命题都正确,
最后可用上述假定来证明一般情况下的n总是成立. 这是证明吗? 太荒谬了!
而我第一次了解递归这种程序设计技术时, 它看上去也完全像魔术. 程序检测输入参
数是否属于像1或2这样的基础情形. 如果不是, 你可通过将这个较大的问题分割成若干小
1 译者注: 指算例中所处理的元素个数. 一般而言, n = 1是平凡情况.
1.3 关于正确性的推理15
块(即子问题), 并调用它自己作为子程序来求解这些子问题, 进而可解决原问题. 这是程序
吗? 太荒谬了!
递归和数学归纳法看上去都像魔术的原因是, 递归就是数学归纳法. 在这两种方法中,
我们都能找到一般条件和边界条件, 利用一般条件一步步将问题割成小而又小的问题. 初
始条件或边界条件最后会终止递归. 一旦你理解了递归或归纳, 就可以了解为什么另一个
也是正确的.
我曾听到这样的说法, 计算机科学家是只知道用归纳法来证明问题的数学家. 这种说
法部分正确, 其原因是计算机科学家证明问题的能力确实不强, 而更主要的原因是: 在我们
所研究的算法中, 很多算法不是递归的就是增量式的(incremental).
考虑在本章开始所介绍的插入排序的正确性. 其原因/推理(reason)可按数学归纳法描
述如下:
? 基础情形仅含一个元素, 由定义知一个单元素的数组完全有序.
? 在一般情况下, 我们可假定, 插入排序的n ? 1次迭代之后, 数组A中的前n ? 1个元
素完全有序.
? 为在A中插入最后一个元素x, 我们要去找x所应摆放的位置, 即小于等于x的最大元
素与大于x的最小元素之间的点, 显然这个位置是唯一的. 可将所有大于x的元素向
后依次挪一位, 这样所产生的空位就是x所要的位置, 于是x的插入位置便可找到.
因此插入排序是正确的.
不过肯定有人要对归纳证明提出疑义, 因为它可能会悄悄出现一些相当细微的推理错
误. 第一个是边界错误(boundary error). 例如, 上述插入排序的正确性证明给出了如下命
题——两个元素之间存在一个唯一的位置可插入x, 而当我们的基础情形是一个单元素的
数组时这个命题就很冒失了. 这提示我们还需要正确处理插入最小或最大元素的特例, 这
更要多加小心.
归纳证明的第二个同时也是更常犯的错误和随意扩展断言(claim)有关. 在给定问题的
算例中额外加入一个元素可能会导致最优解完全改变. 图1.7是影片调度问题的一个实例.
在插入新线段后的最优调度不会包含插入前最优解所包含的任何线段. 要是完全无视此类
难点的话, 可能会让你对一个错误算法给出一个看上去令人信服的归纳证明.
图1.7 在算例中插入单个区间(以虚线表示)后, 最优解(以盒状物表示)所发生的大规模变动
所得教益: 数学归纳法通常是证明一个递归或增量式算法的正确思路.
停下来想想: 增量式的正确性
问题: 证明下面这个自然数增量操作(即y → y + 1)递归算法的正确性.
16 第1章算法设计导引
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
Increment(y)
if (y = 0) then
return 1
else if (y mod 2) = 1 then
return 2 · Increment(?y/2?)
else
return y + 1
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
证明: 此算法的正确性对我来说无疑不是显然的. 但是由于它是递归的, 而我又是位计算机
科学家, 我的自然反应就是尝试以归纳法证明它.
它显然可正确处理基础情形y = 0. 很明显返回值为1, 且0 + 1 = 1.
现在假设一般情形下(即y = n ? 1)该函数运行无误. 上述假设给出之后, 我们接下来
得论证y = n时命题为真. 这类y值有一半是很容易证明的, 即y为偶数时(也即y mod 2 = 0),
因为直接就返回了y + 1.
y为奇数时, 答案取决于Increment(?y/2?)所返回的值. 这里我们想使用归纳假设, 但它
不是很合适. 我们已假设Increment在y = n ? 1时运行无误, 但未假设该函数处理?y/2?(约
为y的一半)时会怎样. 可以加强我们的假设以解决这个问题, 即声明一般情形为所有
的y 6 n ? 1取值. 这种假设的修订虽然看起来没什么本质性改动, 但它对证出该算法的正
确性却是必不可少的.
现在奇数y(即y = 2m + 1, m为某一整数)情况便可这样处理:
2 · Increment(?(2m + 1)/2?) = 2 · Increment(?m + 1/2?)
= 2 · Increment(m)
= 2(m + 1) = 2m + 2
= y + 1
于是一般情形获证.
1.3.5 求和
数学求和公式经常在算法分析中出现, 这方面的知识我们将在第2章中学习. 此外, 证
明求和公式的正确性是归纳法的一个经典应用, 本章末尾将以习题形式列出若干求和的归
纳证明练习. 为了让你更容易理解上述内容, 这里复习一些关于求和的基础知识.
求和式是描述任意大小的集合中元素之和的简明表达式, 特别是如下公式:
Σn
i=1
f(i) = f(1) + f(2) + · · · + f(n)
这里有一些代数函数求和式的简单闭形式. 例如, n个1之和为n,
1.3 关于正确性的推理17
Σn
i=1
1 = n
前n个正整数的和可通过将第i个和第n ? i + 1个配对而知晓:
Σn
i=1
i =
(Σn
i=1
(i + (n ? i + 1))
)/
2 = n(n + 1)/2
能认出下述两类基本的求和公式将会让你在算法分析中完成很多任务.
? 算术级数(arithmetic progression)——在第2章的选择排序的分析中看到S(n) =
Σn
i=1 i = n(n + 1)/2这种式子时, 我们将会遇到算术级数. 从大局观思考, 重要的是
和为平方量级, 而不是式中的常系数1/2. 推广到一般情况, 对于p > 1, 我们有
S(n, p) =
Σn
i=1
ip = Θ(np+1).
依上式可知平方之和是立方量级, 而立方之和则是四次方(quartic)量级(如果你使
用“quartic”这个词的话). 大Θ记号(Θ(x))将在2.2节中给予严格解释.
对于p < ?1时, 此和在n → ∞时总是收敛至一常数. 而当p取?1(它在上述两个p的
取值范围之间)时该和式很有意思, 这就是调和级数:
H(n) =
Σn
i=1
1/i ≈ ln n.
? 几何级数(geometric progression)——在几何级数中, 求和号中的下标会作用到指数
上, 即
G(n, p) =
Σn
i=0
ai = (an+1 ? 1)/(a ? 1).
如何解读这个和式取决于级数的基(base), 即a. 当a < 1时, 它在n → ∞时收敛至某
一常数.
事实证明, 此级数的收敛性是算法分析中十足的“免费午餐”. 它意味着级数之和可
能是个常数, 而不一定与级数的项数成比例增长. 例如, 1+1/2+1/4+1/8+· · · 6 2,
不管我们把多少项加起来都如此.
当a > 1时, 该和式的值随着每加入一个新项而迅速地增长, 例如, 1 + 2 + 4 + 8 +
16 + 32 = 63. 实际上, 对于a > 1, G(n, a) = Θ(an+1).
停下来想想: 阶乘的公式
问题: 用归纳法证明
Σn
i=1 i × i! = (n + 1)! ? 1.
证明: 直接依照归纳法的范式很容易证明. 先验证基础情形(这里证明n = 1情形, 不
过n = 0情形可能更具一般性):
Σ1
i=1
i × i! = (1 + 1)! ? 1 = 2 ? 1 = 1.
18 第1章算法设计导引
再假设此命题一直到n都为真. 我们要证明n + 1的一般情况, 注意到下式中取出最大项
后便可显露出归纳假设式的左侧:
nΣ+1
i=1
i × i! = (n + 1)(n + 1)! +
Σn
i=1
i × i!
因此以归纳假设式的右侧替换则可给出
nΣ+1
i=1
i × i! = (n + 1)(n + 1)! + (n + 1)! ? 1
= (n + 1)! × ((n + 1) + 1) ? 1
= (n + 2)! ? 1
从和式中分离出最大项并显露出归纳假设的某个实例, 这是一种通用性技巧, 它是所
有此类证明的要点.
1.4 建立问题的模型
根据已被前人精确描述且深入认识的问题而构筑出你的实际应用是一种艺术, 这就是
建立模型. 恰当地建立模型是将算法设计技术应用于实际问题的关键所在. 其实, 建模能将
你的实际应用与已有成果联系起来, 模型要是建得合适, 就可能不再需要去设计甚至实现
算法了. 恰当地建立模型同时也是有效利用本书卷II中“算法世界搭车客手册”的关键.
现实世界的实际应用包含着取自现实的对象. 你可能正致力于这些系统: 在网络中安
排通信路由, 或是在大学中寻找教室的最优排法, 抑或是在企业数据库中寻找某些模式.1
然而, 大多数算法都是在严格定义的抽象结构上而设计的, 如置换、图、集合等结构. 要想
充分利用算法文献, 你得学会像文献中那样基于基本结构来抽象地描述问题.
1.4.1 组合式对象
之前要是有人已经碰巧研究过你的算法问题(也许是完全不同的应用场合下), 你现在
解决它的把握就会很大. 但是你得弄清楚对于你要解决的这个特殊的“widget2优化问题”现
在已经研究到何种程度了, 可别指望在能在参考书中刚好找到“widget”这样一个词条. 你必
须将该优化问题表述为在一种抽象结构上计算某种特性, 常见结构如下:
? 置换(permutation)——它是若干元素的安排或排布. 例如(1, 4, 3, 2)和(4, 3, 2, 1)是
对于某个4元素集的两种不同置换. 我们已在机器人巡游优化问题和排序中见过置
换. 每当你的问题要寻求“安排”“巡游”“排布”或“序列”时, 置换很可能就是问题中
的对象.
1 译者注: 模式(pattern)指一个不包含空串的非空语言, 可由一个字符串(例如“abc”)组成, 也可以是一个字符串
集合(例如“a?c”这样的字符串, 其中“?”可代表字母表中任意字符).
2 译者注: “widget”指某种不知名的小设备/小装置(因为现实中它们的种类繁多无法一一起名), 而我们不可能
对每种小设备都有深入的研究, 此处的widget也是泛指这样的问题.
1.4 建立问题的模型19
? 子集(subset)——它代表从一组元素中所挑出的项. 例如, {1, 3, 4}和{2}是从前4个
正整数中挑出的不同子集. 元素的次序在置换中很重要, 但在子集中却无关紧要, 因
此{1, 3, 4}和{4, 3, 1}应认为完全一样. 我们已看到在影片调度问题出现了子集. 每
当你的问题要寻求“簇”(cluster)1“群集”“委员会”“群组”“装箱”或“选择”时, 子集很
可能就是问题中的对象.
? 树(tree)——它代表元素之间的等级关系. 图1.8的左边描绘了Skiena家族的部分家
谱图. 每当你的问题要寻求“等级”“强弱关系”(dominance relationship)“祖先/子孙
关系”或“逐级分类”(taxonomy)时, 树很可能就是问题中的对象.
? 图(graph)——它代表对象之间的关系, 这种关系可能会存在于任意两个对象之间.
图1.8的右边就是以图对公路网建模, 其中顶点为城市, 而边则是连接一对城市之间
的公路. 每当你的问题要寻求“网络”“线路”“万维网”或“关系”时, 图很可能就是问
题中的对象.
? 点(point)——它代表某个几何空间中的位置. 例如, 麦当劳的位置可用地图/平面上
的点描述. 每当你的问题要处理“地方”“方位”“数据记录”或“位置”时, 点很可能就
是问题中的对象.
? 多边形(polygon)——它代表某个几何空间中的区域. 例如, 国家的边界可用地图/平
面上的多边形描述. 每当你的问题要处理“形状”“区域”“外形”或“边界”时, 多边形
很可能就是问题中的对象.
? 串(string)——它代表了字符序列或模式(pattern). 例如, 班级中的学生姓名可用串
表示. 每当你在处理“文本”“字符”“模式”或“标记”时, 串很可能就是问题中的对象.
Sol
Steve Len Rob Richard Laurie Jim Lisa Jeff
Morris Eve Sid
Stony Brook
Orient Point
Montauk
Shelter Island
Sag Harbor
Riverhead
Islip
Greenport
图1.8 分别以树和图建立两种取自现实的结构
上述基本结构都有与之相关的算法问题, 而这些问题将在卷II算法问题便览中予以展
示. 熟悉它们很重要, 因为这些问题为我们提供了用于对实际应用建模的语言. 要想熟悉
便览中的术语体系, 你必须将它从头到尾浏览一遍, 并研究每个问题的输入(input)和输
出(output)图示. 理解了这些问题能让你以后在实际应用中碰到时知道去哪里找, 即便你只
看懂了问题的图示或定义也会大有裨益.
对实际应用建模的成功案例将在散布于全书的War Story予以讨论. 不过, 在这里我们
还得再告诉你几条注意事项: 对实际应用建模可将它缩减成由少数已有问题和结构所组成
1 译者注: “cluster”作动词译为“聚类”, 作名词译为“簇”.
20 第1章算法设计导引
的实体. 这种方法的本质决定了其局限性, 因为你的实际应用中的某些细节可能难以用模
型中的标准问题表达. 另外, 某些问题能以多种不同的方法建模, 而其中一些方法远胜于其
他方法.
建模只是为问题设计算法的第一步. 在处理你的实际应用时, 对某些细节与候选模型
之间的差异要保持警觉, 但也不要过早宣布你的问题独一无二. 最好先暂时忽略那些尚未
匹配的细节, 这样就不用一开始浪费太多时间去思考这些细节是否真的很重要.1
所得教益: 根据已有明确定义的结构和算法对你的实际应用建立模型, 这是通往解决
方案的最重要一步.
1.4.2 递归式对象
学习递归地思考就是学会如何找出较大的递归式对象, 即严格依照较小的同类对象构
造而成的较大对象. 如果你认为房屋是一组房间, 那么添加或删除某个房间后所留下的依
然是房屋.
递归式对象在算法世界中随处可见. 其实, 前文中每个抽象结构都可用递归方式考虑.
如图1.9所示,2 你只需要明白如何能将它们拆成小对象即可.
A L G O R I T H M
4+(1,4,2,3)
{1,2,7,9} 9+{1,2,7}
(4,1,5,2,3)
A L G O R I T H M
图1.9 组合式对象的递归分解: 左栏为置换、子集、树和图, 右栏为点集、多边形和串
? 置换——从基于{1, . . . , n}的某一置换中删除首元素后, 你会得到以剩下元素构成
的置换. 因此置换是递归式对象.
? 子集——集合{1, . . . , n}的所有子集S包含着一个{1, . . . , n ? 1}的子集S′, 并可通过
删除S中的n(如果S中有n的话)使S′这个子集凸显. 因此子集是递归式对象.
1 译者注: 先去寻找到合适的算法和基本结构与之大致匹配.
2 译者注: 其中对于置换的递归定义, 作者在其网站上作了解释: (4, 1, 5, 2, 3)可拆成4和1, 5, 2, 3, 即将4从序列
中移去. 而表示4个元素的置换应采用集合{1, 2, 3, 4}的元素, 因此1, 5, 2, 3在置换定义下应写成(1, 4, 2, 3), 即
对1, 2, 3, 5施加置换(1, 4, 2, 3).
1.5 关于War Story 21
? 树——删除树的根你会得到什么? 一堆更小的树. 删除树的叶子你会得到什么? 一
棵略小的树. 因此树是递归式对象.
? 图——删除图中的任一结点, 你会得到一个更小的图. 现在将图的顶点分成左右两
组. 将跨越左右两组的所有边从中切断, 你会得到什么? 两个更小的图和一束被切
断的边. 因此图是递归式对象.
? 点——取一团点, 再画一条线将其一分为二. 现在你便拥有更小的两团点. 因此点集
是递归式对象.
? 多边形——对一个具有n个顶点的简单多边形, 在其两个不相邻顶点间插入一条内
弦, 则将原多边形切成两个更小的多边形. 因此多边形是递归式对象.
? 串——从串中删除首字符, 你会得到什么? 一个更短的串. 因此串是递归式对象.
对象的递归描述既需要分解规则, 还需要基础情形(即关于最小和最简单对象的明
确描述, 此时分解终止). 基础情形通常易于定义. 只有0个元素的置换和子集看上去大概
像()和{}. 有实际意义的最小树和图包含单个顶点, 而有实际意义的最小点团也只包含单个
点. 多边形稍微需要注意, 最小简单多边形为三角形, 边再少就不能再称为多边形了. 最后,
空串中只有0个字符. 将0个元素还是1个元素选为基础情形, 这只是喜好和是否方便的问题,
而无关乎大体.
这种递归分解将会给出许多算法, 我们会在本书中一一看到. 睁大眼睛迎接它们吧.
1.5 关于War Story
想了解精心设计的算法是如何能对性能产生巨大作用的, 最好的办法就是去看真实的
案例研究. 仔细地研究他人的经历, 就能知道他们可能会怎样去处理我们所面临的问题.
散布于本书的War Story是一些我个人在算法研究中值得回忆的经历, 描述了我们在
实际应用中对算法设计所做的努力尝试, 大部分是成功的, 但偶尔也会失败. 我希望读者能
吸收这些经验并为己所用, 这样在你自己对问题发起进攻时它们可以发挥典范作用.
每个War Story都是真实的. 当然, 复述这些故事时已对其稍加修饰, 并加入了生动的
对话以使故事的可读性更强. 不过, 我尽量忠实地记录从原始问题直至最终解决的过程, 因
此你可以观察到此过程究竟是如何展开的.
《牛津英语词典》(Oxford English Dictionary)对算法学家/算法工作者(algorist)的定义
是: “one skillful in reckonings or figuring”. 在这些故事中, 我尽量生动地展现算法学家在
进攻某问题过程时所用的思考方式.
这些各式各样的War Story通常至少包含一个(经常是好几个)卷II算法问题便览中
的问题. 当某个问题出现时, 我会提及便览中与该问题所对应的章节. 这样做是为了强
调——根据经典算法问题来建立实际应用的模型大有裨益. 每当你需要了解关于某个特定
问题的已有成果时, 只要使用便览便能从中抽出想知道的内容.
22 第1章算法设计导引
1.6 War Story: 通灵者的模型建立
我在办公室正坐着, 突然有个电话来找我.
“Skiena教授, 希望您能帮帮我. 我是博彩系统集团的总裁, 我们的最新产品里出现了一
个问题, 需要一个能求解它的算法.”
“可以啊.” 我回答. 毕竟, 我所在这个工程学院的院长总是鼓励学院的教师(faculty)1与
工业界多些互动.
“我们博彩系统集团在推销一种程序, 它的设计目的是提高我们的顾客预测中彩数字的
能力.2 在通常的博彩中, 每张彩票上包含了某个范围内的6个数字, 比如说它们选自1到44.
因此, 任何给定彩票只有相当小的几率赢得大奖. 然而, 加以适当的训练后, 我们的顾客能
在44个数字中预判出某些数字(比如说15个), 并能保证这些数中至少有4个将成为中奖数.3
我所说的这些话您理解了吗?”
“不太明白.” 我回答道. 但我那会脑子里在回想院长鼓励我们与工业界互动的景象.
“我们的问题是这样的. 假定通灵者(psychic)已将可选数字集缩小到15个数, 且能肯定
其中至少有4个将成为中奖数, 我们得找出最高效的方法来利用这条信息. 假定每当您的彩
票上选对至少3个数字时, 就会中奖并可兑换成现金. 我们需要一种算法来构造出必须购买
的最小彩票集, 这样即可保证至少能中最低奖.”
“假定通灵者是正确的?”
“对, 我们假定通灵者是正确的. 为使通灵者的投资最小化, 我们需要一个程序打印出
他所应购买的所有彩票. 您能帮我们吗?”
他们是找对人了, 由此看来他们也许真有通灵能力. 找出应买的最小彩票子集是一个极
具组合味的组合算法问题. 我们将把它转化成某类覆盖问题, 即所购买的每张彩票都要“覆
盖”通灵者所选集合的某些可能出现的4元素子集. 在所有可能性中找出最小彩票集以覆盖
所有元素是集合覆盖(set cover)(这是一个NP完全问题, 18.1节会讨论它)的一种特殊算例,
据此推测最小彩票集问题在计算意义上大概也是难解的.
该问题确实是集合覆盖问题的一个特殊算例, 用4个参数即可完全表述清楚: 候选
集S的大小n(通常n ≈ 15), 每张彩票用以填写数字的格子数目k(通常k ≈ 6), S中已被通
灵者确保会出现的数字个数j(比如说j = 4), 最后还有中奖最低应匹配的数字个数l(比如
说l = 3). 图1.10表示了在一个较小算例下的覆盖, 其中n = 5, j = k = 3, 而l = 2.4
“尽管找到精确的最小应购买彩票集会很难, 如果用启发式方法, 我应该可以让您非常
接近于最便宜的彩票集合覆盖”, 我告诉他, ”这样可以满足要求吗?”
“只要比我的竞争对手销售的程序所产生的彩票集更好就行. 他的系统可不是每次都保
证能中奖的. Skiena教授, 我实在很感激您帮忙改进我公司的程序.”
“还有最后一件事. 如果您的程序能训练人们挑出中彩号码, 为何您自己不用它来赢取
奖金呢?”
“我期待尽快与您再次通话, Skiena教授. 感谢您的帮助.”
1 译者注: “faculty”一词无法精准译出, 读者可进入欧美各大学的网站以了解“faculty”与“教师”的异同.
2 是的, 这是一个真实的故事.
3 译者注: 受过这种训练的顾客便会成为下文中的通灵者.
4 译者注: l = 2, 因此图1.10中取成对数字.
1.6 War Story: 通灵者的模型建立23
1, 2
1, 3
1, 4
1, 5
2, 3
2, 4
2, 5
3, 4
3, 5
4, 5
图1.10 以彩票{1, 2, 3}, {1, 4, 5}, {2, 4, 5}, {3, 4, 5}覆盖{1, 2, 3, 4, 5}的所有数对
我挂断电话后陷入了沉思. 看起来把这事交给一个聪明的本科生是个理想方案. 以集
合和子集的语言来建模后, 这个解决方案的主干部分看上去就非常易懂了:
? 我们要找个能从候选集S生成所有子集(包含k个数字)的方案. 14.5节描述了对集合
生成有排名(ranking)/无排名(unranking)子集的算法.
? 我们需要对“什么集合可以称为彩票购买覆盖集”进行确切的阐述. 最明显的准则
是, 我们要买数量较少的一组彩票, 使得对于S的任意一个l-子集(共
(n
l
)
个), 所购买
的彩票中必有一张包含该子集, 由于每个子集都可能出现, 那么我们必会中奖进而
有可能赚回购买彩票的本金.
? 我们必须记录下迄今为止哪些中奖组合1已覆盖. 我们想找的彩票应该能够尽可能
多地覆盖尚未覆盖的中奖组合. 当前已覆盖的那些中奖组合是所有可能中奖组合集
合的一个子集. 用于子集的数据结构在12.5节中讨论. 最佳候选者看起来应该是位
向量, 它能在常数时间回答“这个组合已经覆盖了吗?”
? 我们需要一种搜索机制来确定下次该买哪张彩票. 集合的元素个数要是不太大, 那
么我们可在所有可能的彩票子集上穷举搜索进而选出最小者. 对于较大的问题, 使
用随机搜索方法如模拟退火(见7.5.3节)所选出的彩票能够尽可能多地覆盖那些仍
未覆盖的组合, 而这就是我们应该买的彩票. 通过不断重复这种随机搜索过程若干
次并从中挑出质量最好的一个解, 我们有可能会提供一组很好的彩票.
除掉搜索机制的细节, 用于彩票购买情况记账2的伪代码大概是这样:
I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I · · · · · · · · · · · · · · · · · · I
LottoTicket(n, k, l)
将拥有
(n
l
)
个元素的位向量V 全部初始化为false
while (V 中存在为false的条目) do
选一个{1, 2, . . . , n}的k-子集T作为下次要买的彩票
1 译者注: 指l-子集, 由于所有l-子集都可能中奖, 因此称之为中奖组合.
2 译者注: 本书中常常使用“记账”一词, 意为如实记录.
24 第1章算法设计导引
for each (T的l-子集Ti)
V [rank(Ti)] = true
对已买的这组彩票报表
J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J · · · · · · · · · · · · · · · · · · J
Fayyaz Younas这个机灵的本科生勇敢地接受了这个挑战. 基于上述框架, 他实现了一
个蛮力搜索算法, 并能在不太长的时间内找到n 6 5情况的问题最优解. 他还实现了一个随
机搜索过程以求解规模更大的问题, 并且花了些时间对程序调优从而最终设定了一个最佳
版本. 终于到了能给博彩系统集团打电话宣布问题已解决的那天.
“我们的程序对于n = 15, k = 6, j = 6, l = 3情况找到了一个最优解, 也即需要购
买28张彩票.”
“二十八张!” 总裁不答应了, “肯定有错误. 你仔细看, 下列5张彩票就足以覆盖所有可
能子集两次了: {2, 4, 8, 10, 13, 14}, {4, 5, 7, 8, 12, 15}, {1, 2, 3, 6, 11, 13}, {1, 7, 9, 11,
12, 14}.”
我们把这个实例捣鼓了一会, 不得不承认他说的确实是正确的. 我们居然没有正确
地建立问题的模型! 事实上, 我们不需要以最小彩票集去直接覆盖所有可能的中奖组合.
图1.11给出了能解决前述4-彩票实例的2张彩票的方案, 你可从中了解总裁所给出覆盖方案
的基本原理. 如果公布了像{2, 4, 5}和{3, 4, 5}这种乍一看没指望的开奖结果, 但是图1.11所
给的彩票仍会分别与这个结果有一对数字匹配. 我们先前试图覆盖的组合太多了, 而这些
精打细算的通灵者是不会为这样的铺张浪费行为买单的.
1, 2
4, 5 1, 3
3, 5
3, 4
2, 5
2, 4
2, 3
1, 4
1, 5
图1.11 {1, 2, 3, 4, 5}为彩票数字范围, 仅用彩票{1, 2, 3}和{1, 4, 5}即可确保能有一对数字中奖
幸运地是, 这个故事有个圆满结局. 我们原先基于搜索的求解方案框架对新找到的真
正问题依然有效. 当用某组给定彩票去覆盖整个集合时, 我们所应修正的仅仅是新情况下
该组彩票中的某张能确保哪些子集可被覆盖.1 经过上述改造后, 我们实现了他们所期待的
那种结果. 博彩系统集团非常感激, 他们采纳了我们的程序并吸收进他们的产品中, 并且觉
得使用此产品肯定能帮助顾客博得头彩.
1 译者注: 图1.11中以{2, 4}为例, 它实际上会被覆盖到, 因为包含它的中奖数字只可能是{1, 2, 4}, {2, 3, 4},
{2, 4, 5}, 这3个都与{1, 2, 3}或{1, 4, 5}有一对数字相互匹配. 本章有关于此的习题.
1.7 习题25
此故事的寓意是, 在解决问题之前, 要设法确保你对问题的建模是正确的. 在本节这个
实例中, 我们提出了一个还算不错的模型, 但在开始编程之前并未足够深入地研究以保证该
模型确实有效. 如果开始编程前先用手算出一个小实例, 并且再跟研发经费赞助商多通通
气, 就会很容易发现我们对该问题的误读. 我们能从此错误重新回到成功, 显示了初始的方
法构思基本上没什么大问题, 而且它正确地对下面的任务作了清晰的抽象: (1) 有排名/无
排名的k-子集, (2) 集合抽象数据类型, (3) 组合搜索.
章节注释
每本严肃的算法教材都反映了其作者的算法设计观. 有许多表述形式与设计观点与
本书不同的教材可供选择, 对于那些想寻求这些书的学生们, 我们特别推荐Cormen等人
的[CLRS01], Kleinberg/Tardos的[KT06]和Manber的[Man89]这几本书.
算法正确性的形式化证明非常重要, 很值得对其进行更详细的讨论, 不过它不是本书
所关注的重点, 所以本章仅仅一带而过. 可在Gries的[Gri89]中看到对程序验证技术全面深
入的介绍.
影片调度问题形象地展示了独立集问题(independent set problem)的一种相当特殊的
情况, 独立集问题这个更具一般性的问题将在16.2节中讨论. 影片调度问题只允许以区
间图G作为输入算例: 直线上的区间可视为图G中的顶点, 如果i和j所对应区间相互重叠
则(i, j)是图G中的一条边. Golumbic在[Gol04]中提供了这类有趣且重要的图的完整论述.
Jon Bentley的《编程珠玑》(Programming Pearls)专栏或许是关于算法最知名的War
Story了. 它原载于Communications of the ACM, 现已集结成两册书[Ben 90, Ben 99].
Brooks的《人月神话》(Mythical Man Month)是另一本收集了War Story的著作, 它关注软
件工程更胜于算法设计, 但你依然可从中汲取许多深刻洞见. 每个程序员都应阅读上述这
些著作, 为了顿悟, 更为愉悦.
对于彩票集合覆盖问题, 我们在[YS96]中详细地阐述了其求解方法.
1.7 习题
寻找反例
1-1. [3] 证明a + b可能会小于min(a, b).
1-2. [3] 证明a × b可能会小于min(a, b).
1-3. [5] 设计/画出一张道路交通网, 它有a和b两个点, 并满足a和b之间最快的路线不是最短
的路线.
1-4. [5] 设计/画出一张道路交通网, 它有a和b两个点, 并满足a和b之间最短的路线不是转弯
次数最少的路线.
26 第1章算法设计导引
1-5. [4] 背包问题(knapsack problem)描述如下: 给定整数集S = {s1, s2, ..., sn}与目标数
值T, 寻找S的一个子集使得其中元素加起来恰为T. 例如, 存在S = {1, 2, 5, 9, 10}的一个子
集其元素和为T = 22, 但T = 23时却无法找到.
为下列每个背包问题的求解算法找出反例. 即对每个算法给出这样的S和T: 虽然该算
例可解, 但用该算法所选出的子集不能完全装满背包.
(a) 从左到右将S中元素取出, 若背包还能放下则放入此元素, 即最先适应算法.
(b) 按从小到大顺序将S中元素放入背包, 即最佳适应算法.
(c) 按从大到小顺序将S中元素放入背包.
1-6. [5] 集合覆盖问题(set cover problem)描述如下: 给定全集U = {1, . . . , n}的一组子
集S1, . . . , Sm, 寻找S = {S1, . . . , Sm}的最小子集T使得∪ti∈T ti = U. 例如, 有以下子集:
S1 = {1, 3, 5}, S2 = {2, 4}, S3 = {1, 4}, S4 = {2, 5}. 集合覆盖应为S1和S2.
为下面的算法寻找反例: 为了找出集合覆盖, 我们先选出最大的子集, 然后从全集中删
除此子集所包含的所有元素. 重复加入包含那些尚未覆盖元素个数最多的子集, 直到所有
元素都被覆盖为止.
正确性证明
1-7. [3] 对所有大于2的常整数c, 证明下述两个自然数相乘的递归算法之正确性.
function multiply(y, z) // 注释: 返回yz的积
if z = 0
return 0
else
return multiply(cy, ?z/c? + y · (z mod c))
1-8. [3] 证明下述多项式求值算法的正确性.
P(x) = anxn + an?1xn?1 + . . . + a1x + a0, 并令A = {a0, a1, ..., an}.
function Horner(A, x)
p = an
for i from n ? 1 to 0
p = p ? x + ai
return p
1-9. [3] 证明下述排序算法的正确性.
function bubblesort(A : list[1..n])
int i, j
for i from n to 1
for j from 1 to i ? 1
if (A[j] > A[j + 1])
交换A[j]和A[j + 1]的值
1.7 习题27
归纳法
1-10. [3] 以归纳法证明, 对于n > 0,
Σn
i=1 i = n(n + 1)/2.
1-11. [3] 以归纳法证明, 对于n > 0,
Σn
i=1 i2 = n(n + 1)(2n + 1)/6.
1-12. [3] 以归纳法证明, 对于n > 0,
Σn
i=1 i3 = n2(n + 1)2/4.
1-13. [3] 证明
Σn
i=1 i(i + 1)(i + 2) = n(n + 1)(n + 2)(n + 3)/4.
1-14. [5] 在n > 1时, 对于所有a ?= 1, 以归纳法证明
Σn
i=0
ai =
an+1 ? 1
a ? 1
.
1-15. [3] 以归纳法证明, 对于n > 1
Σn
i=1
1
i(i + 1)
=
n
n + 1
.
1-16. [3] 以归纳法证明, 对于所有的n > 0, n3 + 2n可被3整除.
1-17. [3] 以归纳法证明一棵n个结点的树恰有n ? 1条边.
1-18. [3] 以数学归纳法证明前n个正整数的立方和等于这些数之和的平方, 即
Σn
i=1
i3 =
(Σn
i=1
i
)2
.
估计
1-19. [3] 你所有的书籍全部加起来至少有一百万页吗? 你学校图书馆所藏书籍的总页数是
多少?
1-20. [3] 本书有多少字?
1-21. [3] 一百万秒是多少小时? 多少天? 回答这些问题的所有演算只能在你头脑里完成.
1-22. [3] 估计美国有多少个市和镇.
1-23. [3] 估计每天从密西西比河出口流出多少立方米水. 不要查任何额外的资料数据. 描
述你得到此答案所做的全部假设.
1-24. [3] 磁盘驱动器访问时间通常以毫秒(千分之一秒)或微秒(百万分之一秒)计量吗? 你
的RAM访问一个机器字的时间比1微秒多还是少呢? 如果你的机器全时运行, 其CPU一年
能执行多少条指令呢?
1-25. [4] 在你的机器上一个排序算法用1秒可排1000项, 它排10000项将要用时多久· · · · · ·
(a) 如果你相信此算法用时正比于n2, 答案是多少?
(b) 如果你相信此算法用时大概正比于n log n, 答案是多少?
实现项目
1-26. [5] 实现1.1节中的两种TSP启发式方法. 在实际中它们哪个能给出更优的解? 你能想
出比它俩运行得都要好的启发式方法吗?
28 第1章算法设计导引
1-27. [5] 在1.6节的博彩问题中, 给定一组彩票, 描述如何测试它们是否足以形成覆盖. 写出
一个程序来寻找较好的彩票集.
面试题
1-28. [5] 写出一个不用/和*运算即可执行整数除法的函数. 尽量找一个比较快的方案完成
本题.
1-29. [5] 现有25匹马. 在同一时刻, 至多能有5匹马同时比赛. 你必须确定出最快的、第二
快的、第三快的马. 寻找能完成此任务的最少比赛次数.
1-30. [3] 全世界有多少名调琴师?
1-31. [3] 美国有多少家加油站?
1-32. [3] 冰球场的所有冰有多重?
1-33. [3] 美国的公路总长多少英里?
1-34. [3] 为找到某个名字, 每次你在曼哈顿的电话簿中以随机方式迅速翻开一页, 平均情
况下需要多少次能找到呢?1
编程挑战赛
这些编程挑战赛问题, 可在http://www.programming-challenges.com或者http://
uva.onlinejudge.org/上找到, 它们均具备自动判分功能.
1-1. “The 3n + 1 Problem” — Programming Challenges 110101, UVA Judge 100.
1-2. “The Trip” — Programming Challenges 110103, UVA Judge 10137.
1-3. “Australian Voting” — Programming Challenges 110108, UVA Judge 10142.
1 译者注: 此过程类似查字典, 先随机翻到某页, 再根据所查名字与当前页内容的字典序关系向左或向右再随机
找下一页.
第2章
算法分析
算法是计算机科学中最重要和最历久弥新的组成部分, 其原因是它能以一种与语言和
机器都无关的方式来研究. 这就意味着, 我们需要一些技术可让我们无须实现算法即可比
较不同算法的效率. 我们将介绍两种最重要的工具: (1) RAM计算模型, (2) 最坏情况复杂
度的渐近分析.
评估算法意义下的性能会用到“大O”记号, 事实证明它对于算法的比较分析以及设计
更高效算法都是不可或缺的. 尽管对于那些声称自己从事实际工作的人可能会碰到理论分
析的这些概念而脸色苍白(他们确实难以学会), 我们还是提供了这部分内容, 因为它在构想
算法时实在是太有用了.
算法分析本质上是一种记分(keeping score)方法,1 它应该是本书中数学要求最高的部
分了. 不过你一旦理解了算法分析思想背后的直观意义, 那种数学公式的形式化处理就变
得容易多了.