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

第1章 绪论 1

1.1 算法的基本概念 2

1.1.1 算法的重要性 2

1.1.2 算法设计与分析的流程 3

1.2 算法设计与分析的重要问题类型 4

1.2.1 排序问题 4

1.2.2 查找问题 4

1.2.3 图问题 5

1.2.4 组合问题 5

1.2.5 数值问题 5

1.2.6 几何问题 6

1.3 算法复杂性分析基础 6

1.3.1 算法复杂性分析的原理 6

1.3.2 渐进符号 8

1.4 本章小结 9

1.5 习题 9

第2章 基本数据结构 11

2.1 数据结构的概念 12

2.2 线性结构 15

2.2.1 线性表 15

2.2.2 栈 18

2.2.3 队列 20

2.2.4 串 21

2.3 树形结构 23

2.3.1 树的定义与性质 23

2.3.2 二叉树 24

2.3.3 多叉树 27

2.4 图状结构 28

2.4.1 图的定义 28

2.4.2 图的存储结构 29

2.4.3 图的遍历 31

2.5 集合与字典 33

2.5.1 集合 33

2.5.2 字典 34

2.6 本章小结 35

2.7 习题 35

第3章 蛮力算法 37

3.1 算法设计思想 38

3.2 排序问题中的蛮力算法 39

3.2.1 选择排序 39

3.2.2 冒泡排序 40

3.3 查找问题中的蛮力算法 41

3.3.1 顺序查找算法 41

3.3.2 串匹配算法 42

3.4 组合问题中的蛮力算法 43

3.4.1 旅行商问题 43

3.4.2 背包问题 44

3.4.3 任务分配问题 45

3.5 几何问题中的蛮力算法 46

3.5.1 最近点对问题 46

3.5.2 凸包问题 46

3.6 本章小结 47

3.7 习题 48

第4章 分治算法 51

4.1 算法设计思想 52

4.2 排序问题中的分治算法 53

4.2.1 归并排序 53

4.2.2 快速排序 55

4.3 查找问题中的分治算法 56

4.3.1 折半查找 56

4.3.2 二叉树遍历算法 57

4.4 组合问题中的分治算法 58

4.4.1 最大子段和问题 58

4.4.2 棋盘覆盖问题 59

4.5 几何问题中的分治算法 60

4.5.1 最近点对问题 60

4.5.2 凸包问题 61

4.6 本章小结 62

4.7 习题 62

第5章 贪心算法 65

5.1 算法设计思想 66

5.1.1 贪心算法的设计思想 66

5.1.2 贪心算法的求解过程 66

5.2 图问题中的贪心算法 67

5.2.1 单源最短路径问题：Dijkstra算法 67

5.2.2 最小生成树问题：Prim算法和Kruskal算法 70

5.2.3 哈夫曼树 74

5.3 组合问题中的贪心算法 76

5.3.1 背包问题 76

5.3.2 活动安排问题 77

5.3.3 多机调度问题 78

5.4 本章小结 81

5.5 习题 81

第6章 动态规划算法 85

6.1 算法设计思想 86

6.1.1 动态规划算法的基本要素 86

6.1.2 动态规划算法的基本步骤 87

6.2 查找问题中的动态规划算法 90

6.2.1 最优二叉查找树 90

6.2.2 近似串匹配问题 92

6.3 图问题中的动态规划算法 94

6.3.1 多段图的最短路径问题 94

6.3.2 多源最短路径问题：Floyd算法 95

6.4 组合问题中的动态规划算法 97

6.4.1 0/1背包问题 97

6.4.2 最长公共子序列问题 98

6.5 本章小结 100

6.6 习题 100

第7章 回溯算法 103

7.1 算法设计思想 104

7.1.1 问题的解空间与解空间树 104

7.1.2 解空间树的动态搜索 106

7.1.3 回溯算法的求解过程 106

7.1.4 回溯算法的时间性能 107

7.2 图问题中的回溯算法 108

7.2.1 深度优先搜索 108

7.2.2 TSP问题 110

7.3 组合问题中的回溯算法 113

7.3.1 0/1背包问题 113

7.3.2 八皇后问题 117

7.3.3 图着色问题 119

7.4 本章小结 121

7.5 习题 121

第8章 分支限界算法 123

8.1 算法的设计思想 124

8.1.1 解空间树的动态搜索 124

8.1.2 分支限界算法的设计思想 126

8.1.3 分支限界算法的时间性能 128

8.2 图问题中的分支限界算法 128

8.2.1 TSP问题 128

8.2.2 单源最短路径问题 130

8.3 组合优化问题中的分支限界算法 134

8.3.1 0/1背包问题 134

8.3.2 任务分配问题 136

8.3.3 活动安排问题 139

8.4 本章小结 142

8.5 习题 142

第9章 概率算法 145

9.1 概率算法设计思想与实现基础 146

9.1.1 确定性与随机性 146

9.1.2 各种概率算法的设计思想 147

9.1.3 随机数和伪随机数 147

9.2 数值概率算法 149

9.2.1 投点法计算π值 149

9.2.2 拉普拉斯方程狄利克雷问题的求解 150

9.3 蒙特卡罗算法 151

9.3.1 蒙特卡罗算法正确率的提升 151

9.3.2 串相等性测试问题 153

9.3.3 素数性测试 154

9.4 拉斯维加斯算法 156

9.4.1 随机抽牌问题 156

9.4.2 整数因子分解 158

9.5 舍伍德算法 159

9.5.1 舍伍德型的快速排序 159

9.5.2 随机化的选择算法 160

9.6 本章小结 162

9.7 习题 162

第10章 计算智能 165

10.1 人工神经网络 166

10.1.1 思想来源和发展历程 166

10.1.2 人工神经网络的基本原理 167

10.1.3 ANN小结 170

10.2 模糊逻辑 170

10.2.1 模糊逻辑概述 170

10.2.2 模糊逻辑的基本原理 171

10.2.3 模糊逻辑技术小结 173

10.3 遗传算法 174

10.3.1 遗传算法的思想起源 174

10.3.2 遗传算法的基本原理 175

10.3.3 遗传算法的特点及其发展趋势 176

10.4 蚁群算法 177

10.4.1 蚁群算法的思想来源 177

10.4.2 蚁群优化的基本原理 178

10.4.3 蚁群优化小结 180

10.5 粒子群优化算法 181

10.5.1 粒子群优化算法的思想来源 181

10.5.2 粒子群优化算法的基本原理 181

10.5.3 粒子群优化算法的发展趋势 182

10.6 差分进化算法 183

10.6.1 差分进化概述 183

10.6.2 差分进化算法的基本原理 184

10.6.3 差分进化算法小结 185

10.7 分布估计算法 185

10.7.1 分布估计算法概述 185

10.7.2 分布估计算法的基本原理 187

10.7.3 分布估计算法的发展趋势 187

10.8 本章小结 188

10.9 习题 189

附录A 名词索引 191

索引 196

参考文献 199