目   录

卷I 实用算法设计

第1章 算法设计简论 3

1.1 机器人巡游最优化 4

1.2 合理挑选工作  8

1.3 关于正确性的推理 11

1.3.1 问题和特性 11

1.3.2 表述算法  12

1.3.3 论证非正确性 13

1.4 归纳与递归 14

1.5 建立问题的模型 16

1.5.1 组合式对象 17

1.5.2 递归式对象 18

1.6 反证法 20

1.7 关于“算法征战逸事” 20

1.8 算法征战逸事: 通灵者的模型建立 21

1.9 估算  24

1.10 习题 25

第2章 算法分析 30

2.1 RAM计算模型 30

2.2 大O记号 32

2.3 增长量级与强弱关系 35

2.4 以大O来推演公式 37

2.4.1 函数相加  38

2.4.2 函数相乘  38

2.5 关于效率的推理 39

2.5.1 选择排序  39

2.5.2 插入排序  40

2.5.3 字符串模式匹配 41

2.5.4 矩阵乘法  43

2.6 求和  44

2.7 对数及其应用  46

2.7.1 对数与二分查找 46

2.7.2 对数与树  46

2.7.3 对数与比特 46

2.7.4 对数与乘法 47

2.7.5 快速求幂  47

2.7.6 对数与求和 48

2.7.7 对数与司法正义 48

2.8 对数的特性 50

2.9 算法征战逸事: 锥体之秘 51

2.10 高等分析(*)  53

2.10.1 一些深奥难懂的函数 54

2.10.2 极限与强弱关系 55

2.11 习题 56

第3章 数据结构. 65

3.1 紧接数据结构与链接数据结构 65

3.1.1 数组. 66

3.1.2 指针与链接结构 67

3.1.3 对比. 69

3.2 容器: 栈与队列. 70

3.3 字典  71

3.4 二叉查找树 75

3.4.1 实现二叉查找树 76

3.4.2 二叉查找树究竟能有多好. 80

3.4.3 平衡查找树 80

3.5 优先级队列 82

3.6 算法征战逸事: 剥离三角剖分 84

3.7 散列  87

3.7.1 碰撞消除  87

3.7.2 凭借散列实现副本检测. 89

3.7.3 其他散列技巧. 91

3.7.4 规范化 91

3.7.5 精简. 91

3.8 专用数据结构  92

3.9 算法征战逸事: 把它们串起来 93

3.10 习题 96

第4章 排序  103

4.1 排序的应用  103

4.2 排序的范式  107

4.3 堆排序: 借助数据结构而得的最优排序. 108

4.3.1 堆 109

4.3.2 建堆. 111

4.3.3 取最小元  112

4.3.4 更快的建堆算法(*)  114

4.3.5 利用增量式插入来排序. 116

4.4 算法征战逸事: 给我一张机票 117

4.5 归并排序: 通过分治来排序 119

4.6 快速排序: 通过随机化来排序 122

4.6.1 快速排序期望情况的直观解释  124

4.6.2 随机化算法. 125

4.6.3 快速排序真的快吗  127

4.7 分配排序: 通过装桶来排序 127

4.8 算法征战逸事: 为被告辩护的Skiena 129

4.9 习题 131

第5章 分治  138

5.1 二分查找及相关算法  138

5.1.1 出现次数的计数 139

5.1.2 单侧二分查找. 140

5.1.3 平方根和其他方根  140

5.2 算法征战逸事: 错中揪错. 141

5.3 递推关系 142

5.4 求解分治递推关系 144

5.5 快速乘法 145

5.6 最大子范围与最近点对 . 146

5.7 并行算法 148

5.7.1 数据并行化. 149

5.7.2 并行化的陷阱. 149

5.8 算法征战逸事: 毫无进展. 150

5.9 卷积(*). 151

5.9.1 卷积的应用. 152

5.9.2 快速多项式乘法(**) . 153

5.10 习题 155

第6章 散列与随机化算法 158

6.1 重温概率论  159

6.1.1 概率. 159

6.1.2 复合事件与独立性  160

6.1.3 条件概率  161

6.1.4 概率分布  162

6.1.5 均值与方差. 163

6.1.6 投掷硬币  163

6.2 理解球与箱  165

6.3 为什么散列是随机化算法. 167

