第1章 算法分析技术 1
§1.1 算法及其复杂性 1
§1.2 渐近估计技术及基本规则 4
§1.3 递归算法分析 7
1.3.1 合并排序算法分析 7
1.3.2 一类递推方程的一般解 10
§1.4 大整数相乘的递归算法 14
§1.5 练习 15
第2章 算法设计技术 17
§2.1 分而治之 17
§2.2 贪心技术 21
§2.3 动态规划 23
§2.4 回溯技术 29
2.4.1 对策树搜索与α/β删除 30
2.4.2 一般树的回溯搜索与分支定界 34
§2.5 局部搜索技术 40
§2.6 练习 44
第3章 P类、NP类及NPC类 47
§3.1 问题与算法 47
§3.2 确定型图灵机与P类 49
§3.3 非确定型计算与NP类 55
§3.4 多项式变换与NPC类 59
§3.5 库克定理 63
§3.6 练习 68
第4章 证明问题属于NPC类的技术 69
§4.1 基本的NPC问题 69
§4.2 证明NP-完全性的典型技术 83
4.2.1 限制技术 84
4.2.2 局部替换技术 86
4.2.3 分支设计技术 92
§4.3 练习 95
第5章 NPC问题子问题的复杂性 97
§5.1 2SAT问题属于P类 97
§5.2 几个NPC问题在三角化图上的解 103
5.2.1 三角化图的特征 104
5.2.2 用字典编辑广度优先搜索识别三角化图 106
5.2.3 三角化图上着色、团、独立集及团覆盖问题的算法 112
§5.3 子问题中P和NPC的分界 113
§5.4 练习 119
第6章 拟多项式变换和图灵归约 121
§6.1 判定问题、语言和编码方案 121
§6.2 拟多项式时间算法和强NPC类 123
§6.3 用拟多项式变换证明强NP-完全性 127
§6.4 复杂性类之间的关系 138
§6.5 图灵归约和NP-难解问题 140
§6.6 练习 147
第7章 NP-难解问题近似算法 149
§7.1 近似算法及其性能评估 149
§7.2 近似算法设计 160
7.2.1 满足三角不等式的货郎问题及其近似算法 160
7.2.2 满足三角不等式的货郎问题的最小生成树算法 165
7.2.3 多任务排工问题的近似算法 168
7.2.4 独立任务排工问题 171
§7.3 NP-难解问题可近似计算复杂性 174
§7.4 多项式时间近似方案 177
§7.5 练习 188
第8章 近似算法设计技术 190
§8.1 组合技术 190
8.1.1 MaxSAT问题 190
8.1.2 Maxk-SAT问题 192
8.1.3 图顶点覆盖问题 193
8.1.4 整数排列与换位移动排序 194
8.1.5 集合覆盖问题 200
§8.2 线性规划技术 203
8.2.1 顶点覆盖近似算法 203
8.2.2 集合覆盖近似算法 204
§8.3 原始对偶技术 206
8.3.1 集合覆盖 207
8.3.2 击中集问题 209
8.3.3 最短路问题 213
8.3.4 Steiner树问题 214
§8.4 局部搜索技术 216
8.4.1 Max-3sAT问题的局部搜索算法 217
8.4.2 k-median问题的局部搜索算法 218
8.4.3 设施定位问题的局部搜索近似算法 222
§8.5 随机近似算法 224
8.5.1 MaxSAT问题的随机算法 225
8.5.2 欧氏平面上货郎问题的随机算法 228
§8.6 练习 236
参考文献 239