算法设计与分析

第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

习题1 21

第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.3 p类问题和np类问题34

2.3.1 判定问题34

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

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

2.4 np完全问题36

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

2.4.2 np完全问题的定义38

2.4.3 基本的np完全问题40

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

2.5 实验项目——sat问题43

阅读材料——遗传算法43

习题2 47

第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.3 0/1背包问题59

3.4.4 任务分配问题59

3.5 图问题中的蛮力法61

3.5.1 哈密顿回路问题61

3.5.2 tsp问题62

3.6 几何问题中的蛮力法63

3.6.1 最近对问题63

3.6.2 凸包问题64

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

阅读材料——蚁群算法67

习题3 70

第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

习题4 95

第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

习题5 112

第6章 动态规划法115

6.1 概述115

6.1.1 最优化问题115

6.1.2 最优性原理116

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

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

6.2.1 tsp问题119

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

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

6.3.1 0/1背包问题..123

6.3.2 最长公共子序列问题126

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

6.4.1 最优二叉查找树128

6.4.2 近似串匹配问题132

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

阅读材料——文化算法135

习题6 137

第7章 贪心法139

7.1 概述139

7.1.1 贪心法的设计思想139

7.1.2 贪心法的求解过程140

7.2 图问题中的贪心法141

7.2.1 tsp问题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

习题7 159

第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

习题8 180

第9章 分支限界法183

9.1 概述183

9.1.1 解空间树的动态搜索(2)183

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

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

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

9.2.1 tsp问题188

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

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

9.3.1 任务分配问题195

9.3.2 批处理作业调度问题198

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

阅读材料——免疫算法201

习题9 203

第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

习题10 221

第11章 近似算法223

11.1 概述223

11.1.1 近似算法的设计思想223

11.1.2 近似算法的性能224

11.2 图问题中的近似算法225

11.2.1 顶点覆盖问题225

11.2.2 tsp问题226

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

11.3.1 装箱问题228

11.3.2 子集和问题231

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

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

习题11 237

第12章 计算复杂性理论239

12.1 计算模型239

12.1.1 图灵机的基本模型240

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

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

12.2 p类问题和np类问题245

12.2.1 非确定性图灵机245

12.2.2 p类语言和np类语言246

12.3 np完全问题247

12.3.1 多项式时间变换247

12.3.2 cook定理248

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

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

习题12 254

参考文献...255