算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课，越来越受到重视。本书将计算机经典问题和算法设计技术很好地结合起来，系统地介绍了算法设计技术及其在经典问题中的应用。全书共12章，第1章介绍了算法的基本概念和算法分析方法，第2章从算法的观点介绍了NP完全理论，第3章~第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术，第12章基于图灵机计算模型介绍了计算复杂性理论。每章均附有一篇阅读材料，以通俗易懂的笔触介绍了算法领域的一些最新研究成果。书中所有算法均给出了伪代码，大部分算法还给出了C++描述，书中所有问题均给出了若干应用实例。

算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课，越来越受到重视，CC2001和CCC2002都将“算法和复杂性”列为主领域，将算法设计策略、基本可计算性理论、P和NP问题类等算法设计技术和复杂性分析方法列为核心知识单元。

无论是计算科学还是计算实践，算法都在其中扮演着重要角色，算法被公认为是计算机科学的基石。翻开重要的计算机学术刊物，算法都占有一席之地，没有算法，计算机程序将不复存在。对于计算机专业的学生，学会读懂算法、设计算法，应该是一项最基本的要求，而发明算法则是计算机学者的最高境界。

提高学生的问题求解能力是高等教育的一个主要目标，在计算机科学的课程体系中，安排一门关于算法设计与分析的课程是非常必要的，因为这门课程能够引导学生的思维过程，告诉学生如何应用一些特定的算法设计策略来解决问题。学习算法还能够提高学生分析问题的能力。算法可以看作是解决问题的一类特殊方法——它不是问题的答案，而是经过精确定义的、用来获得答案的求解过程。因此，无论是否涉及计算机，特定的算法设计技术都可以看作是问题求解的有效策略。

本书将计算机经典问题和算法设计技术很好地结合起来，系统地介绍了算法设计技术及其在经典问题中的应用。通过同一算法设计技术在不同问题中的应用进行比较，牢固掌握算法设计技术的基本策略；通过不同的算法设计技术在同一问题中的应用进行比较，更容易体会到算法设计技术的思想方法，收到融会贯通的效果。所以，本书采用了模块化的设计思想，读者除了按本书组织的章节学习外，还可以将每种算法设计技术的问题提取出来，比较解决相同问题的不同解决方法。随着本书内容的不断展开，读者也将感受到综合应用多种算法设计技术有时可以更有效地解决问题。

全书共12章，第1章介绍了算法的基本概念和算法分析方法，第2章从算法的观点非形式化地介绍了NP完全理论，第3章~第11章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术，第12章基于图灵机计算模型介绍了计算复杂性理论。

书中所有问题均给出了若干应用实例，每章还设有一个实验项目，通过设计提高学生创造性思维的培养。每章均附有一篇阅读材料，以通俗易懂的笔触介绍了算法领域的一些最新研究成果，保证知识的先进性。书中所有算法均给出了伪代码，大部分算法还给出了C++描述。在算法介绍上，注重对问题求解过程的理解，注重算法设计思路和分析过程的讲解，体现了“授之以渔”的教学理念。

王涛老师收集和整理了本书的阅读材料，参加本书编写的还有胡明、许建潮、孙卫佳、逄焕利、刘钢、陈志雨等老师，研究生张倩、魏卓调试了本书的全部算法。算法设计与分析

由于作者的知识和写作水平有限，书稿虽几经修改，仍难免有缺点和错误。热忱欢迎同行专家和读者批评指正，使本书在使用中不断改进、日臻完善。

作者2006年2月

第1章绪论1

1.1算法的基本概念1

1.1.1为什么要学习算法1

1.1.2算法及其重要特性3

1.1.3算法的描述方法4

1.1.4算法设计的一般过程5

1.1.5重要的问题类型8

1.2算法分析10

1.2.1渐进符号10

1.2.2最好、最坏和平均情况12

1.2.3非递归算法的分析13

1.2.4递归算法的分析14

1.2.5算法的后验分析16

1.3实验项目——求最大公约数18

阅读材料——人工神经网络与BP算法19

习题121

第2章NP完全理论25

2.1下界25

2.1.1平凡下界26

2.1.2判定树模型26

2.1.3最优算法27

2.2算法的极限28

2.2.1易解问题与难解问题28

2.2.2实际问题难以求解的原因30

2.2.3不可解问题32

2.3P类问题和NP类问题34

2.3.1判定问题34

2.3.2确定性算法与P类问题35

2.3.3非确定性算法与NP类问题35

2.4NP完全问题36

2.4.1问题变换与计算复杂性归约37

2.4.2NP完全问题的定义38

2.4.3基本的NP完全问题40

2.4.4NP完全问题的计算机处理41

2.5实验项目——SAT问题43

阅读材料——遗传算法43

习题247算法设计与分析

第3章蛮力法49

3.1蛮力法的设计思想49

3.2查找问题中的蛮力法50

3.2.1顺序查找50

3.2.2串匹配问题52

3.3排序问题中的蛮力法56

3.3.1选择排序56

3.3.2起泡排序57

3.4组合问题中的蛮力法58

3.4.1生成排列对象58

