算法設(shè)計(jì)與分析（第4版）

目錄CONTENTS
第1章算法引論1
1.1算法與程序1
1.2表達(dá)算法的抽象機(jī)制1
1.3描述算法3
1.4算法復(fù)雜性分析10
小結(jié)13
習(xí)題14
第2章遞歸與分治策略16
2.1遞歸的概念16
2.2分治法的基本思想21
2.3二分搜索技術(shù)23
2.4大整數(shù)的乘法23
2.5Strassen矩陣乘法24
2.6棋盤(pán)覆蓋26
2.7合并排序28
2.8快速排序30
2.9線(xiàn)性時(shí)間選擇33
2.10最接近點(diǎn)對(duì)問(wèn)題35
2.11循環(huán)賽日程表43
小結(jié)44
習(xí)題44
第3章動(dòng)態(tài)規(guī)劃50
3.1矩陣連乘問(wèn)題50
3.2動(dòng)態(tài)規(guī)劃算法的基本要素55
3.3最長(zhǎng)公共子序列58
3.4凸多邊形最優(yōu)三角剖分61
3.5多邊形游戲64
3.6圖像壓縮67
3.7電路布線(xiàn)69
3.8流水作業(yè)調(diào)度72
3.90\\|1背包問(wèn)題75
3.10最優(yōu)二叉搜索樹(shù)80
小結(jié)83
習(xí)題83
目錄算法設(shè)計(jì)與分析(第4版)第4章貪心算法85
4.1活動(dòng)安排問(wèn)題85
4.2貪心算法的基本要素88
4.2.1貪心選擇性質(zhì)88
4.2.2最優(yōu)子結(jié)構(gòu)性質(zhì)89
4.2.3貪心算法與動(dòng)態(tài)規(guī)劃算法的差異89
4.3最優(yōu)裝載91
4.4哈夫曼編碼92
4.4.1前綴碼93
4.4.2構(gòu)造哈夫曼編碼93
4.4.3哈夫曼算法的正確性95
4.5單源最短路徑96
4.5.1算法基本思想97
4.5.2算法的正確性和計(jì)算復(fù)雜性98
4.6最小生成樹(shù)99
4.6.1最小生成樹(shù)性質(zhì)99
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多機(jī)調(diào)度問(wèn)題104
4.8貪心算法的理論基礎(chǔ)106
4.8.1擬陣106
4.8.2帶權(quán)擬陣的貪心算法107
4.8.3任務(wù)時(shí)間表問(wèn)題109
小結(jié)113
習(xí)題113
第5章回溯法115
5.1回溯法的算法框架115
5.1.1問(wèn)題的解空間115
5.1.2回溯法的基本思想116
5.1.3遞歸回溯117
5.1.4迭代回溯118
5.1.5子集樹(shù)與排列樹(shù)119
5.2裝載問(wèn)題120
5.3批處理作業(yè)調(diào)度126
5.4符號(hào)三角形問(wèn)題128
5.5n后問(wèn)題130
5.601背包問(wèn)題133
5.7最大團(tuán)問(wèn)題136
5.8圖的m著色問(wèn)題138
5.9旅行售貨員問(wèn)題140
5.10圓排列問(wèn)題142
5.11電路板排列問(wèn)題144
5.12連續(xù)郵資問(wèn)題147
5.13回溯法的效率分析149
小結(jié)152
習(xí)題152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2單源最短路徑問(wèn)題156
6.3裝載問(wèn)題158
6.4布線(xiàn)問(wèn)題166
6.501背包問(wèn)題170
6.6最大團(tuán)問(wèn)題175
6.7旅行售貨員問(wèn)題178
6.8電路板排列問(wèn)題181
6.9批處理作業(yè)調(diào)度184
小結(jié)189
習(xí)題189
第7章概率算法190
7.1隨機(jī)數(shù)191
7.2數(shù)值概率算法193
7.2.1用隨機(jī)投點(diǎn)法計(jì)算π值193
7.2.2計(jì)算定積分194
7.2.3解非線(xiàn)性方程組195
7.3舍伍德算法197
7.3.1線(xiàn)性時(shí)間選擇算法198
7.3.2跳躍表200
7.4拉斯維加斯算法205
7.4.1n后問(wèn)題206
7.4.2整數(shù)因子分解209
7.5蒙特卡羅算法211
7.5.1蒙特卡羅算法的基本思想211
7.5.2主元素問(wèn)題213
7.5.3素?cái)?shù)測(cè)試214
小結(jié)217
習(xí)題217
第8章NP完全性理論與近似算法221
8.1P類(lèi)與NP類(lèi)問(wèn)題221
8.1.1非確定性圖靈機(jī)222
8.1.2P類(lèi)與NP類(lèi)語(yǔ)言222
8.1.3多項(xiàng)式時(shí)間驗(yàn)證224
8.2NP完全問(wèn)題225
8.2.1多項(xiàng)式時(shí)間變換225
8.2.2Cook定理226
8.3一些典型的NP完全問(wèn)題229
8.3.1合取范式的可滿(mǎn)足性問(wèn)題230
8.3.23元合取范式的可滿(mǎn)足性問(wèn)題230
8.3.3團(tuán)問(wèn)題231
8.3.4頂點(diǎn)覆蓋問(wèn)題232
8.3.5子集和問(wèn)題233
8.3.6哈密頓回路問(wèn)題235
8.3.7旅行售貨員問(wèn)題238
8.4近似算法的性能238
8.5頂點(diǎn)覆蓋問(wèn)題的近似算法240
8.6旅行售貨員問(wèn)題近似算法241
8.6.1具有三角不等式性質(zhì)的旅行售貨員問(wèn)題242
8.6.2一般的旅行售貨員問(wèn)題243
8.7集合覆蓋問(wèn)題的近似算法244
8.8子集和問(wèn)題的近似算法246
8.8.1子集和問(wèn)題的指數(shù)時(shí)間算法247
8.8.2子集和問(wèn)題的完全多項(xiàng)式時(shí)間近似格式247
小結(jié)250
習(xí)題250
第9章串與序列的算法253
9.1子串搜索算法253
9.1.1串的基本概念253
9.1.2KMP算法255
9.1.3RabinKarp算法258
9.1.4多子串搜索與AC自動(dòng)機(jī)260
9.2后綴數(shù)組與最長(zhǎng)公共子串266
9.2.1后綴數(shù)組的基本概念266
9.2.2構(gòu)造后綴數(shù)組的倍前綴算法267
9.2.3構(gòu)造后綴數(shù)組的DC3分治法270
9.2.4最長(zhǎng)公共前綴數(shù)組與最長(zhǎng)公共擴(kuò)展算法274
9.2.5最長(zhǎng)公共子串算法276
9.3序列比較算法277
9.3.1編輯距離算法277
9.3.2最長(zhǎng)公共單調(diào)子序列280
9.3.3有約束最長(zhǎng)公共子序列281
小結(jié)284
習(xí)題285
第10章算法優(yōu)化策略288
10.1算法設(shè)計(jì)策略的比較與選擇288
10.1.1最大子段和問(wèn)題的簡(jiǎn)單算法288
10.1.2最大子段和問(wèn)題的分治算法289
10.1.3最大子段和問(wèn)題的動(dòng)態(tài)規(guī)劃算法291
10.1.4最大子段和問(wèn)題與動(dòng)態(tài)規(guī)劃算法的推廣291
10.2動(dòng)態(tài)規(guī)劃加速原理294
10.2.1貨物儲(chǔ)運(yùn)問(wèn)題294
10.2.2算法及其優(yōu)化295
10.3問(wèn)題的算法特征298
10.3.1貪心策略298
10.3.2對(duì)貪心策略的改進(jìn)299
10.3.3算法三部曲299
10.3.4算法實(shí)現(xiàn)300
10.3.5算法復(fù)雜性305
10.4優(yōu)化數(shù)據(jù)結(jié)構(gòu)306
10.4.1帶權(quán)區(qū)間最短路問(wèn)題306
10.4.2算法設(shè)計(jì)思想306
10.4.3算法實(shí)現(xiàn)方案308
10.4.4并查集311
10.4.5可并優(yōu)先隊(duì)列314
10.5優(yōu)化搜索策略318
小結(jié)324
習(xí)題324
第11章在線(xiàn)算法設(shè)計(jì)325
11.1在線(xiàn)算法設(shè)計(jì)的基本概念325
11.2頁(yè)調(diào)度問(wèn)題327
11.3勢(shì)函數(shù)分析329
11.4k服務(wù)問(wèn)題330
11.4.1競(jìng)爭(zhēng)比的下界330
11.4.2平衡算法331
11.4.3對(duì)稱(chēng)移動(dòng)算法332
11.5Steiner樹(shù)問(wèn)題334
11.6在線(xiàn)任務(wù)調(diào)度336
11.7負(fù)載平衡337
小結(jié)338
習(xí)題338
詞匯索引340
參考文獻(xiàn)345