目 錄
第1部分 算法和算法分析
第1章 算法問(wèn)題求解基礎(chǔ)1
1.1 算法概述1
1.1.1 什么是算法1
1.1.2 為什么學(xué)習(xí)算法3
1.2 問(wèn)題求解方法3
1.2.1 問(wèn)題和問(wèn)題求解4
1.2.2 問(wèn)題求解過(guò)程4
1.2.3 系統(tǒng)生命周期5
1.3 算法設(shè)計(jì)與分析5
1.3.1 算法問(wèn)題求解過(guò)程5
1.3.2 如何設(shè)計(jì)算法6
1.3.3 如何表示算法6
1.3.4 如何確認(rèn)算法6
1.3.5 如何分析算法7
1.4 遞歸和歸納7
1.4.1 遞歸7
1.4.2 遞歸算法示例9
1.4.3 歸納證明11
本章小結(jié)12
習(xí)題113
第2章 算法分析基礎(chǔ)14
2.1 算法復(fù)雜度14
2.1.1 什么是好的算法14
2.1.2 影響程序運(yùn)行時(shí)間的因素15
2.1.3 算法的時(shí)間復(fù)雜度16
2.1.4 使用程序步分析算法17
2.1.5 算法的空間復(fù)雜度18
2.2 漸近表示法19
2.2.1 大O記號(hào)19
2.2.2 ?記號(hào)20
2.2.3 ?記號(hào)21
2.2.4 小o記號(hào)21
2.2.5 算法按時(shí)間復(fù)雜度分類21
2.3 遞推關(guān)系22
2.3.1 遞推方程22
2.3.2 替換方法23
2.3.3 迭代方法23
2.3.4 主方法24
2.4 分?jǐn)偡治?5
2.4.1 聚集方法26
2.4.2 會(huì)計(jì)方法26
2.4.3 勢(shì)能方法27
本章小結(jié)28
習(xí)題228
第3章 伸展樹與跳表30
3.1 伸展樹30
3.1.1 二叉搜索樹30
3.1.2 自調(diào)節(jié)樹和伸展樹30
3.1.3 伸展操作31
3.1.4 伸展樹類32
3.1.5 旋轉(zhuǎn)的實(shí)現(xiàn)34
3.1.6 插入運(yùn)算的實(shí)現(xiàn)34
3.1.7 分?jǐn)偡治?6
3.2 跳表38
3.2.1 什么是跳表38
3.2.2 跳表類39
3.2.3 級(jí)數(shù)分配41
3.2.4 插入運(yùn)算的實(shí)現(xiàn)42
3.2.5 性能分析43
本章小結(jié)44
習(xí)題344


第2部分 算法設(shè)計(jì)策略

