第1章 算法复杂性及其分析 1
1.1 概述 1
1.2 RAM模型 4
1.3 算法及其复杂性测度 11
1.4 RAM模型的简化 16
1.4.1 直线式程序模型 16
1.4.2 判定树模型 18
1.4.3 算法描述语言 19
1.5 递归技术 20
1.5.1 递归定义与实现技术 20
1.5.2 递归方程求解的递推求和方法 23
1.5.3 递归方程求解的生成函数求和方法 27
本章小结 30
习题 31
第2章 分治法 34
2.1 分治法的基本思想 34
2.2 最大元最小元问题 35
2.3 合并排序 37
2.4 顺序统计问题 41
2.5 矩阵相乘问题 45
2.6 快速排序算法 47
2.7 顺序统计问题的另一个求解算法 52
2.8 子集和问题的分治求解 53
2.9 马的周游路线问题 56
本章小结 62
习题 63
第3章 动态规划方法 65
3.1 动态规划方法的基本思想 65
3.2 单源最短路径问题 65
3.3 最佳折半查找树构造 69
3.4 资源分配问题 76
3.5 多机系统可靠性设计 80
3.6 背包问题 82
3.7 旅行商问题 84
3.8 计算矩阵连乘积 87
本章小结 92
习题 92
第4章 贪心法 96
4.1 贪心法的基本思想 96
4.2 背包问题 97
4.3 多处理机调度 100
4.4 带时限的作业调度 102
4.5 单源最短路径问题 106
4.6 Huffman编码 109
4.7 最佳合并顺序 111
4.8 最小耗费生成树 116
本章小结 120
习题 121
第5章 回溯法 124
5.1 回溯法的基本思想 124
5.2 n皇后问题 127
5.3 子集和问题 131
5.4 图着色问题 135
5.5 哈密顿图判定问题 138
5.6 回溯法效能分析 141
本章小结 145
习题 145
第6章 分枝限界方法 149
6.1 分枝限界方法的基本思想 149
6.2 15迷问题 153
6.3 带时限的作业调度 157
6.4 最优分配问题 161
6.5 货郎担问题的分枝限界求解算法 164
6.6 0-1背包问题 170
本章小结 172
习题 172
第7章 NP完全问题 174
7.1 确定型图灵机 174
7.2 图灵机模型和RAM模型的关系 181
7.3 非确定型图灵机 184
7.4 P和NP问题类 188
7.5 NP完全性和COOK定理 191
7.6 若干NP完全问题及证明 196
7.7 Co-NP类问题 200
本章小结 202
习题 202
参考文献 204