本书围绕算法设计技术组织素材，对每种算法技术选择了多个典型范例进行分析。本书将直观性与严谨性完美地结合起来。每章从实际问题出发，经过具体、深入、细致的分析，自然且富有启发性地引出相应的算法设计思想，并对算法的正确性、复杂性进行恰当的分析、论证。本书覆盖的面较宽，凡属串行算法的经典论题都有涉及，并且论述深入有新意。本书内容由浅入深，讲解通俗易懂，具有很强的可读性。

本书是近年来关于算法设计和分析的不可多得的优秀教材。本书围绕算法设计技术组织素材，对每种算法技术选择了多个典型范例进行分析。本书将直观性与严谨性完美地结合起来。每章从实际问题出发，经过具体、深入、细致的分析，自然且富有启发性地引出相应的算法设计思想，并对算法的正确性、复杂性进行恰当的分析、论证。本书覆盖的面较宽，凡属串行算法的经典论题都有涉及，并且论述深入有新意。全书共200多道丰富而精彩的习题是本书的重要组成部分，也是本书的突出特色之一。

本书适用于本科高年级学生以及研究生算法课的教材，也很适于具有计算机或相近专业本科水平的人自学算法的需要。

第1章 引言：某些典型的问题1

1.1第一个问题：稳定匹配1

1.2五个典型问题9

带解答的练习14

练习16

注释和进一步的阅读20

第2章 算法分析基础21

2.1计算可解性21

2.2增长的渐近阶25

2.3用表和数组实现稳定匹配算法31

2.4一般运行时间的概述34

2.5更复杂的数据结构：优先队列41

带解答的练习48

练习49

注释和进一步的阅读51

第3章 图53

3.1基本定义与应用53

3.2图的连通性与图的遍历56

3.3用优先队列与栈实现图的遍历62

3.4二分性测试：宽度优先搜索的一个应用68

3.5有向图中的连通性70

3.6有向无圈图与拓扑排序72

带解答的练习76

练习78

注释和进一步的阅读81

第4章 贪心算法82

4.1区间调度：贪心算法领先83

4.2最小延迟调度：一个交换论证89

4.3最优高速缓存：一个更复杂的交换论证94

4.4一个图的最短路径98

4.5最小生成树问题101

4.6实现Kruska1算法：Union—Find数据结构108

4.7聚类113

4.8Huffman码与数据压缩115

4.9最小费用有向树：一个多阶段贪心

算法126

带解答的练131

练习134

注释和进一步的阅读145

第5章 分治策略147

5.1第一个递推式：归并排序算法147

5.2更多的递推关系151

5.3计数逆序155

5.4找最接邻近的点对158

5.5整数乘法163

5.6卷积与快速傅里叶变换165

带解答的练习171

练习173

注释和进一步的阅读175

第6章 动态规划177

6.1带权的区间调度：一个递归过程177

6.2动态规划原理：备忘录或者子问题迭代182

6.3分段的最小二乘：多重选择184

6.4子集和与背包：加一个变量188

6.5RNA二级结构：在区间上的动态规划192

6.6序列比对196

6.7通过分治策略在线性空间的序列比对201

6.8图中的最短路径206

6.9最短路径和距离向量协议211

6.10图中的负圈214

带解答的练习218

练习222

注释和进一步的阅读237

第7章 网络流239

7.1最大流问题与Ford—Fu1kerson算法240

7.2网络中的最大流与最小割246

7.3选择好的增广路径250

7.4前向流推动最大流算法254

7.5第一个应用：二分匹配问题262

7.6在有向与无向图中的不交路径266

7.7对最大流问题的推广270

7.8调查设计274

7.9航线调度276

7.10图像分割280

7.11项目选择283

7.12棒球排除286

7.13进一步的方向：对匹配问题增加

费用289

带解答的练习294

练习297

注释和进一步的阅读318

第8章 NP与计算的难解性320

8.1多项式时间归约321

8.2使用“零件”的归约：可满足性问题325

8.3有效证书和NP的定义328

8.4NP完全问题330

8.5排序问题335

8.6划分问题340

8.7图着色343

8.8数值问题347

8.9co一NP及NP的不对称性350

8.10难问题的部分分类352

带解答的练习354

练习357

注释和进一步的阅读372

第9章 PPPATε：一个超出NP的

问题类373

9.1PPPATε373

9.2PPPATε中的难问题374

9.3在多项式空间中解量化问题和博弈问题376

9.4在多项式空间内求解规划问题378

9.5证明问题是PSPACE完全的382

带解答的练习384

练习386

注释和进一步的阅读387

第10章 扩展易解性的界限388

10.1找小的顶点覆盖389

10.2在树上解NP难问题391

10.3圆弧集着色395

10.4图的树分解401

10.5构造树分解409

带解答的练习413

练习415

注释和进一步的阅读418

第11章 近似算法419

11.1贪心算法与最优值的界限：负载均衡问题419

11.2中心选址问题423

11.3集合覆盖：一般的贪心启发式方法428

11.4定价法：顶点覆盖432

11.5用定价法最大化：不交路径问题436

11.6线性规划与舍人：对顶点覆盖的应用441

11.7再沦负载均衡：一个更高级的1P应用445

11.8任意好的近似：背包问题450

带解答的练习454

练习455

注释和进一步的阅读461

第12章 局部搜索462

12.1最优化问题的地形图462

12.2Metropo1is算法与模拟退火算法466

12.3局部搜索对Hopfie1d神经网络的应用469

12.4局部搜索对最大割近似的应用472

12.5选择邻居关系475

12.6用局部搜索分类476

12.7最佳响应动态过程与Nash平衡点482

带解答的练习489

练习491

注释和进一步的阅读493

第13章 随机算法494

13.1第一个应用：消除争用495

13.2求完全最小割498

13.3随机变量及其期望502

13.4关于MAX3-SAT的随机近似算法506

13.5随机分治策略：求中位数与快速排序509

13.6散列法：字典的随机实现514

13.7求最邻近点对：一个随机方法519

13.8随机超高速缓存525

13.9C11ernoff界531

13.10负载均衡532

13.11包路由选择534

13.12背景：某些基本概率定义539

带解答的练习544

练习547

注释和进一步的阅读554

后记：永不停止运行的算法556

索引563