3.4.2生成子集58

3.4.30/1背包问题59

3.4.4任务分配问题59

3.5图问题中的蛮力法61

3.5.1哈密顿回路问题61

3.5.2TSP问题62

3.6几何问题中的蛮力法63

3.6.1最近对问题63

3.6.2凸包问题64

3.7实验项目——串匹配问题65

阅读材料——蚁群算法67

习题370

第4章分治法73

4.1概述73

4.1.1分治法的设计思想73

4.1.2分治法的求解过程74

4.2递归75

4.2.1递归的定义75

4.2.2递归函数的运行轨迹77

4.2.3递归函数的内部执行过程77

4.3排序问题中的分治法78

4.3.1归并排序78

4.3.2快速排序80

4.4组合问题中的分治法83

4.4.1最大子段和问题83

4.4.2棋盘覆盖问题85

4.4.3循环赛日程安排问题87

4.5几何问题中的分治法88

4.5.1最近对问题89

4.5.2凸包问题90

4.6实验项目——最近对问题91

阅读材料——鱼群算法92

习题495

第5章减治法97

5.1减治法的设计思想97

5.2查找问题中的减治法98

5.2.1折半查找98

5.2.2二叉查找树100

5.3排序问题中的减治法101

5.3.1堆排序101

5.3.2选择问题105

5.4组合问题中的减治法106

5.4.1淘汰赛冠军问题106

5.4.2假币问题107

5.5实验项目——8枚硬币问题109

阅读材料——粒子群算法109

习题5112

第6章动态规划法115

6.1概述115

6.1.1最优化问题115

6.1.2最优性原理116

6.1.3动态规划法的设计思想117

6.2图问题中的动态规划法119

6.2.1TSP问题119

6.2.2多段图的最短路径问题121

6.3组合问题中的动态规划法123

6.3.10/1背包问题123

6.3.2最长公共子序列问题126

6.4查找问题中的动态规划法128

6.4.1最优二叉查找树128

6.4.2近似串匹配问题132

6.5实验项目——最大子段和问题134

阅读材料——文化算法135

习题6137

第7章贪心法139

7.1概述139

7.1.1贪心法的设计思想139

7.1.2贪心法的求解过程140

7.2图问题中的贪心法141

7.2.1TSP问题141

7.2.2图着色问题144

7.2.3最小生成树问题145

7.3组合问题中的贪心法148

7.3.1背包问题148

7.3.2活动安排问题151

7.3.3多机调度问题153

7.4实验项目——霍夫曼编码155

阅读材料——模拟退火算法157

习题7159

第8章回溯法161

8.1概述161

8.1.1问题的解空间161

8.1.2解空间树的动态搜索（1）163

8.1.3回溯法的求解过程165

8.1.4回溯法的时间性能166

8.2图问题中的回溯法168

8.2.1图着色问题168

8.2.2哈密顿回路问题170

8.3组合问题中的回溯法173

8.3.1八皇后问题173

8.3.2批处理作业调度问题175

8.4实验项目——0/1背包问题177

阅读材料——禁忌搜索算法178

习题8180

第9章分支限界法183

9.1概述183

9.1.1解空间树的动态搜索（2）183

9.1.2分支限界法的设计思想186

9.1.3分支限界法的时间性能188

9.2图问题中的分支限界法188

9.2.1TSP问题188

9.2.2多段图的最短路径问题192

9.3组合问题中的分支限界法195

9.3.1任务分配问题195

9.3.2批处理作业调度问题198

9.4实验项目——电路布线问题200

阅读材料——免疫算法201

习题9203

第10章概率算法205

10.1概述205

10.1.1概率算法的设计思想206

10.1.2随机数发生器207

10.2舍伍德(Sherwood)型概率算法207

10.2.1快速排序208

10.2.2选择问题209

10.3拉斯维加斯(Las Vegas)型概率算法210

10.3.1八皇后问题211

10.3.2整数因子分解问题212

10.4蒙特卡罗(Monte Carlo)型概率算法214

10.4.1主元素问题215

10.4.2素数测试问题216

10.5实验项目——随机数发生器218

阅读材料——DNA计算与DNA计算机219

习题10221

第11章近似算法223

11.1概述223

11.1.1近似算法的设计思想223

11.1.2近似算法的性能224

11.2图问题中的近似算法225

11.2.1顶点覆盖问题225

11.2.2TSP问题226

11.3组合问题中的近似算法228

11.3.1装箱问题228

11.3.2子集和问题231

11.4实验项目——TSP问题的近似算法235

阅读材料——量子密码技术235

习题11237

第12章计算复杂性理论239

12.1计算模型239

12.1.1图灵机的基本模型240

12.1.2k带图灵机和时间复杂性241

12.1.3离线图灵机和空间复杂性244

12.2P类问题和NP类问题245

12.2.1非确定性图灵机245

12.2.2P类语言和NP类语言246

12.3NP完全问题247

12.3.1多项式时间变换247

12.3.2Cook定理248

12.4实验项目——NP完全问题树251

阅读材料——算法优化策略251

习题12254

参考文献255