算法詳解（捲4）——NP-Hard問題算法 Algorithms Illuminated (Part 4): Algorithms for NP-Hard Problems

蒂姆·拉夫加登（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