《算法设计与分析习题解答（第3版）》（作者：王晓东）以算法设计策略为知识单元，系统地介绍了计算机算法的设计方法与分析技巧，以期为计算机科学与技术学科的学生提供一个广泛而坚实的计算机算法基础知识。全书共十一章节，内容包括算法引论、递归与分治策略、动态规划、贪心算法、回溯法等。

为了适应培养我国21世纪计算机各类人才的需要，结合我国高等学校教育工作的现状，立足培养学生能跟上国际计算机科学技术的发展水平，更新教学内容和教学方法，提高教学质量，本书以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机科学与技术学科的学生提供广泛而坚实的计算机算法基础知识。

另有配套的《算法设计与分析习题解答（第3版）》（作者：王晓东），对本书的全部习题做了详尽的解答。

《算法设计与分析习题解答（第3版）》内容丰富，观点新颖，理论联系实际。不仅可用作高等学校计算机专业本科生和研究生学习计算机算法设计的教材，而且也适合广大工程技术人员和自学读者学习参考。

第1章 算法引论

11.1 算法与程序1

1.2 表达算法的抽象机制1

1.3 描述算法3

1.4 算法复杂性分析11

小结14

习题14

第2章 递归与分治策略16

2.1 递归的概念16

2.2 分治法的基本思想22

2.3 二分搜索技术23

2.4 大整数的乘法24

2.5 Strassen矩阵乘法25

2.6 棋盘覆盖26

2.7 合并排序28

2.8 快速排序30

2.9 线性时间选择33

2.10 最接近点对问题36

2.11 循环赛日程表43

小结44

习题45

第3章 动态规划50

3.1 矩阵连乘问题50

3.2 动态规划算法的基本要素55

3.3 最长公共子序列58

3.4 凸多边形最优三角剖分61

3.5 多边形游戏64目录算法设计与分析(第3版)3.6 图像压缩67

3.7 电路布线70

3.8 流水作业调度72

3.9 0\\|1背包问题75

3.10 最优二叉搜索树80

小结83

习题84

第4章 贪心算法85

4.1 活动安排问题85

4.2 贪心算法的基本要素88

 4.2.1 贪心选择性质88

 4.2.2 最优子结构性质88

 4.2.3 贪心算法与动态规划算法的差异89

4.3 最优装载91

4.4 哈夫曼编码92

 4.4.1 前缀码93

 4.4.2 构造哈夫曼编码93

 4.4.3 哈夫曼算法的正确性95

4.5 单源最短路径97

 4.5.1 算法基本思想97

 4.5.2 算法的正确性和计算复杂性99

4.6 最小生成树100

 4.6.1 最小生成树性质100

 4.6.2 Prim算法100

 4.6.3 Kruskal算法102

4.7 多机调度问题104

4.8 贪心算法的理论基础106

 4.8.1 拟阵107

 4.8.2 带权拟阵的贪心算法108

 4.8.3 任务时间表问题110

小结113

习题113

第5章 回溯法115

5.1 回溯法的算法框架115

 5.1.1 问题的解空间115

 5.1.2 回溯法的基本思想116

 5.1.3 递归回溯117

 5.1.4 迭代回溯118

 5.1.5 子集树与排列树119

5.2 装载问题120

5.3 批处理作业调度126

5.4 符号三角形问题128

5.5 n后问题130

5.6 0-1背包问题133

5.7 最大团问题136

5.8 图的m着色问题138

5.9 旅行售货员问题140

5.10 圆排列问题142

5.11 电路板排列问题144

5.12 连续邮资问题147

5.13 回溯法的效率分析149

小结152

习题152

第6章 分支限界法153

6.1 分支限界法的基本思想153

6.2 单源最短路径问题156

6.3 装载问题158

6.4 布线问题167

6.5 0-1背包问题171

6.6 最大团问题175

6.7 旅行售货员问题178

6.8 电路板排列问题182

6.9 批处理作业调度184

小结189

习题189

第7章 概率算法190

7.1 随机数191

7.2 数值概率算法193

 7.2.1 用随机投点法计算π值193

 7.2.2 计算定积分194

 7.2.3 解非线性方程组196

7.3 舍伍德算法198

 7.3.1 线性时间选择算法198

 7.3.2 跳跃表200

7.4 拉斯维加斯算法205

 7.4.1 n后问题206

 7.4.2 整数因子分解209

7.5 蒙特卡罗算法211

 7.5.1 蒙特卡罗算法的基本思想211

 7.5.2 主元素问题213

 7.5.3 素数测试214

小结217

习题217

第8章 NP完全性理论221

8.1 计算模型221

 8.1.1 随机存取机RAM222

 8.1.2 随机存取存储程序机RASP228

 8.1.3 RAM模型的变形与简化231

 8.1.4 图灵机235

 8.1.5 图灵机模型与RAM模型的关系236

 8.1.6 问题变换与计算复杂性归约238

8.2 P类与NP类问题239

 8.2.1 非确定性图灵机239

 8.2.2 P类与NP类语言240

 8.2.3 多项式时间验证241

8.3 NP完全问题243

 8.3.1 多项式时间变换243

 8.3.2 Cook定理244

8.4 一些典型的NP完全问题247

 8.4.1 合取范式的可满足性问题247

 8.4.2 3元合取范式的可满足性问题248

 8.4.3 团问题249

 8.4.4 顶点覆盖问题250

 8.4.5 子集和问题251

 8.4.6 哈密顿回路问题252

 8.4.7 旅行售货员问题256

小结256

习题257

第9章 近似算法259

9.1 近似算法的性能259

9.2 顶点覆盖问题的近似算法260

9.3 旅行售货员问题近似算法262

 9.3.1 具有三角不等式性质的旅行售货员问题262

 9.3.2 一般的旅行售货员问题263

9.4 集合覆盖问题的近似算法264

9.5 子集和问题的近似算法267

 9.5.1 子集和问题的指数时间算法267

 9.5.2 子集和问题的完全多项式时间近似格式268

小结270

习题270

第10章 算法优化策略273

10.1 算法设计策略的比较与选择273

 10.1.1 最大子段和问题的简单算法273

 10.1.2 最大子段和问题的分治算法274

 10.1.3 最大子段和问题的动态规划算法275

 10.1.4 最大子段和问题与动态规划算法的推广276

10.2 动态规划加速原理279

 10.2.1 货物储运问题279

 10.2.2 算法及其优化279

10.3 问题的算法特征283

 10.3.1 贪心策略283

 10.3.2 对贪心策略的改进283

 10.3.3 算法三部曲285

 10.3.4 算法实现285

 10.3.5 算法复杂性290

10.4 优化数据结构291

 10.4.1 带权区间最短路问题291

 10.4.2 算法设计思想291

 10.4.3 算法实现方案293

 10.4.4 并查集296

 10.4.5 可并优先队列298

10.5 优化搜索策略302

小结308

习题309

第11章 在线算法设计310

11.1 在线算法设计的基本概念310

11.2 页调度问题312

11.3 势函数分析314

11.4 k服务问题315

 11.4.1 竞争比的下界315

 11.4.2 平衡算法316

 11.4.3 对称移动算法317

11.5 Steiner树问题320

11.6 在线任务调度321

11.7 负载平衡322

小结323

习题324

词汇索引325

参考文献330