博客來
演算法詳解系列圖書共有4卷，本書是第4卷——NP-Hard問題演算法。全書共有6章，主要介紹了快速識別NP-Hard問題的方法和處理NP的演算法工具。本書的每一章均有小測驗、章末習題，這為讀者的自我檢查以及進一步學習提供了方便。
本書提供了豐富而實用的資料，能夠説明讀者提升演算法思維能力。本書適合電腦專業的高校教師和學生，想要培養和訓練演算法思維與計算思維的IT專業人士，以及正在準備面試的應聘者和麵試官閱讀參考。
| FindBook |
有 1 項符合
算法詳解(卷4)--NP-Hard問題算法的圖書 |
 |
算法詳解(卷4)--NP-Hard問題算法 作者：（美）蒂姆·拉夫加登 ／ 譯者：徐波 出版社：人民郵電出版社 出版日期：2023-09-01 語言：簡體中文 規格：平裝 / 234頁 / 19 x 26 x 1.17 cm / 普通級/ 1-1 |
| 圖書館借閱 |
| 國家圖書館 | 全國圖書書目資訊網 | 國立公共資訊圖書館 | 電子書服務平台 | MetaCat 跨館整合查詢 |
| 臺北市立圖書館 | 新北市立圖書館 | 基隆市公共圖書館 | 桃園市立圖書館 | 新竹縣公共圖書館 |
| 苗栗縣立圖書館 | 臺中市立圖書館 | 彰化縣公共圖書館 | 南投縣文化局 | 雲林縣公共圖書館 |
| 嘉義縣圖書館 | 臺南市立圖書館 | 高雄市立圖書館 | 屏東縣公共圖書館 | 宜蘭縣公共圖書館 |
| 花蓮縣文化局 | 臺東縣文化處 |
|
|
圖書介紹 - 資料來源：博客來 評分：
圖書名稱：算法詳解(卷4)--NP-Hard問題算法
內容簡介
作者介紹
蒂姆·拉夫加登（Tim Roughgarden）是哥倫比亞大學電腦科學系的教授，之前曾任教於斯坦福大學電腦科學系，他從2004年開始教授和研究演算法。本書是他的《演算法詳解》四部曲的第三卷，基於他從2012年開始定期舉行的線上演算法課程編寫。
目錄
第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
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
|
