算法設(shè)計

目　錄
第 1章　引言：一些典型問題　1
1．1　第 一個問題：穩(wěn)定匹配　1
1．2　5個典型問題　8
帶解答的練習(xí)　12
練習(xí)　14
注釋和進一步閱讀　17
第 2章　算法分析基礎(chǔ)　18
2．1 計算可解性　18
2．2 增長的漸近階　21
2．3 用列表和數(shù)組實現(xiàn)穩(wěn)定匹配算法　26
2．4 常見運行時間綜述　29
2．5 更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)：優(yōu)先隊列　35
帶解答的練習(xí)　40
練習(xí)　41
注釋和進一步閱讀　44
第3章　圖　45
3．1 基本定義和應(yīng)用　45
3．2 圖連通性和圖遍歷　48
3．3 用隊列和棧實現(xiàn)圖遍歷　53
3．4 二分性測試：廣度優(yōu)先搜索的應(yīng)用　58
3．5 有向圖中的連通性　59
3．6 有向無環(huán)圖和拓撲排序　61
帶解答的練習(xí)　64
練習(xí)　66
注釋和進一步閱讀　69
第4章　貪心算法　70
4．1 區(qū)間調(diào)度：貪心算法保持領(lǐng)先　70
4．2 最小化延遲的調(diào)度：交換論證　76
4．3 最優(yōu)緩存：更復(fù)雜的交換論證　80
4．4 圖的最短路徑　83
4．5 最小生成樹問題　87
4．6 實現(xiàn)Kruskal算法：Union-Find數(shù)據(jù)結(jié)構(gòu)　92
4．7 聚類　97
4．8 哈夫曼碼和數(shù)據(jù)壓縮　99
*4．9 最小開銷樹形圖：多階段貪心算法　109
帶解答的練習(xí)　113
練習(xí)　116
注釋和進一步閱讀　125
第5章　分治　127
5．1 第 一個遞推式：歸并排序算法　127
5．2 進一步的遞推關(guān)系　130
5．3 計數(shù)逆序　134
5．4 尋找最近點對　137
5．5 整數(shù)乘法　141
5．6 卷積和快速傅里葉變換　142
帶解答的練習(xí)　148
練習(xí)　150
注釋和進一步閱讀　152
第6章　動態(tài)規(guī)劃　153
6．1 加權(quán)區(qū)間調(diào)度：遞歸過程　153
6．2 動態(tài)規(guī)劃原理：備忘錄或子問題迭代　157
6．3 分段最小二乘：多重選擇　159
6．4 子集和與背包：加一個變量　162
6．5 RNA二級結(jié)構(gòu)：區(qū)間上的動態(tài)規(guī)劃　166
6．6 序列比對　169
6．7 通過分治在線性空間中序列比對　173
6．8 圖中的最短路徑　177
6．9 最短路徑和距離向量協(xié)議　182
*6．10 圖中的負環(huán)　184
帶解答的練習(xí)　187
練習(xí)　190
注釋和進一步閱讀　204
第7章　網(wǎng)絡(luò)流　205
7．1 最大流問題和Ford-Fulkerson算法　205
7．2 網(wǎng)絡(luò)中的最大流和最小割　211
7．3 選擇好的增廣路徑　214
*7．4 預(yù)流推進最大流算法　218
7．5 第 一個應(yīng)用：二分匹配問題　225
7．6 有向圖和無向圖中的不相交路徑　228
7．7 最大流問題的擴展　232
7．8 調(diào)查設(shè)計　236
7．9 航空公司調(diào)度　237
7．10 圖像分割　240
7．11 項目選擇　243
7．12 棒球排除　246
*7．13 進一步的方向：為匹配問題增加開銷　249
帶解答的練習(xí)　253
練習(xí)　255
注釋和進一步閱讀　274
第8章　NP和計算難解性　276
8．1 多項式時間歸約　276
8．2 通過“小配件”歸約：可滿足性問題　280
8．3 有效證書和NP的定義　283
8．4 NP完全問題　285
8．5 排序問題　289
8．6 劃分問題　294
8．7 圖著色　297
8．8 數(shù)值問題　300
8．9 co-NP和NP的不對稱性　303
8．10 困難問題的部分分類　305
帶解答的練習(xí)　307
練習(xí)　309
注釋和進一步閱讀　323
第9章　PSPACE：NP之外的一類問題　324
9．1 PSPACE　324
9．2 PSPACE中的一些難題　325
9．3 在多項式空間中求解量化問題和博弈　327
9．4 在多項式空間中求解規(guī)劃問題　328
9．5 證明問題是PSPACE完全的　331
帶解答的練習(xí)　334
練習(xí)　335
注釋和進一步閱讀　336
第 10章　擴展易解性的界限　337
10．1 尋找小的頂點覆蓋　338
10．2 求解樹上的NP困難問題　340
10．3 圓弧集著色　343
*10．4 圖的樹分解　349
*10．5 構(gòu)造樹分解　356
帶解答的練習(xí)　361
練習(xí)　363
注釋和進一步閱讀　365
第 11章　近似算法　366
11．1 貪心算法和最優(yōu)值的界限：負載均衡問題　366
11．2 中心選址問題　370
11．3 集合覆蓋：一般貪心啟發(fā)式　374
11．4 定價方法：頂點覆蓋　378
11．5 用定價方法最大化：不相交路徑問題　382
11．6 線性規(guī)劃和舍入：頂點覆蓋的應(yīng)用　386
*11．7 再論負載均衡：更高級的LP應(yīng)用　390
11．8 任意好的近似：背包問題　394
帶解答的練習(xí)　398
練習(xí)　399
注釋和進一步閱讀　404
第 12章　局部搜索　406
12．1 優(yōu)化問題的地形　406
12．2 Metropolis算法和模擬退火算法　409
12．3 局部搜索在Hopfield神經(jīng)網(wǎng)絡(luò)中的應(yīng)用　412
12．4 通過局部搜索的最大割近似　415
12．5 選擇鄰居關(guān)系　417
*12．6 用局部搜索分類　418
12．7 最優(yōu)響應(yīng)動態(tài)和納什均衡　423
帶解答的練習(xí)　430
練習(xí)　431
注釋和進一步閱讀　433
第 13章　隨機算法　434
13．1 第 一個應(yīng)用：消除爭用　435
13．2 尋找全局最小割　438
13．3 隨機變量及其期望　442
13．4 MAX 3-SAT的隨機近似算法　445
13．5 隨機分治：找中位數(shù)和Quicksort　447
13．6 哈希：字典的隨機實現(xiàn)　452
13．7 尋找最近點對：隨機方法　457
13．8 隨機緩存　462
13．9 切爾諾夫界　467
13．10 負載均衡　468
13．11 分組路由　470
13．12 背景知識：一些基本概率定義　474
帶解答的練習(xí)　479
練習(xí)　483
注釋和進一步閱讀　489
后記：永遠運行的算法　491
參考文獻　497