第4章 基本搜索和遍歷方法45
4.1 基本概念45
4.2 圖的搜索和遍歷46
4.2.1 搜索方法46
4.2.2 鄰接表類47
4.2.3 廣度優(yōu)先搜索48
4.2.4 深度優(yōu)先搜索50
4.3 雙連通分量53
4.3.1 基本概念53
4.3.2 發(fā)現(xiàn)關(guān)節(jié)點(diǎn)54
4.3.3 構(gòu)造雙連通圖57
4.4 與或圖58
4.4.1 問(wèn)題分解58
4.4.2 判斷與或樹是否可解59
4.4.3 構(gòu)建解樹61
本章小結(jié)62
習(xí)題462
第5章 分治法64
5.1 一般方法64
5.1.1 分治法的基本思想64
5.1.2 算法分析65
5.1.3 數(shù)據(jù)結(jié)構(gòu)66
5.2 求最大最小元67
5.2.1 分治法求解67
5.2.2 時(shí)間分析68
5.3 二分搜索69
5.3.1 分治法求解69
5.3.2 對(duì)半搜索70
5.3.3 二叉判定樹71
5.3.4 搜索算法的時(shí)間下界73
5.4 排序問(wèn)題74
5.4.1 合并排序74
5.4.2 快速排序76
5.4.3 排序算法的時(shí)間下界80
5.5 選擇問(wèn)題82
5.5.1 分治法求解82
5.5.2 隨機(jī)選擇主元82
5.5.3 線性時(shí)間選擇算法84
5.5.4 時(shí)間分析86
5.5.5 允許重復(fù)元素的選擇算法86
5.6 斯特拉森矩陣乘法87
5.6.1 分治法求解87
5.6.2 斯特拉森分治法88
本章小結(jié)88
習(xí)題588
第6章 貪心法91
6.1 一般方法91
6.2 背包問(wèn)題92
6.2.1 問(wèn)題描述92
6.2.2 貪心法求解92
6.2.3 算法正確性94
6.3 帶時(shí)限的作業(yè)排序95
6.3.1 問(wèn)題描述95
6.3.2 貪心法求解95
6.3.3 算法正確性97
6.3.4 可行性判定97
6.3.5 作業(yè)排序貪心算法98
6.3.6 一種改進(jìn)算法99
6.4 最佳合并模式102
6.4.1 問(wèn)題描述102
6.4.2 貪心法求解103
6.4.3 算法正確性104
6.5 最小代價(jià)生成樹105
6.5.1 問(wèn)題描述105
6.5.2 貪心法求解105
6.5.3 普里姆算法106
6.5.4 克魯斯卡爾算法109
6.5.5 算法正確性111
6.6 單源最短路徑111
6.6.1 問(wèn)題描述112
6.6.2 貪心法求解112
6.6.3 迪杰斯特拉算法112
6.6.4 算法正確性115
6.7 磁帶最優(yōu)存儲(chǔ)116
6.7.1 單帶最優(yōu)存儲(chǔ)116
6.7.2 多帶最優(yōu)存儲(chǔ)117
6.8 貪心法的基本要素119
6.8.1 最優(yōu)量度標(biāo)準(zhǔn)119
6.8.2 最優(yōu)子結(jié)構(gòu)119
本章小結(jié)120
習(xí)題6120
第7章 動(dòng)態(tài)規(guī)劃法122
7.1 一般方法和基本要素122
7.1.1 一般方法122
7.1.2 基本要素123
7.1.3 多段圖問(wèn)題123
7.1.4 資源分配問(wèn)題126
7.1.5 關(guān)鍵路徑問(wèn)題127
7.2 每對(duì)結(jié)點(diǎn)間的最短路徑129
7.2.1 問(wèn)題描述129
7.2.2 動(dòng)態(tài)規(guī)劃法求解130
7.2.3 弗洛伊德算法131
7.2.4 算法正確性132
7.3 矩陣連乘132
7.3.1 問(wèn)題描述132
7.3.2 動(dòng)態(tài)規(guī)劃法求解133
7.3.3 矩陣連乘算法134
7.3.4 備忘錄方法136
7.4 最長(zhǎng)公共子序列137
7.4.1 問(wèn)題描述137
7.4.2 動(dòng)態(tài)規(guī)劃法求解137
7.4.3 最長(zhǎng)公共子序列算法138
7.4.4 算法的改進(jìn)140
7.5 最優(yōu)二叉搜索樹140
7.5.1 問(wèn)題描述140
7.5.2 動(dòng)態(tài)規(guī)劃法求解141
7.5.3 最優(yōu)二叉搜索樹算法143
7.6 0/1背包144
7.6.1 問(wèn)題描述144
7.6.2 動(dòng)態(tài)規(guī)劃法求解145
7.6.3 0/1背包算法框架147
7.6.4 0/1背包算法150
7.6.5 性能分析152
7.6.6 使用啟發(fā)式方法153
7.7 流水作業(yè)調(diào)度154
7.7.1 問(wèn)題描述154
7.7.2 動(dòng)態(tài)規(guī)劃法求解155
7.7.3 Johnson算法157
本章小結(jié)158
習(xí)題7158
第8章 回溯法160
8.1 一般方法160
8.1.1 基本概念160
8.1.2 剪枝函數(shù)和回溯法161
8.1.3 回溯法的效率分析163
8.2 n-皇后163
8.2.1 問(wèn)題描述163
8.2.2 回溯法求解164
8.2.3 n-皇后算法165
8.2.4 時(shí)間分析166
8.3 子集和數(shù)167
8.3.1 問(wèn)題描述167
8.3.2 回溯法求解167
8.3.3 子集和數(shù)算法168
8.4 圖的著色170
8.4.1 問(wèn)題描述170
8.4.2 回溯法求解170
8.4.3 圖著色算法171
8.4.4 時(shí)間分析172
8.5 哈密頓環(huán)172
8.5.1 問(wèn)題描述172
8.5.2 哈密頓環(huán)算法173
8.6 0/1背包174
8.6.1 問(wèn)題描述174
8.6.2 回溯法求解174
8.6.3 限界函數(shù)175
8.6.4 0/1背包算法176
8.7 批處理作業(yè)調(diào)度178
8.7.1 問(wèn)題描述178
8.7.2 回溯法求解178
8.7.3 批處理作業(yè)調(diào)度算法178
本章小結(jié)180
習(xí)題8180
第9章 分枝限界法182
9.1 一般方法182
9.1.1 分枝限界法概述182
9.1.2 LC分枝限界法184
9.1.3 15謎問(wèn)題185
9.2 求最優(yōu)解的分枝限界法187
9.2.1 上下界函數(shù)187
9.2.2 FIFO分枝限界法188
9.2.3 LC分枝限界法189
9.3 帶時(shí)限的作業(yè)排序190
9.3.1 問(wèn)題描述190
9.3.2 分枝限界法求解190
9.3.3 帶時(shí)限作業(yè)排序算法191
9.4 0/1背包193
9.4.1 問(wèn)題描述193
9.4.2 分枝限界法求解194
9.4.3 0/1背包算法195
9.5 旅行商問(wèn)題197
9.5.1 問(wèn)題描述197
9.5.2 分枝限界法求解198
9.6 批處理作業(yè)調(diào)度201
9.6.1 問(wèn)題描述201
9.6.2 分枝限界法求解201
9.6.3 批處理作業(yè)調(diào)度算法202
本章小結(jié)205
習(xí)題9205

