演演算法設計與分析

為了適應培養我國21世紀計算機各類人才的需要，結合我國高等學校教育工作的現狀，立足培養學生能跟上國際計算機科學技術的發展水平，更新教學內容和教學方法，提高教學質量，本書以演演算法設計策略為知識單元，系統地介紹計算機演演算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機演演算法基礎知識。

本書內容豐富，觀點新穎，理論聯繫實際。不僅可用作高等學校計算機專業本科生和研究生學習計算機演演算法設計的教材，而且也適合廣大工程技術人員和自學讀者學習參考。

第1章演演算法引論11.1演演算法與程序1

1.2表達演演算法的抽象機制1

1.3描述演演算法3

1.4演演算法複雜性分析11

小結14

習題14

第2章遞歸與分治策略16

2.1遞歸的概念16

2.2分治法的基本思想22

2.3二分搜索技術23

2.4大整數的乘法24

2.5Strassen矩陣乘法25

2.6棋盤覆蓋26

2.7合併排序28

2.8快速排序30

2.9線性時間選擇33

2.10最接近點對問題36

2.11循環賽日程表43

小結44

習題45

第3章動態規劃50

3.1矩陣連乘問題50

3.2動態規劃演演算法的基本要素55

3.3最長公共子序列58

3.4凸多邊形最優三角剖分61

3.5多邊形遊戲64目錄演演算法設計與分析(第3版)3.6圖像壓縮67

3.7電路布線70

3.8流水作業調度72

3.90\|1背包問題75

3.10最優二叉搜索樹80

小結83

習題84

第4章貪心演演算法85

4.1活動安排問題85

4.2貪心演演算法的基本要素88

4.2.1貪心選擇性質88

4.2.2最優子結構性質88

4.2.3貪心演演算法與動態規劃演演算法的差異89

4.3最優裝載91

4.4哈夫曼編碼92

4.4.1前綴碼93

4.4.2構造哈夫曼編碼93

4.4.3哈夫曼演演算法的正確性95

4.5單源最短路徑97

4.5.1演演算法基本思想97

4.5.2演演算法的正確性和計算複雜性99

4.6最小生成樹100

4.6.1最小生成樹性質100

4.6.2Prim演演算法100

4.6.3Kruskal演演算法102

4.7多機調度問題104

4.8貪心演演算法的理論基礎106

4.8.1擬陣107

4.8.2帶權擬陣的貪心演演算法108

4.8.3任務時間表問題110

小結113

習題113

第5章回溯法115

5.1回溯法的演演算法框架115

5.1.1問題的解空間115

5.1.2回溯法的基本思想116

5.1.3遞歸回溯117

5.1.4迭代回溯118

5.1.5子集樹與排列樹119

5.2裝載問題120

5.3批處理作業調度126

5.4符號三角形問題128

5.5n后問題130

5.601背包問題133

5.7最大團問題136

5.8圖的m著色問題138

5.9旅行售貨員問題140

5.10圓排列問題142

5.11電路板排列問題144

5.12連續郵資問題147

5.13回溯法的效率分析149

小結152

習題152

第6章分支限界法153

6.1分支限界法的基本思想153

6.2單源最短路徑問題156

6.3裝載問題158

6.4布線問題167

6.501背包問題171

6.6最大團問題175

6.7旅行售貨員問題178

6.8電路板排列問題182

6.9批處理作業調度184

小結189

習題189

第7章概率演演算法190

7.1隨機數191

7.2數值概率演演算法193

7.2.1用隨機投點法計算π值193

7.2.2計算定積分194

7.2.3解非線性方程組196

7.3舍伍德演演算法198

7.3.1線性時間選擇演演算法198

7.3.2跳躍表200

7.4拉斯維加斯演演算法205

7.4.1n后問題206

7.4.2整數因子分解209

7.5蒙特卡羅演演算法211

7.5.1蒙特卡羅演演算法的基本思想211

7.5.2主元素問題213

7.5.3素數測試214

小結217

習題217

第8章NP完全性理論221

8.1計算模型221

8.1.1隨機存取機RAM222

8.1.2隨機存取存儲程序機RASP228

8.1.3RAM模型的變形與簡化231

8.1.4圖靈機235

8.1.5圖靈機模型與RAM模型的關係236

8.1.6問題變換與計算複雜性歸約238

8.2P類與NP類問題239

8.2.1非確定性圖靈機239

8.2.2P類與NP類語言240

8.2.3多項式時間驗證241

8.3NP完全問題243

8.3.1多項式時間變換243

8.3.2Cook定理244

8.4一些典型的NP完全問題247

8.4.1合取範式的可滿足性問題247

8.4.23元合取範式的可滿足性問題248

8.4.3團問題249

8.4.4頂點覆蓋問題250

8.4.5子集和問題251

8.4.6哈密頓迴路問題252

8.4.7旅行售貨員問題256

小結256

習題257

第9章近似演演算法259

9.1近似演演算法的性能259

9.2頂點覆蓋問題的近似演演算法260

9.3旅行售貨員問題近似演演算法262

9.3.1具有三角不等式性質的旅行售貨員問題262

9.3.2一般的旅行售貨員問題263

9.4集合覆蓋問題的近似演演算法264

9.5子集和問題的近似演演算法267

9.5.1子集和問題的指數時間演演算法267

9.5.2子集和問題的完全多項式時間近似格式268

小結270

習題270

第10章演演算法優化策略273

10.1演演算法設計策略的比較與選擇273

10.1.1最大子段和問題的簡單演演算法273

10.1.2最大子段和問題的分治演演算法274

10.1.3最大子段和問題的動態規劃演演算法275

10.1.4最大子段和問題與動態規劃演演算法的推廣276

10.2動態規劃加速原理279

10.2.1貨物儲運問題279

10.2.2演演算法及其優化279

10.3問題的演演算法特徵283

10.3.1貪心策略283

10.3.2對貪心策略的改進283

10.3.3演演算法三部曲285

10.3.4演演算法實現285

10.3.5演演算法複雜性290

10.4優化數據結構291

10.4.1帶權區間最短路問題291

10.4.2演演算法設計思想291

10.4.3演演算法實現方案293

10.4.4並查集296

10.4.5可並優先隊列298

10.5優化搜索策略302

小結308

習題309

第11章在線演演算法設計310

11.1在線演演算法設計的基本概念310

11.2頁調度問題312

11.3勢函數分析314

11.4k服務問題315

11.4.1競爭比的下界315

11.4.2平衡演演算法316

11.4.3對稱移動演演算法317

11.5Steiner樹問題320

11.6在線任務調度321

11.7負載平衡322

小結323

習題324

辭彙索引325

參考文獻330