目　录

第 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