算法详解（卷4）——NP-Hard问题算法

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

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

第 1章 什么是NP问题 1 1.1 MST和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.6 P≠NP猜想 14 1.3.7 NP问题的临时定义 14 1.3.8 随机化和量子算法 15 1.3.9 微妙性 15 1.4 NP问题的算法策略 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.3 Graham算法 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.4 GreedyCoverage算法的糟糕例子 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.4 TSP的2-OPT启发式算法 70 2.4.1 处理TSP 70 2.4.2 通过2-变换改进路线 72 2.4.3 2-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.1 TSP的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.6 Bellman-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.2 MIP和SAT解决程序 120 3.3.3 将要学习的和不会学习的 121 3.3.4 再论新手易犯的错误 121 3.4 混合整数规划解决程序 121 3.4.1 例子：背包问题 122 3.4.2 更基本意义上的MIP 124 3.4.3 MIP解决程序：一些起点 125 3.5 可满足性解决程序 126 3.5.1 示例：图形着色 126 3.5.2 可满足性 127 3.5.3 把图形着色问题表达为SAT 128 3.5.4 SAT解决程序：一些起点 130 3.6 本章要点 130 3.7 章末习题 132 3.7.1 挑战题 134 3.7.2 编程题 137 第4章 证明NP问题 138 4.1 再论转化 138 4.2 3-SAT问题和Cook-Levin定理 140 4.3 整体思路 142 4.3.1 再论新手易犯的错误 142 4.3.2 18个转化 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.7 TSP是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选择集合C 172 *5.2 决策、搜索和优化 173 *5.3 NP：具有容易识别的解决方案的问题 174 5.3.1 复杂类NP的定义 174 5.3.2 NP中的问题实例 175 5.3.3 NP问题是可以通过穷举搜索解决的 176 5.3.4 NP问题 176 5.3.5 再论Cook-Levin定理 177 5.3.6 小测验5.1的解决方案 179 *5.4 P≠NP猜想 180 5.4.1 多项式时间可解决的NP问题 180 5.4.2 P≠NP猜想的正式定义 180 5.4.3 P≠NP猜想的状态 181 *5.5 指数级时间假设 183 5.5.1 NP问题需要指数级的时间吗？ 183 5.5.2 强指数级时间假设（SETH） 184 5.5.3 容易问题的运行时间下界 185 *5.6 NP完全问题 187 5.6.1 Levin转化 187 5.6.2 NP中最难的问题 189 5.6.3 NP完全问题的存在 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.1 4个临时的简化假设 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