算法詳解：NP-Hard問題算法（卷4）

第 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 讀者的不同專業(yè)層次 7
1.3 容易的問題和困難的問題 8
1.3.1多項式時間的算法 9
1.3.2 多項式時間與指數(shù)級時間 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 通用性的妥協(xié) 18
1.4.3 正確性的妥協(xié) 19
1.4.4 最壞情況運行時間的妥協(xié) 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 無環(huán)最短路徑是NP問題 26
1.5.5 小測驗1.3的答案 30
1.6 新手錯誤和可接受的不準確說法 30
1.7 本章要點 33
1.8 章末習題 34
1.8.1 挑戰(zhàn)題 36
1.8.2 編程題 37
第 2章 正確性的妥協(xié)：高效的不準確算法 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 最長處理時間優(yōu)先（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 社交網(wǎng)絡的瀑布模型 62
2.3.2 例子 63
2.3.3 影響最大化問題 64
2.3.4 一種貪心算法 65
2.3.5 近似正確性 66
2.3.6 影響是覆蓋函數(shù)的一個加權和 66
2.3.7 定理2.8的證明 67
2.3.8 小測驗2.6的答案 69
2.4 TSP的2-OPT啟發(fā)式算法 70
2.4.1 處理TSP 70
2.4.2 通過2-變換改進路線 72
2.4.3 2-OPT算法 74
2.4.4 運行時間 75
2.4.5 解決方案質(zhì)量 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 運行時間和解決方案質(zhì)量 84
2.5.6 避免不好的局部最優(yōu)解 84
2.5.7 什么時候應該使用局部搜索？ 86
2.5.8 小測驗2.9?C2.10的答案 86
2.6 本章要點 87
2.7 章末習題 88
2.7.1 挑戰(zhàn)題 91
2.7.2 編程題 96
第3章 速度的妥協(xié)：準確的非高效算法 98
3.1 TSP的Bellman-Held-Karp算法 98
3.1.1 底線：窮舉搜索 98
3.1.2 動態(tài)規(guī)劃 99
3.1.3 最優(yōu)子結構 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網(wǎng)絡 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 混合整數(shù)規(guī)劃解決程序 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 挑戰(zhàn)題 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頂點環(huán)路 162
4.8.3 例子：5頂點環(huán)路 163
4.8.4 定理4.9的證明 164
4.9 本章要點 165
4.10 章末習題 166
第5章 P、NP及相關概念 170
*5.1 難處理性的累積證據(jù) 171
5.1.1 通過轉化創(chuàng)建一個案例 171
5.1.2 為TSP選擇集合C 172
*5.2 決策、搜索和優(yōu)化 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猜想的狀態(tài) 181
*5.5 指數(shù)級時間假設 183
5.5.1 NP問題需要指數(shù)級的時間嗎？ 183
5.5.2 強指數(shù)級時間假設（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 回購執(zhí)照的啟發(fā)式貪心算法 198
6.2.1 4個臨時的簡化假設 198
6.2.2 遭遇加權獨立子集問題 199
6.2.3 啟發(fā)式貪心算法 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 降序時鐘拍賣的實現(xiàn) 212
6.4.1 拍賣和算法 212
6.4.2 例子 213
6.4.3 重新實現(xiàn)FCCGreedy算法 214
6.4.4 是時候提供補償了 216
6.5 最終結果 217
6.6 本章要點 218
6.7 章末習題 218
6.7.1 挑戰(zhàn)題 220
6.7.2 編程題 220
后記 算法設計實戰(zhàn)指南 221
附錄 問題提示和答案 224