算法详解(卷4)——NP-Hard问题算法

1.专业作者：哥伦比亚大学计算机科学系教授蒂姆·拉夫加登丰富的教学经验和深入的研究成果使得这本书成为算法领域的专业之作。 2.实战导向：本书是《算法详解》四部曲的第四卷，主要介绍NP-Hard问题算法。全书内容丰富、结构清晰，提供了快速识别NP-Hard问题的方法和处理NP的算法工具，适合读者提升算法思维能力。 3.自测习题：每章都提供了小测验和章末习题，这不仅能够帮助读者加深对算法的理解，还能够培养读者的独立思考能力。 4.能力提升：无论是计算机专业的高校教师和学生，还是想要培养和训练算法思维与计算思维的IT专业人士，甚至是正在准备面试的应聘者和面试官，本书都能够有效提升算法能力。

算法详解系列图书共有4卷，本书是第4卷——NP-Hard问题算法。全书共有6章，主要介绍了快速识别NP-Hard问题的方法和处理NP的算法工具。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维与计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。

蒂姆·拉夫加登（Tim Roughgarden）是哥伦比亚大学计算机科学系的教授，之前曾任教于斯坦福大学计算机科学系，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第三卷，基于他从2012年开始定期举行的在线算法课程编写。

第1章什么是NP问题1
1.1MST和TSP：算法的难解之谜2
1.1.1最小生成树问题2
1.1.2旅行商问题3
1.1.3解决TSP的尝试和失败4
1.1.4小测验1.1–1.2的答案6
1.2读者的不同专业层次7
1.3容易的问题和困难的问题8
1.3.1多项式时间的算法9
1.3.2多项式时间与指数级时间10
1.3.3容易的问题11
1.3.4相对难以处理12
1.3.5困难的问题12
1.3.6P≠NP猜想14
1.3.7NP问题的临时定义14
1.3.8随机化和量子算法15
1.3.9微妙性15
1.4NP问题的算法策略16
1.4.1通用、正确、快速（选择其二）17
1.4.2通用性的妥协18
1.4.3正确性的妥协19
1.4.4最坏情况运行时间的妥协20
1.4.5关键思路21
1.5证明NP问题：一个简单的方案21
1.5.1转化22
1.5.2使用转化来设计快速算法23
1.5.3使用转化对NP问题进行扩展25
1.5.4无环最短路径是NP问题26
1.5.5小测验1.3的答案30
1.6新手错误和可接受的不准确说法30
1.7本章要点33
1.8章末习题34
1.8.1挑战题36
1.8.2编程题37
第2章正确性的妥协：高效的不准确算法38
2.1完成工时最小化38
2.1.1问题定义39
2.1.2贪心算法40
2.1.3Graham算法41
2.1.4运行时间42
2.1.5近似的正确性42
2.1.6定理2.1的证明44
2.1.7最长处理时间优先（LPT）46
2.1.8定理2.4的证明49
2.1.9小测验2.1–2.3的答案50
2.2优选覆盖51
2.2.1问题定义51
2.2.2更多的应用53
2.2.3一种贪心算法54
2.2.4GreedyCoverage算法的糟糕例子55
2.2.5近似正确性57
2.2.6一个关键的辅助结论58
2.2.7定理2.6的证明60
2.2.8小测验2.4–2.5的答案61
*2.3影响优选化62
2.3.1社交网络的瀑布模型62
2.3.2例子63
2.3.3影响优选化问题64
2.3.4一种贪心算法65
2.3.5近似正确性66
2.3.6影响是覆盖函数的一个加权和66
2.3.7定理2.8的证明67
2.3.8小测验2.6的答案69
2.4TSP的2-OPT启发式算法70
2.4.1处理TSP70
2.4.2通过2-变换改进路线72
2.4.32-OPT算法74
2.4.4运行时间75
2.4.5解决方案质量76
2.4.6小测验2.7–2.8的答案76
2.5局部搜索的原则77
2.5.1可行解决方案的元图（Meta-Graph）77
2.5.2局部搜索算法设计范例79
2.5.3三个建模决策80
2.5.4两个算法设计决策83
2.5.5运行时间和解决方案质量84
2.5.6避免不好的局部很优解84
2.5.7什么时候应该使用局部搜索？86
2.5.8小测验2.9–2.10的答案86
2.6本章要点87
2.7章末习题88
2.7.1挑战题91
2.7.2编程题96
第3章速度的妥协：准确的非高效算法98
3.1TSP的Bellman-Held-Karp算法98
3.1.1底线：穷举搜索98
3.1.2动态规划99
3.1.3很优子结构100
3.1.4推导公式102
3.1.5子问题103
3.1.6Bellman-Held-Karp算法104
3.1.7小测验3.1的答案105
*3.2通过颜色编码寻找最长路径106
3.2.1动机107
3.2.2问题定义107
3.2.3子问题的初次试探108
3.2.4颜色编码109
3.2.5计算大力度优惠成本全色路径110
3.2.6正确性和运行时间113
3.2.7随机化挽救危局114
3.2.8最终的算法116
3.2.9运行时间和正确性117
3.2.10再论PPI网络118
3.2.11小测验3.2–3.4的答案118
3.3问题特定的算法与万能魔盒119
3.3.1转化和万能魔盒119
3.3.2MIP和SAT解决程序120
3.3.3将要学习的和不会学习的121
3.3.4再论新手易犯的错误121
3.4混合整数规划解决程序121
3.4.1例子：背包问题122
3.4.2更基本意义上的MIP124
3.4.3MIP解决程序：一些起点125
3.5可满足性解决程序126
3.5.1示例：图形着色126
3.5.2可满足性127
3.5.3把图形着色问题表达为SAT128
3.5.4SAT解决程序：一些起点130
3.6本章要点130
3.7章末习题132
3.7.1挑战题134
3.7.2编程题137
第4章证明NP问题138
4.1再论转化138
4.23-SAT问题和Cook-Levin定理140
4.3整体思路142
4.3.1再论新手易犯的错误142
4.3.218个转化142
4.3.3为什么要啃艰涩的NP问题证明？144
4.3.4小测验4.1的答案145
4.4一个转化模板145
4.5独立子集问题是NP问题147
4.5.1主要思路147
4.5.2定理4.2的证明150
*4.6有向汉密尔顿路径问题是NP问题152
4.6.1变量的编码和真值指派153
4.6.2约束条件的编码154
4.6.3定理4.4的证明156
4.7TSP是NP问题158
4.7.1无向汉密尔顿路径问题158
4.7.2定理4.7的证明159
4.8子集求和问题是NP问题161
4.8.1基本方法161
4.8.2例子：4顶点环路162
4.8.3例子：5顶点环路163
4.8.4定理4.9的证明164
4.9本章要点165
4.10章末习题166
第5章P、NP及相关概念170
*5.1难处理性的累积证据171
5.1.1通过转化创建一个案例171
5.1.2为TSP选择集合C172
*5.2决策、搜索和优化173
*5.3NP：具有容易识别的解决方案的问题174
5.3.1复杂类NP的定义174
5.3.2NP中的问题实例175
5.3.3NP问题是可以通过穷举搜索解决的176
5.3.4NP问题176
5.3.5再论Cook-Levin定理177
5.3.6小测验5.1的解决方案179
*5.4P≠NP猜想180
5.4.1多项式时间可解决的NP问题180
5.4.2P≠NP猜想的正式定义180
5.4.3P≠NP猜想的状态181
*5.5指数级时间假设183
5.5.1NP问题需要指数级的时间吗？183
5.5.2强指数级时间假设（SETH）184
5.5.3容易问题的运行时间下界185
*5.6NP接近问题187
5.6.1Levin转化187
5.6.2NP中最难的问题189
5.6.3NP接近问题的存在189
5.7本章要点191
5.8章末习题192
第6章案例研究：FCC激励拍卖195
6.1无线频谱再利用195
6.1.1从电视到移动电话195
6.1.2无线频谱的一次最近重分配196
6.2回购执照的启发式贪心算法198
6.2.14个临时的简化假设198
6.2.2遭遇加权独立子集问题199
6.2.3启发式贪心算法200
6.2.4多频道情况202
6.2.5遭遇图形着色问题203
6.2.6小测验6.1的答案204
6.3可行性检查205
6.3.1改编为可满足性问题205
6.3.2加入边际约束条件206
6.3.3重新安置问题206
6.3.4技巧#1：预解决程序（寻求一种容易的解决之道）207
6.3.5技巧#2：预处理和简化208
6.3.6技巧#3：SAT解决程序的组合210
6.3.7容忍失败211
6.3.8小测验6.2的答案211
6.4降序时钟拍卖的实现212
6.4.1拍卖和算法212
6.4.2例子213
6.4.3重新实现FCCGreedy算法214
6.4.4是时候提供补偿了216
6.5最终结果217
6.6本章要点218
6.7章末习题218
6.7.1挑战题220
6.7.2编程题220
后记算法设计实战指南221
附录问题提示和答案224