计算机程序设计艺术卷4B：组合算法（二）（英文版）_[美] 高德纳（Donald E. Knuth）_9787115667601

《计算机程序设计艺术》系列是图灵奖得主高德纳倾尽心血进行的一项巨大的写作计划，这套书被公认为计算机科学领域的权威之作，深入阐述了程序设计和算法理论，对计算机领域的发展有着极为深远的影响。高德纳是算法和程序设计领域的先驱者，对计算机科学发展史也有着深入的研究，书中在介绍众多理论的同时，也给出了相关的历史和发展进程，成为本书的一大特色。本书是该系列的卷4B，以7.2.2节开篇，讨论回溯编程，内容包括舞蹈链、精准覆盖问题、算法谜题、可满足性问题等。

重温预备数学知识 1

不等式 3

鞅 6

从鞅得到的尾部不等式 8

应用 9

几乎必然和确乎必然的陈述 11

习题 12

第7 章组合查找 [4A.1]

7.2 生成所有可能的组合对象 [4A.281]

7.2.1 生成基本组合模式 [4A.281]

7.2.2 回溯编程 30

数据结构 32

沃克方法 33

排列与兰福德对 34

单词矩形 36

无逗点码 37

选择的动态排序 38

重温顺序分配 39

无逗点码问题的列表 41

行动和撤销的一般机制 43

无逗点码的回溯 44

运行时间估计 46

*估计解的个数 49

分解问题 52

历史注记 53

习题 55

7.2.2.1 舞蹈链 65

精确覆盖问题 66

副项 70

进度报告 73

数独 74

多联骨牌 79

多联立方 82

分解精确覆盖问题 83

受限颜色覆盖 87

引入重数 92

*新的舞步 95

*分析算法X 98

*分析匹配问题 102

*保持适当的专注 104

利用局部等价性 106

*预处理选项 108

最小成本解 111

*实现最小成本截断 116

*使用ZDD 的舞蹈链 119

总结 122

历史注记 123

习题（第 1 组） 124

习题（第 2 组） 156

习题（第3 组） 174

7.2.2.2 可满足性 185

一个简单的例子 188

精确覆盖 189

图着色 190

因式分解整数 192

故障测试 194

学习布尔函数 198

有界模型检测 200

互斥中的应用 204

数字体层成像 208

SAT 实例总结 210

回溯求解可满足性问题 211

惰性数据结构 214

从单元子句强制移动 215

算法的比较 218

*通过更加努力地工作来获得提速 219

*通过前瞻来获得提速 223

*更进一步的前瞻 229

随机可满足性问题 231

分析随机2SAT问题 235

归结法 238

*一般归结法的下界 241

使用归结的SAT 求解 244

由冲突驱动的子句学习 246

不可满足性证书 253

*清除无用的子句 255

*刷新文字并重新开始 259

蒙特卡罗算法. . . . . . . . . . . . . . . . . . . . . . 261

局部引理 265

迹与板块 267

迹上的算术 269

*迹与局部引理 271

*消息传递 274

*预处理子句 279

将约束编码为子句 281

单元传播与强制 287

对称性破缺 289

保可满足性的映射 291

100 个测试样例 297

调整参数 308

利用并行化 312

简史 313

习题 317

习题答案 370

附录A 数值表 656

附录B 记号索引 660

附录C 算法、定理、引理、推论和程序索引 666

附录D 组合问题索引 667

附录E 习题解答中谜题的答案 671

你还可能感兴趣

我要评论