图解算法

算法是利用电脑解决问题的技巧。本书以轻松的对话方式，采用图解的辅助说明，帮助读者简单且自然地掌握算法的基本概念，并养成主动思考的习惯，达到用算法解决实际问题的目的。全书共分12章，内容包括一切从观察开始、分而治之法、动态规划、贪婪法、修剪与搜索法、树搜索法、问题转换、图算法、计算几何、算法的难题、逼近算法、随机算法等。本书示例丰富，图文并茂，以易于理解的方式阐释算法，帮助程序员在日常项目开发中更好地发挥算法的能量。

推荐序
前 言
1 一切从观察开始
1.1 什么是算法 2
1.2 汉诺塔问题 3
1.3 汉诺塔问题的非递归算法 10
1.4 发现算法的技巧 16
学习效果评测 18
2 分而治之法
2.1 何谓分而治之法 20
2.2 找出最大值 21
2.3 时间复杂度 23
2.4 二维极点问题 25
2.5 快速排序法 30
2.6 快速排序法的时间复杂度 34
2.7 寻找第 k 小值问题 40
2.8 分而治之法的技巧 47
学习效果评测 48
3 动态规划
3.1 何谓动态规划 50
3.2 换零钱 50
3.3 数字金字塔 54
3.4 最长相同子字符串 58
3.5 安排公司聚会 64
3.6 动态规划的技巧 70
学习效果评测 72
4 贪婪法
4.1 何谓贪婪法 75
4.2 最小成本生成树 75
4.3 霍夫曼编码树 83
4.4 贪婪法的陷阱：0—1 背包问题 88
4.5 单位时间工作调度问题 90
4.6 证明贪婪法并介绍Matroid理论 96
4.7 贪婪法的技巧 99
学习效果评测 100
5 修剪与搜索法
5.1 何谓修剪与搜索法 103
5.2 找坏蛋问题 104
5.3 猜数字问题 105
5.4 约瑟夫问题 106
5.5 简化的线性规划问题 113
5.6 修剪与搜索法的技巧 119
学习效果评测 119
6 树搜索法
6.1 何谓树搜索法 122
6.2 树状解空间：n 个皇后问题 123
6.3 回溯法：涂色问题 126
6.4 广度优先搜索法：八数字谜题 128
6.5 加速技巧：旅行商问题 131
6.6 树搜索法的技巧 140
学习效果评测 141
7 问题转换
7.1 何谓问题转换 144
7.2 将相异代表系问题转换成二分图上的匹配问题 145
7.3 将二分图上的匹配问题转换成网络流图问题 147
7.4 将网络流图问题转换成线性规划问题 150
7.5 问题转换的技巧 152
学习效果评测 154
8 图算法
8.1 什么是图 156
8.2 连通分支 157
8.3 Dijkstra zui短路径算法 160
8.4 Bellman—Ford zui短路径算法 168
8.5 双连通分支 175
8.6 图算法的技巧 193
学习效果评测 195
9 计算几何
9.1 何谓计算几何 199
9.2 多边形中的点 200
9.3 天空轮廓 203
9.4 凸包 208
9.5 最近点对 215
9.6 计算几何的技巧 219
学习效果评测 220
10 算法的难题
10.1 什么是 NP—Complete 224
10.2 集合 P 和集合 NP 225
10.3 满足性问题 227
10.4 多项式时间转换 229
10.5 NP 中的难题 230
10.6 NP—Complete 的性质 234
10.7 NP—Complete 的证明技巧 237
学习效果评测 241
11 逼近算法
11.1 什么是逼近算法 244
11.2 最小顶点覆盖问题 244
11.3 装箱问题 247
11.4 平面上的旅行商问题 249
11.5 逼近算法的技巧 252
学习效果评测 252
12 随机算法
12.1 什么是随机算法 256
12.2 随机快速排序法 257
12.3 质数测试 258
12.4 最小割算法 259
12.5 随机算法技巧 265
学习效果评测 265
参考文献

编写这本书的动机是希望帮助读者简单、轻松地掌握算法的基本概念。因此，本书将不尝试收录所有的算法，同时也不把有限的笔墨用来分析算法的复杂度和对算法进行严格证明。    本书在介绍算法之前，常常会刻意地加入一小段对话，目的是希望通过思辨和讨论，自然地引出算法的直观意义。倘若读者从学习中顺便养成思考的习惯，那就更好了。    作者知识面有限，再加上表达能力不足，如果导致书中仍有无法被读者理解之处，在此向读者致歉。假如您在阅读的过程中惊讶地发现算法之美，在此表示深深的敬意。    作者2017年4月