算法詳解：NP-Hard問(wèn)題算法（卷4）

第 1章 什么是NP問(wèn)題 1
1.1 MST和TSP：算法的難解之謎 2
1.1.1 最小生成樹(shù)問(wèn)題 2
1.1.2 旅行商問(wèn)題 3
1.1.3 解決TSP的嘗試和失敗 4
1.1.4 小測(cè)驗(yàn)1.1?C1.2的答案 6
1.2 讀者的不同專(zhuān)業(yè)層次 7
1.3 容易的問(wèn)題和困難的問(wèn)題 8
1.3.1多項(xiàng)式時(shí)間的算法 9
1.3.2 多項(xiàng)式時(shí)間與指數(shù)級(jí)時(shí)間 10
1.3.3 容易的問(wèn)題 11
1.3.4 相對(duì)難以處理 12
1.3.5 困難的問(wèn)題 12
1.3.6 P≠NP猜想 14
1.3.7 NP問(wèn)題的臨時(shí)定義 14
1.3.8 隨機(jī)化和量子算法 15
1.3.9 微妙性 15
1.4 NP問(wèn)題的算法策略 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問(wèn)題：一個(gè)簡(jiǎn)單的方案 21
1.5.1 轉(zhuǎn)化 22
1.5.2 使用轉(zhuǎn)化來(lái)設(shè)計(jì)快速算法 23
1.5.3 使用轉(zhuǎn)化對(duì)NP問(wèn)題進(jìn)行擴(kuò)展 25
1.5.4 無(wú)環(huán)最短路徑是NP問(wèn)題 26
1.5.5 小測(cè)驗(yàn)1.3的答案 30
1.6 新手錯(cuò)誤和可接受的不準(zhǔn)確說(shuō)法 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 問(wèn)題定義 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 問(wèn)題定義 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 影響最大化問(wèn)題 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 通過(guò)2-變換改進(jìn)路線(xià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 底線(xiàn)：窮舉搜索 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 子問(wèn)題 103
3.1.6 Bellman-Held-Karp算法 104
3.1.7 小測(cè)驗(yàn)3.1的答案 105
*3.2 通過(guò)顏色編碼尋找最長(zhǎng)路徑 106
3.2.1 動(dòng)機(jī) 107
3.2.2 問(wèn)題定義 107
3.2.3 子問(wèn)題的初次試探 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 問(wèn)題特定的算法與萬(wàn)能魔盒 119
3.3.1 轉(zhuǎn)化和萬(wà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 例子：背包問(wèn)題 122
3.4.2 更基本意義上的MIP 124
3.4.3 MIP解決程序：一些起點(diǎn) 125
3.5 可滿(mǎn)足性解決程序 126
3.5.1 示例：圖形著色 126
3.5.2 可滿(mǎn)足性 127
3.5.3 把圖形著色問(wèn)題表達(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問(wèn)題 138
4.1 再論轉(zhuǎn)化 138
4.2 3-SAT問(wèn)題和Cook-Levin定理 140
4.3 整體思路 142
4.3.1 再論新手易犯的錯(cuò)誤 142
4.3.2 18個(gè)轉(zhuǎn)化 142
4.3.3 為什么要啃艱澀的NP問(wèn)題證明？ 144
4.3.4 小測(cè)驗(yàn)4.1的答案 145
4.4 一個(gè)轉(zhuǎn)化模板 145
4.5 獨(dú)立子集問(wèn)題是NP問(wèn)題 147
4.5.1 主要思路 147
4.5.2 定理4.2的證明 150
*4.6 有向漢密爾頓路徑問(wèn)題是NP問(wèn)題 152
4.6.1 變量的編碼和真值指派 153
4.6.2 約束條件的編碼 154
4.6.3 定理4.4的證明 156
4.7 TSP是NP問(wèn)題 158
4.7.1 無(wú)向漢密爾頓路徑問(wèn)題 158
4.7.2 定理4.7的證明 159
4.8 子集求和問(wèn)題是NP問(wèn)題 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 通過(guò)轉(zhuǎn)化創(chuàng)建一個(gè)案例 171
5.1.2 為T(mén)SP選擇集合C 172
*5.2 決策、搜索和優(yōu)化 173
*5.3 NP：具有容易識(shí)別的解決方案的問(wèn)題 174
5.3.1 復(fù)雜類(lèi)NP的定義 174
5.3.2 NP中的問(wèn)題實(shí)例 175
5.3.3 NP問(wèn)題是可以通過(guò)窮舉搜索解決的 176
5.3.4 NP問(wèn)題 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問(wèn)題 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問(wèn)題需要指數(shù)級(jí)的時(shí)間嗎？ 183
5.5.2 強(qiáng)指數(shù)級(jí)時(shí)間假設(shè)（SETH） 184
5.5.3 容易問(wèn)題的運(yùn)行時(shí)間下界 185
*5.6 NP完全問(wèn)題 187
5.6.1 Levin轉(zhuǎn)化 187
5.6.2 NP中最難的問(wèn)題 189
5.6.3 NP完全問(wèn)題的存在 189
5.7 本章要點(diǎn) 191
5.8 章末習(xí)題 192
第6章 案例研究：FCC激勵(lì)拍賣(mài) 195
6.1 無(wú)線(xiàn)頻譜再利用 195
6.1.1 從電視到移動(dòng)電話(huà) 195
6.1.2 無(wú)線(xiàn)頻譜的一次最近重分配 196
6.2 回購(gòu)執(zhí)照的啟發(fā)式貪心算法 198
6.2.1 4個(gè)臨時(shí)的簡(jiǎn)化假設(shè) 198
6.2.2 遭遇加權(quán)獨(dú)立子集問(wèn)題 199
6.2.3 啟發(fā)式貪心算法 200
6.2.4 多頻道情況 202
6.2.5 遭遇圖形著色問(wèn)題 203
6.2.6 小測(cè)驗(yàn)6.1的答案 204
6.3 可行性檢查 205
6.3.1 改編為可滿(mǎn)足性問(wèn)題 205
6.3.2 加入邊際約束條件 206
6.3.3 重新安置問(wèn)題 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í)鐘拍賣(mài)的實(shí)現(xiàn) 212
6.4.1 拍賣(mài)和算法 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
附錄 問(wèn)題提示和答案 224