- 机械工业出版社
- 9787111746591
- 2-1
- 47269877-8
- 16开
- 2024-04-28
- 工学
- 电子信息类
- 人工智能
- 本科
内容简介
本书作者根据自己20多年的教学与科研实践，系统地总结了计算机算法的设计与分析方法，覆盖了大部分主要的算法技术，包括：分治法、贪心法、动态规划、图的遍历技术、穷举搜索等，涉及一系列重要的算法问题，包括排序问题、选择问题、生成树问题、网络流问题、二分图的匹配问题、字符串的匹配问题和几何算法问题等，还介绍了问题本身的计算复杂性的概念和NP完全问题的理论等。
目录
目 录
前言
教学建议
第1章 概述 1
1.1 算法与数据结构及程序的关系 1
1.1.1 什么是算法 1
1.1.2 算法与数据结构的关系 1
1.1.3 算法与程序的关系 2
1.1.4 选择排序的例子 2
1.1.5 算法的伪码表示 2
1.2 算法复杂度分析 3
1.2.1 算法复杂度的度量 3
1.2.2 算法复杂度与输入数据规模的关系 4
1.2.3 输入数据规模的度量模型 4
1.2.4 算法复杂度分析中的两个简化假设 5
1.2.5 最好情况、最坏情况和平均情况
的复杂度分析 5
1.3 函数增长渐近性态的比较 6
1.3.1 三种比较关系及O、、记号 6
1.3.2 表示算法复杂度的常用函数 7
1.4 问题复杂度与算法复杂度的关系 9
1.4.1 问题复杂度是算法复杂度的
下界 9
1.4.2 问题复杂度与最佳算法 9
1.4.3 易处理问题和难处理问题 9
习题 10
第2章 分治法 11
2.1 分治法原理 11
2.1.1 二元搜索的例子 11
2.1.2 表示复杂度的递推关系 12
2.2 递推关系求解 13
2.2.1 替换法 13
2.2.2 序列求和法与递归树法 15
2.2.3 常用序列和公式 16
2.2.4 主方法求解 18
2.3 例题示范 19
习题 20
第3章 基于比较的排序算法 24
3.1 插入排序 24
3.1.1 插入排序的算法 24
3.1.2 插入排序算法的复杂度分析 25
3.1.3 插入排序的优缺点 26
3.2 合并排序 26
3.2.1 合并算法及其复杂度 26
3.2.2 合并排序的算法及其复杂度 27
3.2.3 合并排序的优缺点 29
3.3 堆排序 30
3.3.1 堆的数据结构 30
3.3.2 堆的修复算法及其复杂度 31
3.3.3 为输入数据建堆 32
3.3.4 堆排序算法 33
3.3.5 堆排序算法的复杂度 34
3.3.6 堆排序算法的优缺点 35
3.3.7 堆用作优先队列 35
3.4 快排序 36
3.4.1 快排序算法 36
3.4.2 快排序算法最坏情况复杂度 39
3.4.3 快排序算法平均情况复杂度 40
3.4.4 快排序算法最好情况复杂度 41
3.4.5 快排序算法的优缺点 42
习题 42
第4章 不基于比较的排序算法 46
4.1 比较排序的下界 46
4.1.1 决策树模型及排序最坏情况下界 46
4.1.2 二叉树的外路径总长与排序平均
情况下界 49
4.1.3 二叉树的全路径总长与堆排序
最好情况下界 51
4.2 不基于比较的线性时间排序算法 54
4.2.1 计数排序 54
4.2.2 基数排序 57
4.2.3 桶排序 58
习题 60
第5章 中位数和任一顺序数的选择 63
5.1 问题定义 63
5.2 最大数和最小数的选择 63
5.2.1 最大和最小顺序数的选择算法及
其复杂度 64
5.2.2 同时找出最大数和最小数的
算法 65
5.3 线性时间找出任一顺序数的算法 66
5.3.1 最坏情况复杂度为O(n)的算法 66
5.3.2 平均情况复杂度为O(n)的算法 68
5.4 找出k个最大顺序数的算法 69
5.4.1 一个理论联系实际的问题 69
5.4.2 利用堆来找k个最大顺序数的
算法 70
5.4.3 利用锦标赛树来找k个最大顺序数
的算法 70
习题 71
第6章 动态规划 73
6.1 动态规划的基本原理 73
6.2 矩阵连乘问题 75
6.2.1 定义子问题 75
6.2.2 归纳公式 77
6.2.3 算法伪码和例子 78
6.3 最长公共子序列问题 81
6.3.1 定义子问题 81
6.3.2 归纳公式 82
6.3.3 算法伪码和例子 82
6.4 最佳二元搜索树问题 84
6.4.1 定义子问题和归纳公式 85
6.4.2 算法伪码和例子 87
6.5 多级图及其应用 89
6.6 最长递增子序列问题 92
6.6.1 定义子问题 93
6.6.2 归纳公式 93
6.6.3 算法伪码和例子 93
习题 95
第7章 贪心算法 103
7.1 最佳邮局设置问题 103
7.2 一个简单的最佳活动安排问题 105
7.3 其他最佳活动安排问题 106
7.3.1 两个大礼堂的最佳活动安排
问题 106
7.3.2 等长时间的活动的最佳安排
问题 109
7.4 哈夫曼编码问题 112
7.4.1 前缀码 112
7.4.2 最佳前缀码——哈夫曼编码 114
7.5 最佳加油计划问题 118
7.5.1 最佳加油计划问题的描述 118
7.5.2 贪心算法的基本思路 119
7.5.3 贪心算法的伪码 120
习题 121
第8章 图的周游算法 128
8.1 图的表示 128
8.1.1 邻接表 129
8.1.2 邻接矩阵 129
8.2 广度优先搜索及应用 130
8.2.1 广度优先搜索策略 130
8.2.2 广度优先搜索算法及距离树 131
8.2.3 无向图的二着色问题 133
8.3 深度优先搜索及应用 136
8.3.1 深度优先搜索的策略 136
8.3.2 深度优先搜索算法和深度优先
搜索树 137
8.3.3 深度优先搜索算法举例和图中
边的分类 140
8.3.4 拓扑排序 141
8.3.5 无回路有向图中最长路径问题
及应用 144
8.3.6 有向图的强连通分支的分解 146
8.3.7 无向图的双连通分支的分解 150
习题 156
第9章 图的最小支撑树 162
9.1 计算最小支撑树的一个通用的
贪心算法策略 163
9.2 Kruskal 算法 165
9.3 Prim 算法 168
习题 173
第10章 单源最短路径 178
10.1 Dijkstra 算法 179
10.2 Bellman-Ford 算法 184
习题 189
第11章 网络流 192
11.1 网络模型和最大网络流问题 192
11.2 网络中的流与割的关系 196
11.2.1 网络中的割及其容量 197
11.2.2 剩余网络和增广路径 198
11.2.3 最大流最小割定理 201
11.3 Ford-Fulkerson 算法 202
11.3.1 Ford-Fulkerson 的通用算法 202
11.3.2 Edmonds-Karp 算法 204
11.3.3 Dinic 算法 207
11.4 二部图的匹配问题 210
11.4.1 0-1网络的最大流问题 211
11.4.2 用网络流求二部图的最大匹配
的算法 212
11.4.3 Philip Hall 婚配定理 214
11.4.4 Birkhoff-von Neumann 定理 215
11.5 推进-重标号算法简介 217
11.5.1 预流和高度函数 217
11.5.2 在剩余网络中对顶点的两个
操作 219
11.5.3 推进-重标号算法的初始化 220
11.5.4 推进-重标号的通用算法 220
11.5.5 推进-重标号的通用算法的复杂
度分析 223
习题 224
第12章 计算几何基础 228
12.1 平面线段及相互关系 228
12.1.1 向量的点积和叉积 229
12.1.2 平面线段的相互关系 230
12.2 平扫线技术和线段相交的确定 233
12.2.1 平扫线的状态和事件点 234
12.2.2 用平扫线确定线段相交的
算法 235
12.3 平面点集的凸包 237
12.3.1 Graham 扫描法 238
12.3.2 Jarvis行进法 243
12.4 最近点对问题 245
12.4.1 预备工作和分治法的底 245
12.4.2 分治法的分 246
12.4.3 分治法的合 247
12.4.4 分治法的伪码 248
习题 249
第13章 字符串匹配 252
13.1 一个朴素的字符串匹配算法 252
13.2 Rabin-Karp 算法 253
13.3 基于有限状态自动机的匹配
算法 255
13.3.1 有限状态自动机简介 255
13.3.2 字符串匹配用的自动机 256
13.3.3 基于有限状态自动机的匹配
算法 259
13.4 Knuth-Morris-Pratt (KMP) 算法 260
13.4.1 模式的前缀函数 260
13.4.2 基于前缀函数的KMP 算法 263
习题 265
第14章 NP 完全问题 266
14.1 预备知识 267
14.1.1 图灵机 267
14.1.2 符号集和编码对计算复杂度的
影响 268
14.1.3 判断型问题和优化型问题及其
关系 268
14.1.4 判断型问题的形式语言表示 270
14.1.5 多项式关联和多项式归约 271
14.2 P和NP语言类 272
14.2.1 非确定图灵机和NP语言类 273
14.2.2 多项式检验算法和NP类语言的
关系 274
14.3 NPC语言类和NPC问题 276
14.3.1 第一个NPC问题 277
14.3.2 若干著名NPC问题的证明 281
习题 295
第15章 近似算法 301
15.1 近似算法的性能评价 301
15.2 顶点覆盖问题 302
15.3 货郎担问题 303
15.3.1 满足三角不等式的货郎担
问题 304
15.3.2 无三角不等式关系的一般
货郎担问题 307
15.4 集合覆盖问题 307
15.5 MAX-3-SAT问题 310
15.6 加权的顶点覆盖问题 311
15.7 子集和问题 313
15.7.1 一个保证最优解的指数型算法 313
15.7.2 子集和问题的一个完全多项式
近似机制 314
*15.8 鸿沟定理和不可近似性 317
15.8.1 鸿沟定理 318
15.8.2 任务均匀分配问题 319
习题 321
第16章 穷举搜索 324
16.1 问题及方法的描述 324
16.2 回溯法 326
16.2.1 回溯法的通用算法 326
16.2.2 n皇后问题 327
16.2.3 子集和问题 328
16.2.4 回溯法的效率估计 330
16.3 分支限界法 331
16.3.1 分支限界法解n皇后问题 332
16.3.2 0/1背包问题 334
16.4 博弈树和α-β剪枝 340
16.4.1 博弈树及其评估的方法 340
16.4.2 α-β剪枝法 344
习题 346
第17章 平摊分析和斐波那契堆 348
17.1 平摊分析的常用方法 349
17.1.1 聚集法 349
17.1.2 记账法 350
17.1.3 势能法 352
17.2 动态表格 353
17.2.1 只允许扩张的动态表格 353
17.2.2 扩张和收缩都有的动态表格 355
17.3 斐波那契堆 358
17.3.1 斐波那契堆的构造 358
17.3.2 可合并堆的操作 360
17.3.3 减小一个关键字和删除任一结点
的操作 365
17.3.4 最大度数的界 367
习题 369
附录A 红黑树 372
附录B 用于分离集合操作的数据
结构 385
参考文献 397
前言
教学建议
第1章 概述 1
1.1 算法与数据结构及程序的关系 1
1.1.1 什么是算法 1
1.1.2 算法与数据结构的关系 1
1.1.3 算法与程序的关系 2
1.1.4 选择排序的例子 2
1.1.5 算法的伪码表示 2
1.2 算法复杂度分析 3
1.2.1 算法复杂度的度量 3
1.2.2 算法复杂度与输入数据规模的关系 4
1.2.3 输入数据规模的度量模型 4
1.2.4 算法复杂度分析中的两个简化假设 5
1.2.5 最好情况、最坏情况和平均情况
的复杂度分析 5
1.3 函数增长渐近性态的比较 6
1.3.1 三种比较关系及O、、记号 6
1.3.2 表示算法复杂度的常用函数 7
1.4 问题复杂度与算法复杂度的关系 9
1.4.1 问题复杂度是算法复杂度的
下界 9
1.4.2 问题复杂度与最佳算法 9
1.4.3 易处理问题和难处理问题 9
习题 10
第2章 分治法 11
2.1 分治法原理 11
2.1.1 二元搜索的例子 11
2.1.2 表示复杂度的递推关系 12
2.2 递推关系求解 13
2.2.1 替换法 13
2.2.2 序列求和法与递归树法 15
2.2.3 常用序列和公式 16
2.2.4 主方法求解 18
2.3 例题示范 19
习题 20
第3章 基于比较的排序算法 24
3.1 插入排序 24
3.1.1 插入排序的算法 24
3.1.2 插入排序算法的复杂度分析 25
3.1.3 插入排序的优缺点 26
3.2 合并排序 26
3.2.1 合并算法及其复杂度 26
3.2.2 合并排序的算法及其复杂度 27
3.2.3 合并排序的优缺点 29
3.3 堆排序 30
3.3.1 堆的数据结构 30
3.3.2 堆的修复算法及其复杂度 31
3.3.3 为输入数据建堆 32
3.3.4 堆排序算法 33
3.3.5 堆排序算法的复杂度 34
3.3.6 堆排序算法的优缺点 35
3.3.7 堆用作优先队列 35
3.4 快排序 36
3.4.1 快排序算法 36
3.4.2 快排序算法最坏情况复杂度 39
3.4.3 快排序算法平均情况复杂度 40
3.4.4 快排序算法最好情况复杂度 41
3.4.5 快排序算法的优缺点 42
习题 42
第4章 不基于比较的排序算法 46
4.1 比较排序的下界 46
4.1.1 决策树模型及排序最坏情况下界 46
4.1.2 二叉树的外路径总长与排序平均
情况下界 49
4.1.3 二叉树的全路径总长与堆排序
最好情况下界 51
4.2 不基于比较的线性时间排序算法 54
4.2.1 计数排序 54
4.2.2 基数排序 57
4.2.3 桶排序 58
习题 60
第5章 中位数和任一顺序数的选择 63
5.1 问题定义 63
5.2 最大数和最小数的选择 63
5.2.1 最大和最小顺序数的选择算法及
其复杂度 64
5.2.2 同时找出最大数和最小数的
算法 65
5.3 线性时间找出任一顺序数的算法 66
5.3.1 最坏情况复杂度为O(n)的算法 66
5.3.2 平均情况复杂度为O(n)的算法 68
5.4 找出k个最大顺序数的算法 69
5.4.1 一个理论联系实际的问题 69
5.4.2 利用堆来找k个最大顺序数的
算法 70
5.4.3 利用锦标赛树来找k个最大顺序数
的算法 70
习题 71
第6章 动态规划 73
6.1 动态规划的基本原理 73
6.2 矩阵连乘问题 75
6.2.1 定义子问题 75
6.2.2 归纳公式 77
6.2.3 算法伪码和例子 78
6.3 最长公共子序列问题 81
6.3.1 定义子问题 81
6.3.2 归纳公式 82
6.3.3 算法伪码和例子 82
6.4 最佳二元搜索树问题 84
6.4.1 定义子问题和归纳公式 85
6.4.2 算法伪码和例子 87
6.5 多级图及其应用 89
6.6 最长递增子序列问题 92
6.6.1 定义子问题 93
6.6.2 归纳公式 93
6.6.3 算法伪码和例子 93
习题 95
第7章 贪心算法 103
7.1 最佳邮局设置问题 103
7.2 一个简单的最佳活动安排问题 105
7.3 其他最佳活动安排问题 106
7.3.1 两个大礼堂的最佳活动安排
问题 106
7.3.2 等长时间的活动的最佳安排
问题 109
7.4 哈夫曼编码问题 112
7.4.1 前缀码 112
7.4.2 最佳前缀码——哈夫曼编码 114
7.5 最佳加油计划问题 118
7.5.1 最佳加油计划问题的描述 118
7.5.2 贪心算法的基本思路 119
7.5.3 贪心算法的伪码 120
习题 121
第8章 图的周游算法 128
8.1 图的表示 128
8.1.1 邻接表 129
8.1.2 邻接矩阵 129
8.2 广度优先搜索及应用 130
8.2.1 广度优先搜索策略 130
8.2.2 广度优先搜索算法及距离树 131
8.2.3 无向图的二着色问题 133
8.3 深度优先搜索及应用 136
8.3.1 深度优先搜索的策略 136
8.3.2 深度优先搜索算法和深度优先
搜索树 137
8.3.3 深度优先搜索算法举例和图中
边的分类 140
8.3.4 拓扑排序 141
8.3.5 无回路有向图中最长路径问题
及应用 144
8.3.6 有向图的强连通分支的分解 146
8.3.7 无向图的双连通分支的分解 150
习题 156
第9章 图的最小支撑树 162
9.1 计算最小支撑树的一个通用的
贪心算法策略 163
9.2 Kruskal 算法 165
9.3 Prim 算法 168
习题 173
第10章 单源最短路径 178
10.1 Dijkstra 算法 179
10.2 Bellman-Ford 算法 184
习题 189
第11章 网络流 192
11.1 网络模型和最大网络流问题 192
11.2 网络中的流与割的关系 196
11.2.1 网络中的割及其容量 197
11.2.2 剩余网络和增广路径 198
11.2.3 最大流最小割定理 201
11.3 Ford-Fulkerson 算法 202
11.3.1 Ford-Fulkerson 的通用算法 202
11.3.2 Edmonds-Karp 算法 204
11.3.3 Dinic 算法 207
11.4 二部图的匹配问题 210
11.4.1 0-1网络的最大流问题 211
11.4.2 用网络流求二部图的最大匹配
的算法 212
11.4.3 Philip Hall 婚配定理 214
11.4.4 Birkhoff-von Neumann 定理 215
11.5 推进-重标号算法简介 217
11.5.1 预流和高度函数 217
11.5.2 在剩余网络中对顶点的两个
操作 219
11.5.3 推进-重标号算法的初始化 220
11.5.4 推进-重标号的通用算法 220
11.5.5 推进-重标号的通用算法的复杂
度分析 223
习题 224
第12章 计算几何基础 228
12.1 平面线段及相互关系 228
12.1.1 向量的点积和叉积 229
12.1.2 平面线段的相互关系 230
12.2 平扫线技术和线段相交的确定 233
12.2.1 平扫线的状态和事件点 234
12.2.2 用平扫线确定线段相交的
算法 235
12.3 平面点集的凸包 237
12.3.1 Graham 扫描法 238
12.3.2 Jarvis行进法 243
12.4 最近点对问题 245
12.4.1 预备工作和分治法的底 245
12.4.2 分治法的分 246
12.4.3 分治法的合 247
12.4.4 分治法的伪码 248
习题 249
第13章 字符串匹配 252
13.1 一个朴素的字符串匹配算法 252
13.2 Rabin-Karp 算法 253
13.3 基于有限状态自动机的匹配
算法 255
13.3.1 有限状态自动机简介 255
13.3.2 字符串匹配用的自动机 256
13.3.3 基于有限状态自动机的匹配
算法 259
13.4 Knuth-Morris-Pratt (KMP) 算法 260
13.4.1 模式的前缀函数 260
13.4.2 基于前缀函数的KMP 算法 263
习题 265
第14章 NP 完全问题 266
14.1 预备知识 267
14.1.1 图灵机 267
14.1.2 符号集和编码对计算复杂度的
影响 268
14.1.3 判断型问题和优化型问题及其
关系 268
14.1.4 判断型问题的形式语言表示 270
14.1.5 多项式关联和多项式归约 271
14.2 P和NP语言类 272
14.2.1 非确定图灵机和NP语言类 273
14.2.2 多项式检验算法和NP类语言的
关系 274
14.3 NPC语言类和NPC问题 276
14.3.1 第一个NPC问题 277
14.3.2 若干著名NPC问题的证明 281
习题 295
第15章 近似算法 301
15.1 近似算法的性能评价 301
15.2 顶点覆盖问题 302
15.3 货郎担问题 303
15.3.1 满足三角不等式的货郎担
问题 304
15.3.2 无三角不等式关系的一般
货郎担问题 307
15.4 集合覆盖问题 307
15.5 MAX-3-SAT问题 310
15.6 加权的顶点覆盖问题 311
15.7 子集和问题 313
15.7.1 一个保证最优解的指数型算法 313
15.7.2 子集和问题的一个完全多项式
近似机制 314
*15.8 鸿沟定理和不可近似性 317
15.8.1 鸿沟定理 318
15.8.2 任务均匀分配问题 319
习题 321
第16章 穷举搜索 324
16.1 问题及方法的描述 324
16.2 回溯法 326
16.2.1 回溯法的通用算法 326
16.2.2 n皇后问题 327
16.2.3 子集和问题 328
16.2.4 回溯法的效率估计 330
16.3 分支限界法 331
16.3.1 分支限界法解n皇后问题 332
16.3.2 0/1背包问题 334
16.4 博弈树和α-β剪枝 340
16.4.1 博弈树及其评估的方法 340
16.4.2 α-β剪枝法 344
习题 346
第17章 平摊分析和斐波那契堆 348
17.1 平摊分析的常用方法 349
17.1.1 聚集法 349
17.1.2 记账法 350
17.1.3 势能法 352
17.2 动态表格 353
17.2.1 只允许扩张的动态表格 353
17.2.2 扩张和收缩都有的动态表格 355
17.3 斐波那契堆 358
17.3.1 斐波那契堆的构造 358
17.3.2 可合并堆的操作 360
17.3.3 减小一个关键字和删除任一结点
的操作 365
17.3.4 最大度数的界 367
习题 369
附录A 红黑树 372
附录B 用于分离集合操作的数据
结构 385
参考文献 397
