算法詳解：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 小測(cè)驗(yàn)1.1?C1.2的答案 6
1.2 讀者的不同專業(yè)層次 7
1.3 容易的問題和困難的問題 8
1.3.1多項(xiàng)式時(shí)間的算法 9
1.3.2 多項(xiàng)式時(shí)間與指數(shù)級(jí)時(shí)間 10
1.3.3 容易的問題 11
1.3.4 相對(duì)難以處理 12
1.3.5 困難的問題 12
1.3.6 P≠NP猜想 14
1.3.7 NP問題的臨時(shí)定義 14
1.3.8 隨機(jī)化和量子算法 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 最壞情況運(yùn)行時(shí)間的妥協(xié) 20
1.4.5 關(guān)鍵思路 21
1.5 證明NP問題：一個(gè)簡(jiǎn)單的方案 21
1.5.1 轉(zhuǎn)化 22
1.5.2 使用轉(zhuǎn)化來設(shè)計(jì)快速算法 23
1.5.3 使用轉(zhuǎn)化對(duì)NP問題進(jìn)行擴(kuò)展 25
1.5.4 無環(huán)最短路徑是NP問題 26
1.5.5 小測(cè)驗(yàn)1.3的答案 30
1.6 新手錯(cuò)誤和可接受的不準(zhǔn)確說法 30
1.7 本章要點(diǎn) 33
1.8 章末習(xí)題 34
1.8.1 挑戰(zhàn)題 36
1.8.2 編程題 37
第 2章 正確性的妥協(xié)：高效的不準(zhǔn)確算法 38
2.1 完成工時(shí)最小化 38
2.1.1 問題定義 39
2.1.2 貪心算法 40
2.1.3 Graham算法 41
2.1.4 運(yùn)行時(shí)間 42
2.1.5 近似的正確性 42
2.1.6 定理2.1的證明 44
2.1.7 最長(zhǎng)處理時(shí)間優(yōu)先（LPT） 46
2.1.8 定理2.4的證明 49
2.1.9 小測(cè)驗(yàn)2.1?C2.3的答案 50
2.2 最大覆蓋 51
2.2.1 問題定義 51
2.2.2 更多的應(yīng)用 53
2.2.3 一種貪心算法 54
2.2.4 GreedyCoverage算法的糟糕例子 55
2.2.5 近似正確性 57
2.2.6 一個(gè)關(guān)鍵的輔助結(jié)論 58
2.2.7 定理2.6的證明 60
2.2.8 小測(cè)驗(yàn)2.4?C2.5的答案 61
*2.3 影響最大化 62
2.3.1 社交網(wǎng)絡(luò)的瀑布模型 62
2.3.2 例子 63
2.3.3 影響最大化問題 64
2.3.4 一種貪心算法 65
2.3.5 近似正確性 66
2.3.6 影響是覆蓋函數(shù)的一個(gè)加權(quán)和 66
2.3.7 定理2.8的證明 67
2.3.8 小測(cè)驗(yàn)2.6的答案 69
2.4 TSP的2-OPT啟發(fā)式算法 70
2.4.1 處理TSP 70
2.4.2 通過2-變換改進(jìn)路線 72
2.4.3 2-OPT算法 74
2.4.4 運(yùn)行時(shí)間 75
2.4.5 解決方案質(zhì)量 76
2.4.6 小測(cè)驗(yàn)2.7?C2.8的答案 76
2.5 局部搜索的原則 77
2.5.1 可行解決方案的元圖（Meta-Graph） 77
2.5.2 局部搜索算法設(shè)計(jì)范例 79
2.5.3 三個(gè)建模決策 80
2.5.4 兩個(gè)算法設(shè)計(jì)決策 83
2.5.5 運(yùn)行時(shí)間和解決方案質(zhì)量 84
2.5.6 避免不好的局部最優(yōu)解 84
2.5.7 什么時(shí)候應(yīng)該使用局部搜索？ 86
2.5.8 小測(cè)驗(yàn)2.9?C2.10的答案 86
2.6 本章要點(diǎn) 87
2.7 章末習(xí)題 88
2.7.1 挑戰(zhàn)題 91
2.7.2 編程題 96
第3章 速度的妥協(xié)：準(zhǔn)確的非高效算法 98
3.1 TSP的Bellman-Held-Karp算法 98
3.1.1 底線：窮舉搜索 98
3.1.2 動(dòng)態(tài)規(guī)劃 99
3.1.3 最優(yōu)子結(jié)構(gòu) 100
3.1.4 推導(dǎo)公式 102
3.1.5 子問題 103
3.1.6 Bellman-Held-Karp算法 104
3.1.7 小測(cè)驗(yàn)3.1的答案 105
*3.2 通過顏色編碼尋找最長(zhǎng)路徑 106
3.2.1 動(dòng)機(jī) 107
3.2.2 問題定義 107
3.2.3 子問題的初次試探 108
3.2.4 顏色編碼 109
3.2.5 計(jì)算最低成本全色路徑 110
3.2.6 正確性和運(yùn)行時(shí)間 113
3.2.7 隨機(jī)化挽救危局 114
3.2.8 最終的算法 116
3.2.9 運(yùn)行時(shí)間和正確性 117
3.2.10 再論P(yáng)PI網(wǎng)絡(luò) 118
3.2.11 小測(cè)驗(yàn)3.2?C3.4的答案 118
3.3 問題特定的算法與萬能魔盒 119
3.3.1 轉(zhuǎn)化和萬能魔盒 119
3.3.2 MIP和SAT解決程序 120
3.3.3 將要學(xué)習(xí)的和不會(huì)學(xué)習(xí)的 121
3.3.4 再論新手易犯的錯(cuò)誤 121
3.4 混合整數(shù)規(guī)劃解決程序 121
3.4.1 例子：背包問題 122
3.4.2 更基本意義上的MIP 124
3.4.3 MIP解決程序：一些起點(diǎn) 125
3.5 可滿足性解決程序 126
3.5.1 示例：圖形著色 126
3.5.2 可滿足性 127
3.5.3 把圖形著色問題表達(dá)為SAT 128
3.5.4 SAT解決程序：一些起點(diǎn) 130
3.6 本章要點(diǎn) 130
3.7 章末習(xí)題 132
3.7.1 挑戰(zhàn)題 134
3.7.2 編程題 137
第4章 證明NP問題 138
4.1 再論轉(zhuǎn)化 138
4.2 3-SAT問題和Cook-Levin定理 140
4.3 整體思路 142
4.3.1 再論新手易犯的錯(cuò)誤 142
4.3.2 18個(gè)轉(zhuǎn)化 142
4.3.3 為什么要啃艱澀的NP問題證明？ 144
4.3.4 小測(cè)驗(yàn)4.1的答案 145
4.4 一個(gè)轉(zhuǎn)化模板 145
4.5 獨(dú)立子集問題是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頂點(diǎn)環(huán)路 162
4.8.3 例子：5頂點(diǎn)環(huán)路 163
4.8.4 定理4.9的證明 164
4.9 本章要點(diǎn) 165
4.10 章末習(xí)題 166
第5章 P、NP及相關(guān)概念 170
*5.1 難處理性的累積證據(jù) 171
5.1.1 通過轉(zhuǎn)化創(chuàng)建一個(gè)案例 171
5.1.2 為TSP選擇集合C 172
*5.2 決策、搜索和優(yōu)化 173
*5.3 NP：具有容易識(shí)別的解決方案的問題 174
5.3.1 復(fù)雜類NP的定義 174
5.3.2 NP中的問題實(shí)例 175
5.3.3 NP問題是可以通過窮舉搜索解決的 176
5.3.4 NP問題 176
5.3.5 再論Cook-Levin定理 177
5.3.6 小測(cè)驗(yàn)5.1的解決方案 179
*5.4 P≠NP猜想 180
5.4.1 多項(xiàng)式時(shí)間可解決的NP問題 180
5.4.2 P≠NP猜想的正式定義 180
5.4.3 P≠NP猜想的狀態(tài) 181
*5.5 指數(shù)級(jí)時(shí)間假設(shè) 183
5.5.1 NP問題需要指數(shù)級(jí)的時(shí)間嗎？ 183
5.5.2 強(qiáng)指數(shù)級(jí)時(shí)間假設(shè)（SETH） 184
5.5.3 容易問題的運(yùn)行時(shí)間下界 185
*5.6 NP完全問題 187
5.6.1 Levin轉(zhuǎn)化 187
5.6.2 NP中最難的問題 189
5.6.3 NP完全問題的存在 189
5.7 本章要點(diǎn) 191
5.8 章末習(xí)題 192
第6章 案例研究：FCC激勵(lì)拍賣 195
6.1 無線頻譜再利用 195
6.1.1 從電視到移動(dòng)電話 195
6.1.2 無線頻譜的一次最近重分配 196
6.2 回購執(zhí)照的啟發(fā)式貪心算法 198
6.2.1 4個(gè)臨時(shí)的簡(jiǎn)化假設(shè) 198
6.2.2 遭遇加權(quán)獨(dú)立子集問題 199
6.2.3 啟發(fā)式貪心算法 200
6.2.4 多頻道情況 202
6.2.5 遭遇圖形著色問題 203
6.2.6 小測(cè)驗(yàn)6.1的答案 204
6.3 可行性檢查 205
6.3.1 改編為可滿足性問題 205
6.3.2 加入邊際約束條件 206
6.3.3 重新安置問題 206
6.3.4 技巧#1：預(yù)解決程序（尋求一種容易的解決之道） 207
6.3.5 技巧#2：預(yù)處理和簡(jiǎn)化 208
6.3.6 技巧#3：SAT解決程序的組合 210
6.3.7 容忍失敗 211
6.3.8 小測(cè)驗(yàn)6.2的答案 211
6.4 降序時(shí)鐘拍賣的實(shí)現(xiàn) 212
6.4.1 拍賣和算法 212
6.4.2 例子 213
6.4.3 重新實(shí)現(xiàn)FCCGreedy算法 214
6.4.4 是時(shí)候提供補(bǔ)償了 216
6.5 最終結(jié)果 217
6.6 本章要點(diǎn) 218
6.7 章末習(xí)題 218
6.7.1 挑戰(zhàn)題 220
6.7.2 編程題 220
后記 算法設(shè)計(jì)實(shí)戰(zhàn)指南 221
附錄 問題提示和答案 224