6.4 Bloom过滤器 168

6.5 生日悖论和完美散列  170

6.6 取小式散列  172

6.7 高效字符串匹配. 174

6.8 素性检验 176

6.9 算法征战逸事: 将我的中间名首字母告诉Knuth 177

6.10 随机数从何而来 178

6.11 习题 179

第7章 图的遍历 182

7.1 图的风格 183

7.2 用于图的数据结构 187

7.3 算法征战逸事: 我曾是摩尔定律的受害者 191

7.4 算法征战逸事: 图的获取. 194

7.5 遍历图 196

7.6 广度优先搜索  196

7.6.1 实现. 198

7.6.2 发掘遍历的功用 199

7.6.3 寻找路径  199

7.7 广度优先搜索的应用  200

7.7.1 连通分量  200

7.7.2 双色图 201

7.8 深度优先搜索  202

7.9 深度优先搜索的应用  205

7.9.1 寻找环 206

7.9.2 关节点 206

7.10 有向图的深度优先搜索. 210

7.10.1 拓扑排序 211

7.10.2 强连通分量. 212

7.11 习题 215

第8章 加权图算法 222

8.1 最小生成树  222

8.1.1 Prim算法 223

8.1.2 Kruskal算法. 226

8.1.3 合并—查找数据结构 228

8.1.4 最小生成树的变种  230

8.2 算法征战逸事: 网络之外别无他求. 231

8.3 最短路径 234

8.3.1 Dijkstra算法. 234

8.3.2 全图点对最短路径  237

8.3.3 传递闭包  239

8.4 算法征战逸事: 拨出文档. 239

8.5 网络流和二部匹配 243

8.5.1 二部匹配  243

8.5.2 计算网络流. 244

8.6 随机化最小割  247

8.7 去设计图, 而非算法 248

8.8 习题 251

第9章 组合搜索 255

9.1 回溯 255

9.2 回溯实例 258

9.2.1 构建全部子集. 258

9.2.2 构建全部置换. 259

9.2.3 构建图的全部路径  260

9.3 搜索剪枝法  262

9.4 数独 263

9.5 算法征战逸事: 覆盖棋盘. 267

9.6 最佳优先搜索  271

9.7 A.启发式方法. 272

9.8 习题 274

第10章 动态规划 279

10.1 缓存与计算  280

10.1.1 以递归计算Fibonacci数 280

10.1.2 以缓存计算Fibonacci数 281

10.1.3 以动态规划计算Fibonacci数  283

10.1.4 二项式系数. 283

10.2 字符串近似匹配 285

10.2.1 以递归计算编辑距离 .286

10.2.2 以动态规划求解编辑距离 287

10.2.3 重建路径 289

10.2.4 编辑距离的变种 291

10.3 最长递增子序列 293

10.4 算法征战逸事: 条码的文本压缩. 295

10.5 无次序划分/子集和值 . 298

10.6 算法征战逸事: 功率平衡 .300

10.7 依次序划分问题 302

10.8 上下文无关语言的语法分析 305

10.9 动态规划的局限性: TSP. 307

10.9.1 动态规划算法什么时候是正确的?. 308

10.9.2 动态规划算法什么时候是高效的?. 309

10.10 算法征战逸事: 过去所发生的事就是Prolog 310

10.11 习题 313

第11章 NP完全 321

11.1 问题和归约  321

11.1.1 关键思想 322

11.1.2 判定问题 323

11.2 算法的归约  323

11.2.1 最近点对 324

11.2.2 最长递增子序列 324

11.2.3 最小公倍数. 325

11.2.4 凸包(*)  326

11.3 基础性的难解性归约  327

11.3.1 哈密顿环 328

11.3.2 独立集和顶点覆盖  329

11.3.3 团 332

11.4 可满足性 333

11.5 创造性的归约 335

11.5.1 顶点覆盖 335

11.5.2 整数规划 337

11.6 难解性证明的艺术 339

11.7 算法征战逸事: 争分夺秒亦难. 340

11.8 算法征战逸事: 后来我失败了 .343

11.9 P与NP 345

11.9.1 验证与发现 .345

11.9.2 P类和NP类. 345

11.9.3 可满足性问题为何如此之难  346

11.9.4 是NP难解还是NP完全? 346

