算法詳解(卷4)--NP-Hard問題算法

第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