第3部分 求解困難問(wèn)題

第10章 NP完全問(wèn)題207
10.1 基本概念207
10.1.1 不確定算法和不確定機(jī)208
10.1.2 可滿足性問(wèn)題210
10.1.3 P類和NP類問(wèn)題211
10.1.4 NP難度和NP完全問(wèn)題211
10.2 Cook定理和證明212
10.2.1 Cook定理212
10.2.2 簡(jiǎn)化的不確定機(jī)模型212
10.2.3 證明Cook定理214
10.3 一些典型的NP完全問(wèn)題217
10.3.1 最大集團(tuán)217
10.3.2 頂點(diǎn)覆蓋218
10.3.3 三元CNF可滿足性219
10.3.4 圖的著色數(shù)220
10.3.5 有向哈密頓環(huán)221
10.3.6 恰切覆蓋223
10.3.7 子集和數(shù)225
10.3.8 分劃問(wèn)題225
本章小結(jié)226
習(xí)題10226
第11章 隨機(jī)算法228
11.1 基本概念228
11.1.1 隨機(jī)算法概述228
11.1.2 隨機(jī)數(shù)發(fā)生器228
11.1.3 隨機(jī)算法分類228
11.2 拉斯維加斯算法229
11.2.1 標(biāo)識(shí)重復(fù)元素算法229
11.2.2 性能分析230
11.3 蒙特卡羅算法231
11.3.1 素?cái)?shù)測(cè)試問(wèn)題231
11.3.2 偽素?cái)?shù)測(cè)試231
11.3.3 米勒-拉賓算法232
11.3.4 性能分析233
11.4 舍伍德算法234
11.4.1 隨機(jī)快速排序算法234
11.4.2 舍伍德算法的其他應(yīng)用234
本章小結(jié)234
習(xí)題11235
第12章 近似算法236
12.1 近似算法的性能236
12.1.1 基本概念236
12.1.2 絕對(duì)性能保證236
12.1.3 相對(duì)性能保證237
12.1.4 近似方案238
12.2 絕對(duì)近似算法238
12.2.1 最多程序存儲(chǔ)問(wèn)題238
12.2.2 NP難度絕對(duì)近似算法239
12.3 ?-近似算法240
12.3.1 頂點(diǎn)覆蓋近似算法240
12.3.2 旅行商問(wèn)題241
12.3.3 NP難度?-近似旅行商問(wèn)題242
12.3.4 具有三角不等式性質(zhì)的旅行商問(wèn)題243
12.3.5 任務(wù)調(diào)度近似算法244
12.4 ?(n)-近似算法247
12.4.1 集合覆蓋問(wèn)題247
12.4.2 集合覆蓋近似算法247
12.4.3 ln(n)-近似算法248
12.5 多項(xiàng)式時(shí)間近似方案249
12.5.1 任務(wù)調(diào)度近似方案249
12.5.2 多項(xiàng)式時(shí)間近似方案251
12.6 子集和數(shù)的完全多項(xiàng)式時(shí)間近似方案251
12.6.1 子集和數(shù)的指數(shù)時(shí)間算法251
12.6.2 完全多項(xiàng)式時(shí)間近似方案252
本章小結(jié)254
習(xí)題12254
第13章 遺傳算法256
13.1 進(jìn)化計(jì)算256
13.2 遺傳算法的生物學(xué)基礎(chǔ)257
13.3 遺傳算法的基本思想258
13.4 基本遺傳算法259
13.4.1 基本遺傳算法構(gòu)成要素259
13.4.2 基本遺傳算法流程圖262
13.5 遺傳算法的特點(diǎn)和應(yīng)用262
13.5.1 遺傳算法的特點(diǎn)2