《组合数学算法与分析（下册）》

第七章搜索技术与整数规划1

1 DFS 搜索法举例1

2 旅行商问题10

3 任务安排问题15

4 任务的最佳排序问题18

5 整数规划21

6 0—1规划和隐枚举法24

7 Geoffrion 隐枚举法42

8 混合问题的分解算法53

9 分支定界法58

10 Gomory 的割平面法70

习题80

第八章动态规划83

1 问题的提出83

2 最佳原理86

3 最短路径问题94

4 旅行商问题的动态规划解法97

5 其它应用举例102

习题121

第九章优先策略、分治策略与快速算法125

1 优先策略应用举例125

2 分治策略137

3 Strassen 矩阵乘法144

4 Кроирод 算法和 Winagrad 算法149

5 FFT 算法153

6 卷积及其应用172

7 中国剩余定理176

8 数论变换183

9 Sch?hage-Strassen 整数乘法186

习题198

1 分类与其下界估计201

第十章分类与查找201

2 插入法204

3 下溢分类法和归并分类法214

4 快速分类法221

5 堆集分类法227

6 Shell 分类法232

7 Ford—Johnson 的归并插入分类法236

8 基数分类法242

9 分类网络244

10 外存分类法253

11 外存归并分类法258

12 找第 k 个元素268

13 查找271

14 关于高度 h 均衡二分树282

15 均衡二分树的插入和消去288

16 B——树296

17 杂凑300

18 二重杂凑308

习题309

第十一章NP 完全理论及近似解法312

1 确定型的图灵机312

2 可满足性问题315

3 非确定型的图灵机与 Cook 定理319

4 NP 完全问题326

5 NP 难题344

6 任务安排近似解法346

7 装箱问题近似解法352

8 旅行商问题的近似解法355

9 背包问题的近似解法365

10 算法的概率分析370

习题372

参考文献373