算法设计指南（第2版）

1）由算法领域的知名专家Steven Skiena教授编写。（2）“设计”是本书的核心，作者不但以生动有趣的语言讲授了算法设计中的常用技术与思想，还着重教导我们应从已有经典设计和实现中汲取力量来完成问题求解，而这正是一个优秀算法工作者所必备的素养。（3）为了更全面真实地展现作者的算法设计观，本书每章都给出了若干取自现实案例的精彩War Story，读者可以从中深刻体验到优秀算法设计的曲折历程。（4）本书配套网站包含大量算法设计资源以及作者本人的授课视频，为算法设计者提供了极大的便利。（5）本书英文版长期占据算法设计领域畅销书的销售前列，是一本不可多得的“算法设计指南”，它不仅能作为计算机相关专业算法课程的教材，对于相关领域从业人员亦是极具价值的参考书。 

本书由算法领域的知名专家Steven Skiena教授编写，其主要内容包括基本算法设计、算法分析、数据结构、排序与查找、图算法、动态规划以及难解问题与近似算法。
“设计”是本书的核心，作者不但以生动有趣的语言讲授了算法设计中的常用技术与思想，还着重教导我们应从已有经典设计和实现中汲取力量来完成问题求解，而这正是一个优秀算法工作者所必备的素养。为了更全面真实地展现作者的算法设计观，本书每章都给出了若干取自现实案例的精彩War Story，读者可以从中深刻体验到优秀算法设计的曲折历程。为了减轻阅读的难度，作者淡化了繁难的算法分析而仅仅给出性能结论与对比，这在同类算法书中是相当少见的。此外，本书配套网站包含大量算法设计资源以及作者本人的授课视频，为算法设计者提供了极大的便利。
本书长期居于算法畅销教材前列，是一本不可多得的“算法设计指南”，它不仅能作为计算机相关专业算法课程的教材，对于相关领域从业人员亦是极具价值的参考书。

目录

卷I 实用算法设计

第1章算法设计导引. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1 机器人巡游优化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 合理挑选工作. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 关于正确性的推理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.4 建立问题的模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.5 关于War Story . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.6 War Story: 通灵者的模型建立. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1.7 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

第2章算法分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.1 RAM计算模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.2 大O记号. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3 增长量级与强弱关系. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.4 以大O来推演公式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.5 关于效率的推理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.6 对数及其应用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2.7 对数的特性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.8 War Story: 锥体之秘. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.9 高等分析(.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.10 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

第3章数据结构. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.1 紧接数据结构与链接数据结构. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.2 栈与队列. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.3 字典. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.4 二叉查找树. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.5 优先级队列. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3.6 War Story: 剥离三角剖分. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

3.7 散列与字符串. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.8 专用数据结构. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.9 War Story: 把它们串起来. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

3.10 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

X 目录

第4章排序与查找. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.1 排序的应用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.2 排序的范式. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

4.3 堆排序: 借助数据结构而得的排序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.4 War Story: 给我一张机票. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

4.5 归并排序: 通过分治来排序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.6 快速排序: 通过随机化来排序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

4.7 分配排序: 通过装桶来排序. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

4.8 War Story: 为被告辩护的Skiena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

4.9 二分查找及相关算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

4.10 分治. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

4.11 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

第5章图的遍历. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

5.1 图的风格. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

5.2 用于图的数据结构. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

5.3 War Story: 我曾是摩尔定律的受害者. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

5.4 War Story: 图的获取. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

5.5 遍历图. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

5.6 广度优先搜索. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

5.7 广度优先搜索的应用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

5.8 深度优先搜索. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

5.9 深度优先搜索的应用. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

5.10 有向图的深度优先搜索. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

5.11 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

第6章加权图算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

6.1 小生成树. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

6.2 War Story: 网络之外别无他求. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

6.3 短路径. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

6.4 War Story: 拨出文档. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

6.5 网络流和二部匹配. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

6.6 去设计图, 而非算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207

6.7 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

第7章组合搜索与启发式方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

7.1 回溯. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

7.2 搜索剪枝法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

7.3 数独. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

7.4 War Story: 覆盖棋盘. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

目录XI

7.5 启发式搜索方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

7.6 只不过它不是收音机而已. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

7.7 对阵列退火. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243

7.8 其他启发式搜索方法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

7.9 并行算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

7.10 War Story: 毫无进展. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

7.11 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

第8章动态规划. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

8.1 缓存与计算. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252

8.2 字符串近似匹配. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

8.3 长递增子序列. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

8.4 War Story: 龙虾的进化. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

8.5 划分问题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

8.6 对上下文无关的语言做语法分析. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

8.7 动态规划的局限性: TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

8.8 War Story: 过去所发生的事就是Prolog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

8.9 War Story: 条码的文本压缩. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

8.10 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

第9章难解问题和近似算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

9.1 问题和归约. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

9.2 算法的归约. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294

9.3 基础性的难解性归约. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

9.4 可满足性. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303

9.5 创造性的归约. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305

9.6 难解性证明的艺术. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

9.7 War Story: 争分夺秒亦难. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

9.8 War Story: 后来我失败了. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

9.9 P与NP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

9.10 NP完全问题的处理. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

9.11 习题. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

第10章如何设计算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

参考文献. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

我遇到的大多数专业程序员都不太愿意去解决算法设计问题. 这点很遗憾, 因为算法设计已成长为计算机科学的核心实用技术之一. 若想设计出正确、高效和易于实现的算法去求解真实世界的问题, 需要了解两种不同的知识体系:? 技术——优秀的算法设计师懂好几种基本算法设计技术, 包括数据结构、动态规划、深度优先搜索、回溯以及启发式方法. 也许重要的设计技术应该就是建模了, 它能将杂乱现实世界中的应用问题提炼精化以便于用算法攻破, 这可称得上是门艺术.? 资源——优秀的算法设计师都站在巨人的肩膀上. 他们不是每次都从一张白纸开始费尽心思后创造出新算法来解决问题, 他们会先弄清楚这个问题目前的研究现状. 他们不是从零开始重新实现那些广为流传的算法, 他们会去寻找现有的程序实现并以此作为起点. 他们对许多经典算法问题都非常熟悉, 这些问题为大多数应用问题的建模提供了充足的素材.本书意在作为算法设计的一本指南, 从而让学生和计算机从业人员能走进组合算法技术的殿堂. 全书分为两卷: 技术和资源. 前者是对计算机算法设计和分析技术的一般性指引.后者则可让你进行查阅和参考, 它是由多条简介构成的算法问题便览,1 其中每一条都包含了算法资料、程序实现以及大量的参考书目.

评论

第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)就是完成上述任务的具体步骤. 有许多不同的算法能求解排序问题. 例如插入排序(insertionsorting)就是一种排序的方法, 它一开始会从序列中取出一个元素(从而形成一个平凡的有序列表), 然后再将序列中余下元素按输入次序逐个插入到列表中, 并保证插入后列表仍然有序. 以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 TI N S E R T I O N S O R TI N S E R T I O N S O R TE I N S R T I O N S O R TE I N R S T I O N S O R TE I N R S T I O N S O R TE I I N R S T O N S O R TE I I N O R S T N S O R TE I I N N O R S T S O R TE I I N N O R S S T O R TE I I N N O O R R S S T TE I I N N O O R S S T R TE I I N N O O R R S S T T图1.1 插入排序运行情况演示(时间顺序自上而下)注意此算法具有通用性. 只要能给出合适的比较操作(