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

第 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?C1.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?C2.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?C2.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?C2.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?C2.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?C3.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