為了適應培養(yǎng)我國２１世紀計算機各類人才的需要，結合我國高等學校教育工作的現(xiàn)狀，立足培養(yǎng)學生能跟上國際計算機科學技術的發(fā)展水平，更新教學內容和教學方法，提高教學質量，本書以算法設計策略為知識單元，系統(tǒng)地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機算法基礎知識。另有配套的《算法設計與分析（第4版）習題解答》，對本書的全部習題做了詳盡的解答。
本書內容豐富，觀點新穎，理論聯(lián)系實際。不僅可用作高等學校計算機專業(yè)本科生和研究生學習計算機算法設計的教材，而且也適合廣大工程技術人員和自學讀者學習參考。
本書按照教育部*制定的計算機科學與技術專業(yè)規(guī)范的教學大綱編寫，努力與國際計算機學科的教學要求接軌。強調算法與數(shù)據(jù)結構之間密不可分的聯(lián)系，因而強調融數(shù)據(jù)類型與定義在該類型上的運算于一體的抽象數(shù)據(jù)類型，為面向對象的程序設計方法奠定基礎，體現(xiàn)計算機科學方法論的理論、抽象和設計三個過程，知識面較寬，且有一定的深度；反復再現(xiàn)計算機科學中用到的大問題的復雜性、效率、抽象的層次、重用、折衷等帶有普遍性的概念，讓讀者在更深的層次上掌握算法與數(shù)據(jù)結構這一主科目。
21世紀大學本科計算機專業(yè)系列教材編委會
主任： 李曉明副主任： 蔣宗禮盧先和委員： （按姓氏筆畫為序）
馬華東馬殿富王志英王曉東寧洪
劉辰孫茂松李仁發(fā)李文新楊波
吳朝暉何炎祥宋方敏張莉金海
周興社孟祥旭袁曉潔錢樂秋黃國興
曾明廖明宏秘書： 張瑞慶
本書責任編委： 宋方敏
前言FOREWORD
以最低的成本、最快的速度、最好的質量開發(fā)出適合各種應用需求的軟件，必須遵循軟件工程的原則，設計出高效率的程序。一個高效的程序不僅需要編程技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法。這正是計算機科學領域里數(shù)據(jù)結構與算法設計所研究的主要內容。一些著名的計算機科學家在有關計算機科學教育的論述中提出，計算機科學是一種創(chuàng)造性思維活動，其教育必須面向設計。計算機算法設計與分析正是一門面向設計，且處于計算機科學與技術學科核心地位的教育課程。通過對計算機算法系統(tǒng)的學習與研究，理解和掌握算法設計的主要方法，培養(yǎng)對算法的計算復雜性進行正確分析的能力，為獨立地設計算法和對給定算法進行復雜性分析奠定堅實的理論基礎，對從事計算機系統(tǒng)結構、系統(tǒng)軟件和應用軟件研究與開發(fā)的科技工作者是非常重要和必不可少的。為了適應我國21世紀計算機人才培養(yǎng)的需要，結合我國高等學校教育工作的現(xiàn)狀，立足培養(yǎng)學生能跟上國際計算機科學技術的發(fā)展水平，更新教學內容和教學方法，本書以算法設計策略為知識單元，系統(tǒng)地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供一個廣泛而堅實的計算機算法基礎知識。
全書共分11章。在第１章中首先介紹算法的基本概念，接著簡要闡述算法的計算復雜性和算法的描述，然后圍繞設計算法常用的基本設計策略組織第２章至第10章的內容。第2章介紹遞歸與分治策略，這是設計有效算法最常用的策略，是必須掌握的方法。第3章是動態(tài)規(guī)劃算法，以具體實例詳述動態(tài)規(guī)劃算法的設計思想、適用性以及算法的設計要點。第4章介紹貪心算法，這也是一種重要的算法設計策略，它與動態(tài)規(guī)劃算法的設計思想有一定的聯(lián)系，但其效率更高。按貪心算法設計出的許多算法能導致最優(yōu)解，其中有許多典型問題和典型算法可供學習和使用。第５章和第６章分別介紹回溯法和分支限界法，這兩章所介紹的算法適合處理難解問題，其解題的思想各具特色，值得學習和掌握。第７章介紹概率算法，對許多難解問題提供高效的解決途徑，是有很高實用價值的算法設計策略。第８章介紹NP完全性理論和解NP難問題的近似算法。首先介紹計算模型、確定性和非確定性圖靈機，然后進一步深入介紹NP完全性理論，最后介紹解NP難問題的近似算法，這是當前計算機算法領域的熱門研究課題，具有很高的實用價值。第9章介紹有關串和序列的高效算法。第10章通過實例介紹算法設計中常用的算法優(yōu)化策略。最后，在第11章介紹算法設計中較新的研究領域在線算法設計。
在本書各章的論述中，首先介紹一種算法設計策略的基本思想，然后從解決計算機科學與應用中出現(xiàn)的實際問題入手，由簡到繁地描述幾個經(jīng)典的精巧算法，同時對每個算法所需要的時間和空間進行分析。這樣使讀者既能學到一些常用的精巧算法，又能通過對算法設計策略的反復應用，牢固掌握這些算法設計的基本策略，以期收到融會貫通之效。在為各種算法設計策略選擇用于展示其設計思想與技巧的具體應用問題時，本書有意重復選擇某些經(jīng)典問題，使讀者能深刻地體會到一個問題可以用多種設計策略求解。同時，通過對解同一問題的不同算法的比較，更容易體會到每一個具體算法的設計要點。隨著本書內容的逐步展開，讀者也將進一步感受到綜合應用多種設計策略可以更有效地解決問題。
本書采用面向對象的Java語言作為表述手段，在保持Java優(yōu)點的同時，盡量使算法的描述簡明、清晰。
為了便于讀者加深對知識的理解，各章配有難易適當?shù)牧曨}，以適應不同程度讀者練習的需要。
在本書的編寫過程中，得到教育部高等學校計算機類專業(yè)教學指導委員會的關心和支持。福州大學211工程計算機與信息工程重點學科實驗室和福建工程學院為本書的寫作提供了優(yōu)良的設備與工作環(huán)境。清華大學出版社負責本書編輯出版工作的全體人員為本書的出版付出了大量辛勤勞動，他們認真細致、一絲不茍的工作精神保證了本書的出版質量。南京大學宋方敏教授和福州大學傅清祥教授在百忙中認真審閱了全書，提出了許多寶貴的改進意見。在此，謹向每一位曾經(jīng)關心和支持本書編寫工作的各方面人士表示衷心的謝意！
由于作者的知識和寫作水平有限，書稿雖幾經(jīng)修改，仍難免存在缺點。熱忱歡迎同行專家和讀者惠予批評指正，使本書在使用過程中不斷改進，日臻完善。作者2018年6月前言算法設計與分析(第4版)
王曉東,教授，博士生導師。近年來正式出版學術著作11部。近年在國內外學術刊物上發(fā)表學術論文60多篇。參加多項科研項目并獲獎。其中獲國家科技進步二等獎一項，水電部科技進步一等獎一項，福建省科技進步三等獎一項，省水電廳科技進步一等獎一項。
目錄CONTENTS
第1章算法引論1
1.1算法與程序1
1.2表達算法的抽象機制1
1.3描述算法3
1.4算法復雜性分析10
小結13
習題14
第2章遞歸與分治策略16
2.1遞歸的概念16
2.2分治法的基本思想21
2.3二分搜索技術23
2.4大整數(shù)的乘法23
2.5Strassen矩陣乘法24
2.6棋盤覆蓋26
2.7合并排序28
2.8快速排序30
2.9線性時間選擇33
2.10最接近點對問題35
2.11循環(huán)賽日程表43
小結44
習題44
第3章動態(tài)規(guī)劃50
3.1矩陣連乘問題50
3.2動態(tài)規(guī)劃算法的基本要素55
3.3最長公共子序列58
3.4凸多邊形最優(yōu)三角剖分61
3.5多邊形游戲64
3.6圖像壓縮67
3.7電路布線69
3.8流水作業(yè)調度72
3.90\|1背包問題75
3.10最優(yōu)二叉搜索樹80
小結83
習題83
目錄算法設計與分析(第4版)第4章貪心算法85
4.1活動安排問題85
4.2貪心算法的基本要素88
4.2.1貪心選擇性質88
4.2.2最優(yōu)子結構性質89
4.2.3貪心算法與動態(tài)規(guī)劃算法的差異89
4.3最優(yōu)裝載91
4.4哈夫曼編碼92
4.4.1前綴碼93
4.4.2構造哈夫曼編碼93
4.4.3哈夫曼算法的正確性95
4.5單源最短路徑96
4.5.1算法基本思想97
4.5.2算法的正確性和計算復雜性98
4.6最小生成樹99
4.6.1最小生成樹性質99
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多機調度問題104
4.8貪心算法的理論基礎106
4.8.1擬陣106
4.8.2帶權擬陣的貪心算法107
4.8.3任務時間表問題109
小結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批處理作業(yè)調度126
5.4符號三角形問題128
5.5n后問題130
5.601背包問題133
5.7最大團問題136
5.8圖的m著色問題138
5.9旅行售貨員問題140
5.10圓排列問題142
5.11電路板排列問題144
5.12連續(xù)郵資問題147
5.13回溯法的效率分析149
小結152
習題152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2單源最短路徑問題156
6.3裝載問題158
6.4布線問題166
6.501背包問題170
6.6最大團問題175
6.7旅行售貨員問題178
6.8電路板排列問題181
6.9批處理作業(yè)調度184
小結189
習題189
第7章概率算法190
7.1隨機數(shù)191
7.2數(shù)值概率算法193
7.2.1用隨機投點法計算值193
7.2.2計算定積分194
7.2.3解非線性方程組195
7.3舍伍德算法197
7.3.1線性時間選擇算法198
7.3.2跳躍表200
7.4拉斯維加斯算法205
7.4.1n后問題206
7.4.2整數(shù)因子分解209
7.5蒙特卡羅算法211
7.5.1蒙特卡羅算法的基本思想211
7.5.2主元素問題213
7.5.3素數(shù)測試214
小結217
習題217
第8章NP完全性理論與近似算法221
8.1P類與NP類問題221
8.1.1非確定性圖靈機222
8.1.2P類與NP類語言222
8.1.3多項式時間驗證224
8.2NP完全問題225
8.2.1多項式時間變換225
8.2.2Cook定理226
8.3一些典型的NP完全問題229
8.3.1合取范式的可滿足性問題230
8.3.23元合取范式的可滿足性問題230
8.3.3團問題231
8.3.4頂點覆蓋問題232
8.3.5子集和問題233
8.3.6哈密頓回路問題235
8.3.7旅行售貨員問題238
8.4近似算法的性能238
8.5頂點覆蓋問題的近似算法240
8.6旅行售貨員問題近似算法241
8.6.1具有三角不等式性質的旅行售貨員問題242
8.6.2一般的旅行售貨員問題243
8.7集合覆蓋問題的近似算法244
8.8子集和問題的近似算法246
8.8.1子集和問題的指數(shù)時間算法247
8.8.2子集和問題的完全多項式時間近似格式247
小結250
習題250
第9章串與序列的算法253
9.1子串搜索算法253
9.1.1串的基本概念253
9.1.2KMP算法255
9.1.3RabinKarp算法258
9.1.4多子串搜索與AC自動機260
9.2后綴數(shù)組與最長公共子串266
9.2.1后綴數(shù)組的基本概念266
9.2.2構造后綴數(shù)組的倍前綴算法267
9.2.3構造后綴數(shù)組的DC3分治法270
9.2.4最長公共前綴數(shù)組與最長公共擴展算法274
9.2.5最長公共子串算法276
9.3序列比較算法277
9.3.1編輯距離算法277
9.3.2最長公共單調子序列280
9.3.3有約束最長公共子序列281
小結284
習題285
第10章算法優(yōu)化策略288
10.1算法設計策略的比較與選擇288
10.1.1最大子段和問題的簡單算法288
10.1.2最大子段和問題的分治算法289
10.1.3最大子段和問題的動態(tài)規(guī)劃算法291
10.1.4最大子段和問題與動態(tài)規(guī)劃算法的推廣291
10.2動態(tài)規(guī)劃加速原理294
10.2.1貨物儲運問題294
10.2.2算法及其優(yōu)化295
10.3問題的算法特征298
10.3.1貪心策略298
10.3.2對貪心策略的改進299
10.3.3算法三部曲299
10.3.4算法實現(xiàn)300
10.3.5算法復雜性305
10.4優(yōu)化數(shù)據(jù)結構306
10.4.1帶權區(qū)間最短路問題306
10.4.2算法設計思想306
10.4.3算法實現(xiàn)方案308
10.4.4并查集311
10.4.5可并優(yōu)先隊列314
10.5優(yōu)化搜索策略318
小結324
習題324
第11章在線算法設計325
11.1在線算法設計的基本概念325
11.2頁調度問題327
11.3勢函數(shù)分析329
11.4k服務問題330
11.4.1競爭比的下界330
11.4.2平衡算法331
11.4.3對稱移動算法332
11.5Steiner樹問題334
11.6在線任務調度336
11.7負載平衡337
小結338
習題338
詞匯索引340
參考文獻345
新書資訊