第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