11.10 习题 348

第12章 处理难解问题 354

12.1 近似算法 354

12.2 顶点覆盖问题的近似算法 355

12.3 欧氏空间旅行商问题  357

12.4 何时平均已经够好 360

12.4.1 最大化k-SAT 360

12.4.2 最大无环子图 361

12.5 集合覆盖 361

12.6 启发式搜索方法 363

12.6.1 随机抽样 364

12.6.2 局部搜索 366

12.6.3 模拟退火 368

12.6.4 模拟退火的应用 372

12.7 算法征战逸事: 只不过它不是收音机而已 .373

12.8 算法征战逸事: 对阵列退火 376

12.9 遗传算法与其他启发式搜索方法 .379

12.10 量子计算  380

12.10.1 “Quantum”计算机的特性 .380

12.10.2 Grover数据库搜索算法 382

12.10.3 更快的“Fourier”变换 383

12.10.4 整数因子分解的Shor算法 384

12.10.5 展望量子计算 385

12.11 习题 387

第13章 如何设计算法 390

卷II 算法世界搭车客指南

第14章 算法问题目录册 397

第15章 数据结构 399

15.1 字典 399

15.2 优先级队列  404

15.3 后缀树和后缀数组 407

15.4 图数据结构  410

15.5 集合数据结构 413

15.6  k维树. 416

第16章 数值问题 420

16.1 解线性方程组 421

16.2 带宽约减 424

16.3 矩阵乘法 426

16.4 行列式与积和式 428

16.5 约束最优化与无约束最优化 430

16.6 线性规划 434

16.7 随机数生成  437

16.8 因子分解与素性检验  440

16.9 精确算术 443

16.10 背包问题  446

16.11 离散傅里叶变换 449

第17章 组合问题 453

17.1 排序 453

17.2 查找 457

17.3 中位数和选择 461

17.4 生成置换 463

17.5 生成子集 467

17.6 生成划分 469

17.7 图的生成 473

17.8 日历计算 477

17.9 作业调度 478

17.10 可满足性  481

第18章 图问题: 多项式时间. 484

18.1 连通分量 484

18.2 拓扑排序 487

18.3 最小生成树  489

18.4 最短路径 494

18.5 传递闭包与传递约简  498

18.6 匹配 500

18.7 欧拉环/中国邮递员  503

18.8 边连通度与顶点连通度 .506

18.9 网络流 508

18.10 精致绘图  511

18.11 绘树 514

18.12 平面性检验与嵌入  516

第19章 图问题: NP难解 520

19.1 团  520

19.2 独立集 523

19.3 顶点覆盖 525

19.4 旅行商问题  527

19.5 哈密顿环 530

19.6 图划分 533

19.7 顶点着色 535

19.8 边着色 539

19.9 图同构 540

19.10 Steiner树  544

19.11 反馈边集/反馈顶点集 .547

第20章 计算几何 551

20.1 稳健的几何基元操作  551

20.2 凸包 555

20.3 三角剖分 558

20.4 Voronoi图  561

20.5 最近邻搜索  563

20.6 范围搜索 566

20.7 点定位 569

20.8 相交检测 571

20.9 装箱问题 574

20.10 中轴变换  577

20.11 多边形划分  579

20.12 简化多边形  582

20.13 形状相似度  584

20.14 运动规划  587

20.15 直线排布维护 .590

20.16 Minkowski和 .592

第21章 集合与字符串问题 595

21.1 集合覆盖 595

21.2 组集 598

21.3 字符串匹配  600

21.4 字符串近似匹配 603

21.5 文本压缩 607

21.6 密码学 610

21.7 有限状态机最小化 613

21.8 最长公共子串/最长公共子序列   616

21.9 最短公共超串 618

第22章 算法相关资源 621

22.1 算法库 621

22.1.1 LEDA  621

22.1.2 CGAL  622

22.1.3 Boost图库 622

22.1.4 Netlib  622

22.1.5 ACM算法集萃 623

22.1.6 GitHub与SourceForge. 623

22.1.7 The Stanford GraphBase 623

22.1.8 Combinatorica 624

22.1.9 源自书籍的程序 624

22.2 数据源 625

22.3 在线文献资源 626

22.4 专业咨询服务 626

参考文献 627