第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