通信网络设计、VLSI布局和DNA序列分析是重要而具有挑战性的问题，不能用初级算法解决。因此，对于计算机科学家来说，掌握良好的算法设计和分析的知识系统是十分重要的。
本书从算法策略的角度来描述算法设计。每个策略包含许多基于此策略的算法设计。对于每个算法，用丰富的实例进行诠释。另外，每个例子都采用详细的图示。
近年来，许多近似算法相继开发出来。本书清晰地描述了其中的两个重要概念：PTAS和NPO完全性。在介绍近似算法之前，本书对NP完全性的概念进行了讨论，并通过大量的具体实例进行解释，目的是使学生对这个很抽象的概念有明确的认识。
另外，本书还介绍了在线算法的专题，每个在线算法通过先描述其内在的基本原理来展开介绍。分摊分析是算法研究的一个新领域，本书对这个不易理解的新概念也进行了详细的介绍。
本书可以作为计算机科学专业高年级本科生或硕士研究生的教材使用。
无
研究算法可能有许多原因，其中的主要原因是能够使我们更高效地使用计算机。实践证明，一位不具备很好算法知识的新手，对于其老板及工作单位来说都是一个大麻烦。假如某人要找一棵最小生成树，设想现在或者将来都不存在计算机，那么他通过检查所有可能的生成树来确定最小生成树的做法，对他来说也许足够好了。但是，如果他了解Prim算法，那么有一台IBM个人计算机就足以解决问题。另一个例子是某人要解决语音识别问题，对他来说如何开始是相当困难的。但是，如果他了解能够使用动态规划方法解决的最长公共子序列问题，那么他将会明白该问题是相当容易解决的。算法的研究不仅对于计算机科学家非常重要，而且通信工程师在编码时也要用到动态规划或A*算法。有许多其他行业的科学家从研究算法中获益匪浅，其中相当一部分是从事分子生物学研究的科学家。当他们要比较两个DNA序列、两个蛋白质或者三维结构的RNA时，需要了解非常复杂的算法。
此外，研究算法也有很多乐趣。由于我们研究算法已经很长时间，因此在任何时候看到新的设计良好的算法时，或者想出关于设计和分析算法的一些新颖想法时，都会异常兴奋。因此，我们也感到有责任让更多的人共同分享这种乐趣和兴奋。许多看似困难的问题实际上可以通过多项式时间算法解决，而一些看似普通的问题却被证实是NP完全的。最小生成树问题对许多初学者来说似乎是相当困难的，但它却有多项式时间的解决算法。如果稍微对它改动一点就成为旅行商问题，那么它就成为一个NP难问题。另一个例子是3可满足性问题，它是一个NP完全问题。通过降低维数，2可满足性问题将会成为P问题。发现这些事实总是令人着迷的。
在本书中，我们将采取一种与众不同的方法来介绍算法。实际上，我们并不是在介绍算法，而是在介绍用于设计算法的策略。原因很简单：明白用于设计算法的基本原则（也就是策略）显然比算法本身更重要。尽管并非每个算法都基于本书所介绍的某个策略，但大部分是这样的。
剪枝搜索、分摊分析、在线算法以及多项式近似方案都是相对较新的思想，而且是十分重要的思想。众多新开发的算法都是基于分摊分析的，正如我们在关于该主题的章末将看到的那样。
我们将从用来设计多项式时间算法的策略开始介绍。在必须解决看似困难但目前的确还没有多项式时间算法的问题时，我们会介绍NP完全性的概念。尽管经常很难把握它的物理意义，但应用NP完全性的概念还是比较容易的。实际上，其核心思想是为什么每个NP问题实例都关联一个布尔公式集，并且当且仅当该公式集可满足时，该问题实例的回答是“yes”。一旦读者明白了这个思想，就会懂得NP完全性的重要性。我们相信用于解释这个思想而提供的实例将会帮助大多数学生很容易地理解NP完全性的概念。
本书可用作高年级本科生和低年级研究生的教材。依据我们的经验，如果在一个学期（约50学时）内讲授本书，那么无法涵盖书中全部的内容。因此，如果只有一个学期，那么我们建议所有章都要讲，但不必都完全讲透。不要忽略任何章！关于NP完全性的章是非常重要的，应该让学生理解清楚这章的内容。最难理解的章是第10章（分摊分析），其中涉及许多数学知识。教师在授课时应当非常注意讲解分摊分析的基本思想，而不应过多地讲述相关的数学证明。换句话说，学生应该能理解为什么与好算法相结合的特定数据结构在分摊的意义上执行得非常好。另一个相对困难的章可能是第12章（在线算法）。
许多算法并不容易理解，我们将尽量清晰地介绍这些算法。介绍每个算法时都辅以实例，而每个实例都利用图进行解释。在本书中，提供了超过400幅图来帮助初学者理解。
我们还引用了关于算法设计与分析的大量书籍和论文；并特别声明最新的成果，使读者能够容易地找到进一步研究的方向。“参考文献”中列出了825本书籍和论文，共涉及1 095位作者。
我们还会在适当的时候提供实验的结果。但作为教师，还是应当鼓励学生通过实现算法来验证结论。在每一章的结尾有进一步阅读的论文列表，鼓励学生阅读这些论文以提升他们对算法的理解是非常重要的。希望学生能领会到作者不遣余力地解释大量难以理解的论文是多么辛苦！书中还提供一些用Java编写的程序，便于学生实践。
我们在此不可能列举出在准备本书的过程中帮助过我们的所有人的名字，因为实在是太多了。但他们都属于一个班，是我们的学生或者同事（许多学生后来成为同事）。在每周五晚上的讨论会上，我们总是积极活跃地讨论。这些讨论指出了算法研究中的新方向，也有助于我们决定本书应该包含哪些资料。研究生们一直在追踪大约20种学术期刊，并确保关于算法的每篇重要论文都存储在数据库中，且都关联上关键字。这个数据库对于写作本书是非常有价值的。最后，他们还阅读了本书的手稿，提出了批评意见，并完成了实验。如果没有来自同事和学生们的帮助，我们是不可能完成本书的。在这里，我们对他们所有人表示无限的感谢。
R. C. T. Lee;S. S. Tseng; R. C. Chang;Y. T. Tsai：R. C. T. Lee: R. C. T. Lee (李家同) 台湾“暨南大学”教授。李教授是美国电机电子学会的荣誉会士，并且曾担任过11种国际学术刊物的编辑委员。他在算法和逻辑方面的著作曾被译为多种文字出版。同时，李教授也是短篇小说作家，他的小说亲切、自然、发人深省，曾感动了无数人。
S. S. Tseng; R. C. Chang: S. S. Tseng (曾宪雄) 和R. C. Chang (张瑞川) 台湾交通大学计算机与信息科学系教授。
Y. T. Tsai: Y. T. Tsai（蔡英德） 台湾静宜大学信息传播工程学系教授兼系主任。
王卫东：暂无简介
本书是算法设计与分析方面的优秀著作。它从策略的角度详细地阐述了关于算法设计的多种设计策略。设计算法的基本原则，也就是策略，显然比算法本身更重要。本书利用算法设计策略作为指导进行算法设计，通过大量实例介绍了设计策略的基本原理，同时强调了对每种算法详细的复杂性分析。
本书的内容具有相当的广度和深度，这包括对各种策略的基本机制、基础算法、基本算法设计技术、算法的复杂度分析等，具体包括算法复杂度与问题的下界、贪心法、分治策略、树搜索策略、剪枝搜索、动态规划、NP完全性理论、近似算法、分摊分析、随机算法和在线算法等。
本书的组织方式简明扼要、循序渐进，涵盖了大多数算法设计中的一般技术，同时包含了剪枝搜索、分摊分析、在线算法以及多项式近似方案等相对较新的思想，这些都是近20年来算法研究中发展迅猛的领域。另外，对于两个重要概念：PTAS和NPO完全性做了清晰的解释。对于在线算法、近似算法、随机算法等结合实例做了详尽的介绍。对于较难理解的分摊分析给出了理论证明。
算法设计一直是备受关注的研究领域之一。因此，本书还介绍了算法设计与分析领域的最新进展、最新成果和特别声明，使读者能够容易地找到进一步研究的方向。
我们相信本书中译本的出版将对国内高校计算机专业算法课程的教学起到积极的推动作用。
由于译者水平有限，翻译中难免有错误和不妥之处，恳请读者批评指正。
王卫东
西安电子科技大学计算机学院
2007年7月
出版者的话
专家指导委员会
译者序
前言
第1章 绪论 1
第2章 算法复杂度与问题的下界 10
2.1 算法的时间复杂度 10
2.2 最好、平均和最坏情况的算法分析 12
2.3 问题的下界 24
2.4 排序的最坏情况下界 25
2.5 堆排序：在最坏情况下最优的排序
算法 28
2.6 排序的平均情况下界 33
2.7 通过神谕改进下界 35
2.8 通过问题转换求下界 36
2.9 注释与参考 37
2.10 进一步的阅读资料 38
习题 38
第3章 贪心法 40
3.1 生成最小生成树的Kruskal算法 42
3.2 生成最小生成树的Prim算法 44
3.3 单源最短路径问题 46
3.4 二路归并问题 50
3.5 用贪心法解决最小圈基问题 54
3.6 用贪心法解决2终端一对多问题 56
3.7 用贪心法解决1螺旋多边形最小合作
警卫问题 59
3.8 实验结果 61
3.9 注释与参考 62
3.10 进一步的阅读资料 62
习题 63
第4章 分治策略 65
4.1 求2维极大点问题 66
4.2 最近点对问题 67
4.3 凸包问题 69
4.4 用分治策略构造Voronoi图 71
4.5 Voronoi图的应用 77
4.6 快速傅里叶变换 79
4.7 实验结果 82
4.8 注释与参考 82
4.9 进一步的阅读资料 83
习题 83
第5章 树搜索策略 85
5.1 广度优先搜索 87
5.2 深度优先搜索 88
5.3 爬山法 89
5.4 最佳优先搜索策略 90
5.5 分支限界策略 91
5.6 用分支限界策略解决人员分配问题 93
5.7 用分支限界策略解决旅行商优化问题 95
5.8 用分支限界策略解决0/1背包问题 99
5.9 用分支限界方法解决作业调度问题 102
5.10 A*算法 106
5.11 用特殊的A*算法解决通道路线问题 110
5.12 用A*算法解决线性分块编码译码
问题 113
5.13 实验结果 115
5.14 注释与参考 116
5.15 进一步的阅读资料 116
习题 117
第6章 剪枝搜索方法 119
6.1 方法概述 119
6.2 选择问题 119
6.3 两变量线性规划 121
6.4 1圆心问题 128
6.5 实验结果 132
6.6 注释与参考 133
6.7 进一步的阅读资料 133
习题 133
第7章 动态规划方法 134
7.1 资源配置问题 137
7.2 最长公共子序列问题 138
7.3 2序列比对问题 140
7.4 RNA最大碱基对匹配问题 143
7.5 0/1背包问题 150
7.6 最优二叉树问题 151
7.7 树的带权完全支配问题 154
7.8 树的带权单步图边的搜索问题 159
7.9 用动态规划方法解决1螺旋多边形
m守卫路由问题 163
7.10 实验结果 165
7.11 注释与参考 165
7.12 进一步的阅读资料 166
习题 167
第8章 NP完全性理论 169
8.1 关于NP完全性理论的非形式化讨论 169
8.2 判定问题 170
8.3 可满足性问题 171
8.4 NP问题 176
8.5 库克定理 177
8.6 NP完全问题 184
8.7 证明NP完全性的例子 186
8.8 2可满足性问题 201
8.9 注释与参考 204
8.10 进一步的阅读资料 204
习题 205
第9章 近似算法 207
9.1 顶点覆盖问题的近似算法 207
9.2 欧几里得旅行商问题的近似算法 208
9.3 特殊瓶颈旅行商问题的近似算法 209
9.4 特殊瓶颈加权k供应商问题的近似
算法 213
9.5 装箱问题的近似算法 217
9.6 直线m中心问题的最优近似算法 218
9.7 多序列比对问题的近似算法 220
9.8 对换排序问题的2近似算法 225
9.9 多项式时间近似方案 230
9.10 最小路径代价生成树问题的2近似
算法 239
9.11 最小路径代价生成树问题的PTAS 241
9.12 NPO完全性 245
9.13 注释与参考 250
9.14 进一步的阅读资料 251
习题 252
第10章 分摊分析 254
10.1 使用势能函数的例子 254
10.2 斜堆的分摊分析 256
10.3 AVL树的分摊分析 259
10.4 自组织顺序检索启发式方法的分摊
分析 261
10.5 配对堆及其分摊分析 264
10.6 不相交集合并算法的分摊分析 275
10.7 一些磁盘调度算法的分摊分析 284
10.8 实验结果 289
10.9 注释与参考 290
10.10 进一步的阅读资料 290
习题 290
第11章 随机算法 291
11.1 解决最近点对问题的随机算法 291
11.2 随机最近点对问题的平均性能 293
11.3 素数测试的随机算法 295
11.4 模式匹配的随机算法 297
11.5 交互证明的随机算法 300
11.6 最小生成树的随机线性时间算法 302
11.7 注释与参考 305
11.8 进一步的阅读资料 305
习题 306
第12章 在线算法 307
12.1 用贪心法解决在线欧几里得生成树
问题 308
12.2 在线k服务员问题及解决定义在平面
树上该问题的贪心算法 310
12.3 基于平衡策略的在线穿越障碍算法 315
12.4 用补偿策略求解在线二分匹配问题 322
12.5 用适中策略解决在线m台机器调度
问题 326
12.6 基于排除策略的三个计算几何问题的
在线算法 331
12.7 基于随机策略的在线生成树算法 335
12.8 注释与参考 338
12.9 进一步的阅读资料 339
习题 340
参考文献 341
