算法设计与分析PDF电子书下载

1 算法概述 1

1.1 算法概念 1

1.2 算法的复杂度 5

1.3 算法设计与分析的步骤 14

1.4 算法分析举例 17

1.5 算法描述语言简介 20

小结 25

习题 25

2 常用的数学工具 27

2.1 常用的函数和公式 27

2.2 用生成函数求解递归方程 30

2.3 用特征方程求解递归方程 35

2.4 用递推方法求解递归方程 40

3 递归与分治 45

3.1 递归技术概述 45

3.2 递归算法的例子 49

3.3 递归方程的建立与求解 52

3.4 递归消除 54

3.5 分治法概述 59

3.6 分治法举例 61

小结 87

习题 87

4 贪心法 89

4.1 货币兑付问题 89

4.2 贪心算法概述 90

4.3 背包问题 93

4.4 单源最短路径问题 97

4.5 最小花费生成树问题 102

4.6 最优装载 110

4.7 哈夫曼编码 113

小结 117

习题 117

5 动态规划 119

5.1 动态规划概述 119

5.2 0/1背包问题 125

5.3 最短路径 135

5.4 多矩阵乘积 141

5.5 最长公共子序列问题 145

小结 149

习题 149

6 回溯法 151

6.1 概述 151

6.2 背包问题 160

6.3 n皇后问题 166

6.4 图的着色问题 169

6.5 哈密尔顿回路问题 173

6.6 其他常见回溯法问题 176

6.7 回溯法的效率分析 183

小结 185

习题 185

7 分支限界法 187

7.1 概述 187

7.2 复杂的有限期作业调度问题 188

7.3 货郎担问题的分支限界法 190

7.4 其他分支限界问题 193

7.5 分支限界法与回溯法的比较 207

小结 208

习题 208

8 概率算法 210

8.1 概率算法概述 210

8.2 数值概率算法 212

8.3 蒙特卡罗算法 213

8.4 其他概率算法 215

小结 219

习题 219

9 NP问题 221

9.1 NP问题概述 221

9.2 P类与NP类问题 222

9.3 NP完全问题 225

9.4 一些典型的NP完全问题 229

小结 236

习题 236

参考文献 238