算法设计PDF电子书下载

第1章 算法概述 1

1.1问题、算法和程序 1

1.2两个典型问题的求解 3

1.2.1排序问题 3

1.2.2稳定匹配问题 4

1.3算法的复杂度分析 7

1.4小结 8

习题1 8

第2章 基本数据结构 10

2.1链表 10

2.1.1普通链表 10

2.1.2泛型链表 13

2.1.3双向链表 15

2.2堆栈和队列 15

2.2.1堆栈 15

2.2.2队列 17

2.2.3优先级队列 18

2.3树 19

2.3.1树 19

2.3.2二叉树 20

2.3.3堆 22

2.4图 24

2.4.1图的基本概念 24

2.4.2图的存储方式 25

2.5小结 26

习题2 27

第3章 蛮力法 28

3.1字符串匹配 28

3.2矩阵相乘 29

3.3子集和问题 30

3.4冒泡排序 30

3.5若干最优化问题 31

3.5.1最近点对问题 32

3.5.2 0-1背包问题 33

3.5.3子集和问题的最优化版本 34

3.5.4最大独立集和最小顶点覆盖 35

3.5.5旅行商问题 37

3.6小结 38

习题3 38

第4章 递归和分治法 40

4.1递归 40

4.1.1递归的基本概念 40

4.1.2递归算法的效率分析 42

4.1.3汉诺塔问题 43

4.1.4幂集和全排列 45

4.2树和图中的一些递归问题 47

4.2.1二叉树的遍历 47

4.2.2图的遍历 48

4.3分治法的基本思想 49

4.4最近点对问题的分治算法 51

4.5归并排序和快速排序 52

4.5.1归并排序 52

4.5.2快速排序 54

4.6大数乘法和Strassen矩阵乘法 56

4.6.1大数乘法 56

4.6.2 Strassen矩阵乘法 57

4.7小结 58

习题4 58

第5章 动态规划法 60

5.1动态规划法的基本思想 60

5.1.1重叠子问题 60

5.1.2最优性原则 61

5.2计算二项式系数 63

5.3最长连续上升子序列问题 64

5.4最大子段和 65

5.4.1一维数组的最大子段和 65

5.4.2二维数组的最大子段和 66

5.5序列比较 67

5.5.1最长公共子序列问题 67

5.5.2序列比对问题 69

5.6矩阵连乘问题 71

5.7图中的路径 73

5.7.1 Floyd算法 73

5.7.2 Warshall算法 74

5.7.3 Kleen抽象算法 75

5.8多阶段决策问题 76

5.9动态规划的备忘录方法 78

5.10小结 80

习题5 80

第6章 贪心法 82

6.1找零钱问题 82

6.2最大数量装载问题 83

6.3最小生成树 84

6.3.1 Prim算法 85

6.3.2 Kruskal算法 87

6.3.3破圈算法 88

6.4单源最短路径 89

6.5往返运输问题 92

6.6区间活动安排问题 94

6.7单位时间任务调度问题 95

6.8哈夫曼树 97

6.9小结 101

习题6 101

第7章 回溯和分支限界 103

7.1回溯和分支限界法的基本思想 103

7.1.1状态空间 103

7.1.2状态空间树与搜索策略 103

7.1.3剪枝函数 104

7.2 0-1背包问题 106

7.2.1定义剪枝函数 106

7.2.2回溯算法 109

7.2.3分支限界算法 110

7.3旅行商问题 111

7.3.1回溯算法 112

7.3.2分支限界算法 113

7.4图着色问题 113

7.5 N皇后问题 117

7.6任务分配问题 119

7.7小结 121

习题7 122

第8章 迭代改进法 123

8.1线性规划与单纯形法 123

8.1.1线性规划问题 123

8.1.2线性规划的几何意义 125

8.1.3单纯形法 127

8.2二部图匹配问题 130

8.3最大流 133

8.3.1流网络 133

8.3.2最大流问题 134

8.3.3最小割问题 137

8.4小结 139

习题8 139

第9章 计算复杂性与NP理论 141

9.1多项式时间归约 141

9.2计算模型 143

9.2.1形式语言与问题编码 143

9.2.2图灵机模型 143

9.2.3不确定性图灵机 145

9.2.4图灵机与可计算性 146

9.3计算复杂性分类——P和NP 147

9.3.1 P类问题 147

9.3.2 NP类问题 147

9.4 NP完全问题 148

9.4.1第一个NP完全问题 149

9.4.2 NP完全性的证明 150

9.4.3更多的NP完全问题 151

9.5小结 155

习题9 156

第10章 近似算法 158

10.1绝对近似算法——平面图着色 158

10.2相对近似算法——常数近似比 161

10.2.1顶点覆盖问题 161

10.2.2最短工期问题 162

10.2.3旅行商问题 164

10.2.4反馈集问题 166

10.3相对近似算法——函数近似比 167

10.3.1无重合路径问题 168

10.3.2集合覆盖问题 169

10.4相对近似算法——任意近似比 171

10.4.1 0-1背包问题的PTAS 171

10.4.2子集和问题的FPTAS 174

10.5小结 175

习题10 175

第11章 参数化算法 178

11.1顶点覆盖问题的参数化算法 178

11.1.1参数化问题与搜索树方法 178

11.1.2问题简约：消除高度数顶点 180

11.1.3增强的问题简约与搜索树方法 181

11.2反馈集问题的参数化算法 184

11.2.1问题简约 185

11.2.2搜索树方法 186

11.2.3改进的搜索树方法 186

11.3支配集问题的参数化算法 188

11.4参数化的计算复杂性框架 189

11.5小结 190

习题11 190

第12章 随机算法 192

12.1随机算法的基本概念 192

12.1.1近似计算圆周率的随机算法 192

12.1.2随机数的生成 193

12.1.3抛硬币问题 194

12.2舍伍德算法 194

12.2.1随机化快速排序 194

12.2.2有序链表搜索 195

12.3蒙特卡洛算法 197

12.3.1众数问题 197

12.3.2素数判定问题 198

12.4拉斯维加斯算法 200

12.4.1随机取样问题 201

12.4.2 N皇后问题 202

12.4.3大整数分解问题 204

12.5小结 205

习题12 205

第13章 现代优化算法 207

13.1禁忌搜索 207

13.1.1禁忌搜索的基本思想 207

13.1.2禁忌搜索算法框架与应用 208

13.2模拟退火 210

13.2.1模拟退火算法的基本思想 210

13.2.2模拟退火算法框架与应用 211

13.3遗传算法 212

13.3.1遗传算法的基本思想 212

13.3.2遗传算法框架与应用 214

13.3.3遗传算法的其他变种 216

13.4蚁群算法 217

13.4.1蚁群算法的基本思想 217

13.4.2蚁群算法框架与应用 218

13.5粒子群算法 220

13.5.1粒子群算法的基本思想 220

13.5.2粒子群算法框架与应用 221

13.5.3粒子群算法的其他变种 222

13.6差分进化算法 222

13.6.1差分进化算法的基本思想 222

13.6.2差分进化算法框架与应用 223

13.6.3差分进化算法的其他变种 224

13.7小结 224

习题13 225

附录A伪代码语法规则 226