《算法分析與設(shè)計》是中國大學MOOC、智慧樹和學銀在線一流課程配套教材，也是工科聯(lián)盟和一流專業(yè)課程配套教材。全書共15章，以問題求解為主線，全面介紹問題求解的方法策略與優(yōu)化技巧。主要內(nèi)容包括算法與問題、算法分析、枚舉算法、貪心算法、遞推算法、分治算法、動態(tài)規(guī)劃算法、回溯算法、分支限界、網(wǎng)絡(luò)流算法、隨機算法、計算復雜性、近似算法、圖算法和字符串匹配算法。本書適合作為高等院校計算機相關(guān)專業(yè)高年級本科生和研究生的教材，也可作為ACMICPC競賽培訓和成人教育自學教材，亦可供程序設(shè)計開發(fā)人員、廣大科技工作者和研究人員參考。
1.配套雙一流課程2.適配課程思政和二十大精神3.以實踐和能力為導向，線上開放與線下實踐相結(jié)合，自動評測和互動交流相結(jié)合，專題案例與思考討論相結(jié)合。4.適應(yīng)探究性和碎片化學習，適應(yīng)自主性和多樣化學習，適應(yīng)多元化和個性化需求，培養(yǎng)學生主動學習、研究和創(chuàng)新意識。5.適配應(yīng)用型高校教學，教授十種實用算法，配套POJ競賽題，提高實踐應(yīng)用能力。6.俯瞰問題解決，建構(gòu)知識體系，全面介紹問題解決的基礎(chǔ)、思想、方法，培養(yǎng)計算思維。
修改版前言
《算法分析與設(shè)計》（第1版）已經(jīng)出版3年。在這3年時間里，人工智能、機器學習、大數(shù)據(jù)等新一代信息技術(shù)和產(chǎn)業(yè)蓬勃發(fā)展，科技創(chuàng)新成為時代潮流。為適應(yīng)信息產(chǎn)業(yè)的創(chuàng)新發(fā)展需求，服務(wù)于三全育人、科教融合的四新人才培養(yǎng)，編者對本書第1版進行了部分修訂。
本次修訂保持了第1版的基本結(jié)構(gòu)、主要內(nèi)容和寫作特色。以產(chǎn)業(yè)需求為導向，俯瞰問題求解，建構(gòu)前沿交叉的知識體系。以實踐和能力為導向，賽教融合，AI賦能，三全引領(lǐng)，多元探究，培養(yǎng)四新人才，培養(yǎng)學生探索交叉應(yīng)用問題求解算法的思維和能力。修訂版增加了第15章字符串匹配算法，介紹單模式串匹配算法和多模式串匹配算法。全書修訂添加了深度多元的思考題，引領(lǐng)智慧創(chuàng)新的學習需求。拓增了算法發(fā)展歷史的趣味知識、趣味生平和趣味人生，培養(yǎng)學生信息社會的IT素養(yǎng)、數(shù)字世界的工匠精神、智能時代的國際視野。此外，修訂了部分習題，對原書的疏漏之處進行了訂正，增加了第1、11章的混合教學示例視頻。
本次修訂由李恒武老師負責，感謝于瑞寒和李杰同學的審核和建議，并對廣大讀者提出的建議和意見表示誠摯的謝意。同時歡迎各位和讀者繼續(xù)對本書批評指正，提出寶貴意見。
李恒武
2025年3月
第1版前言
智能時代的今天，互聯(lián)網(wǎng)是道開胃菜，人工智能是主菜。但不管是AlphaGo打遍天下無敵手，還是紅客與黑客網(wǎng)絡(luò)大戰(zhàn)，程序設(shè)計都是必要的元技能�！叭绻憧刂屏舜a，那就控制了世界�！边@是未來學家Marc Goodman的預(yù)言，現(xiàn)在正在慢慢成為現(xiàn)實。
“Pascal之父”Nicklaus Wirth提出的公式“算法+數(shù)據(jù)結(jié)構(gòu)=程序”展示了程序的本質(zhì)。算法不但是程序，也是計算機科學的核心和靈魂。David Berlinski更是認為算法成就了現(xiàn)代世界：
“科學殿堂里陳列著兩顆熠熠生輝的寶石： 一顆是微積分； 另一顆就是算法。微積分成就了現(xiàn)代科學，而算法成就了現(xiàn)代世界�！�
面對各個應(yīng)用領(lǐng)域的大量復雜問題，最重要的是建立數(shù)學模型并設(shè)計高效的求解算法。在當今復雜、海量信息的大數(shù)據(jù)處理中，好算法往往是一錘定音的利器。
本書從解決問題和應(yīng)用實例入手，按照提出問題、分析問題、解決問題、總結(jié)問題的步驟，培養(yǎng)學生分析問題和解決問題的能力。以實踐和能力為導向，線上開放與線下實踐相結(jié)合，自動評測和互動交流相結(jié)合，專題案例與思考討論相結(jié)合，聚集和重組課程內(nèi)容，適應(yīng)探究性和碎片化學習，適應(yīng)自主性和多樣化學習，適應(yīng)多元化和個性化需求，培養(yǎng)學生主動學習、研究和創(chuàng)新意識。
本書共14章，主要內(nèi)容包括算法與問題、算法分析、枚舉算法、貪心算法、遞推算法、分治算法、動態(tài)規(guī)劃算法、回溯算法、分支限界、網(wǎng)絡(luò)流算法、隨機算法、計算復雜性、近似算法和圖算法。
本書適合作為高等院校計算機相關(guān)專業(yè)高年級本科生和研究生的教材，也可作為ACMICPC競賽培訓和成人教育自學教材，還可作為電子工程技術(shù)人員的參考用書。
本書由李恒武老師編寫。特別感謝耿蕾蕾老師和張琦乾同學的審核和建議，張琦乾同學給出全書算法示例和POJ編程習題的標準模板。在本書的編寫過程中，得到了許多老師和學生的支持與幫助，在此表示誠摯的感謝！
本書是中國大學MOOC、智慧樹和學銀在線一流課程配套教材，也是工科聯(lián)盟和一流專業(yè)課程配套教材，提供完整的視頻、電子教案、知識梳理、章節(jié)測驗、實踐作業(yè)、思考討論、在線題庫和文檔資源，便于教學和學生實踐。
最后，衷心祝愿讀者能夠從此書中獲益，從而實現(xiàn)自己的編程夢想。由于本書的內(nèi)容較多、牽涉的技術(shù)較廣，書中疏漏之處在所難免，歡迎讀者在使用過程中提出寶貴意見。
李恒武
2021年4月
李恒武,博士，教授，山東省機器學習與財經(jīng)數(shù)據(jù)挖掘重點實驗室主任，山東省教學信息化與教學方法創(chuàng)新指導委員會委員。著有《web技術(shù)》《web技術(shù)設(shè)計與開發(fā)》《云計算機與大數(shù)據(jù)的應(yīng)用》等，發(fā)表高水平論文40余篇，主講《算法分析與設(shè)計》被評為線上一流課程和在線開放精品課程
目錄
第1章算法與問題
1.1穩(wěn)定匹配問題
1.1.1問題分析
1.1.2穩(wěn)定匹配算法
1.1.3正確性證明
1.1.4算法實現(xiàn)
1.1.5算法總結(jié)
1.2算法概述
1.2.1算法的概念
1.2.2算法的性質(zhì)
1.2.3算法與程序
1.2.4算法與問題
1.2.5問題求解
1.3問題變換
1.3.1大學入學申請
1.3.2問題變換
習題一
第2章算法分析
2.1算法分析概述
2.1.1算法選擇
2.1.2分析方法
2.1.3有效算法
2.1.4事后統(tǒng)計
2.1.5算法分析總結(jié)
2.2漸近復雜度
2.2.1上界
2.2.2下界
2.2.3緊界
2.2.4高階和低階
2.2.5性質(zhì)
2.3復雜度比較
2.3.1階的高低
2.3.2比較方法
2.4實例分析
2.4.1非遞歸算法分析
2.4.2分析實例
2.5時空均衡
2.5.1空間復雜度
2.5.2預(yù)處理
2.5.3預(yù)構(gòu)造
2.5.4圖的遍歷
習題二
第3章枚舉算法
3.1枚舉與優(yōu)化
3.1.1蠻力算法
3.1.2枚舉算法概述
3.1.3枚舉優(yōu)化
3.2組合與排列
3.2.1排列
3.2.2子集
習題三
第4章貪心算法
4.1概述
4.1.1部分背包問題
4.1.2貪心算法概述
4.2基本要素
4.2.1性質(zhì)
4.2.2解證明
4.2.3預(yù)處理技巧
4.3區(qū)間問題
4.3.1區(qū)間調(diào)度問題
4.3.2區(qū)間劃分問題
4.3.3區(qū)間選點問題
4.3.4區(qū)間覆蓋問題
4.4MST問題
4.4.1MST特性
4.4.2Prim算法
4.4.3Kruskal算法
4.4.4逆刪除算法
4.4.5MST優(yōu)質(zhì)性
4.5哈夫曼編碼
4.5.1哈夫曼算法
4.5.2木板問題
習題四
第5章遞推算法
5.1遞推算法概述
5.1.1遞推
5.1.2遞推與遞歸
5.1.3遞推與循環(huán)
5.1.4遞歸與非遞歸
5.1.5切分問題
5.1.6獄吏問題
5.2倒推算法
5.2.1倒推與應(yīng)用
5.2.2約瑟夫問題
5.3遞推求解
5.3.1快速排序
5.3.2遞推方程求解
習題五
第6章分治算法
6.1分治算法概述
6.1.1設(shè)計思想
6.1.2合并排序
6.1.3基本特點
6.2分治類型
6.2.1不相似分治
6.2.2不獨立分治
6.2.3三分法
6.2.4減治法
6.2.5排序算法
6.3減少子問題個數(shù)
6.3.1二分搜索
6.3.2大整數(shù)乘法
6.3.3Strassen矩陣乘法
6.4改進分治均衡度
6.4.1隨機快速排序
6.4.2線性時間選擇
6.5減少分解合并時間
6.5.1最接近點對問題
6.5.2計數(shù)逆序問題
習題六
第7章動態(tài)規(guī)劃算法
7.1動態(tài)規(guī)劃
7.1.1兔子序列
7.1.2賦權(quán)區(qū)間調(diào)度問題
7.1.3基本性質(zhì)
7.1.4求解步驟
7.2決策與遞推關(guān)系
7.2.1數(shù)字三角形
7.2.2多階段決策與遞推關(guān)系
7.3背包問題
7.3.101背包問題
7.3.2恰好裝滿背包
7.3.3完全背包
7.3.4多重背包
7.3.5混合背包
7.4區(qū)間動態(tài)規(guī)劃
7.4.1矩陣相乘
7.4.2矩陣連乘
7.5DAG動態(tài)規(guī)劃
7.5.1拓撲排序
7.5.2嵌套矩形
7.5.3最長不降子序列
7.5.4硬幣問題
7.6樹圖動態(tài)規(guī)劃
7.6.1最短路徑問題
7.6.2FloydWarshall算法
7.6.3樹狀動態(tài)規(guī)劃
7.7序列相似度
7.7.1LCS問題
7.7.2序列比對
7.7.3動態(tài)規(guī)劃復雜度
習題七
第8章回溯算法
8.1裝載問題
8.1.1裝載問題分析
8.1.2裝載問題的回溯算法
8.2旅行商問題
8.2.1旅行商問題分析
8.2.2旅行商問題的回溯算法
8.3基本特征
8.3.1解題步驟
8.3.2回溯方式
8.3.3解空間結(jié)構(gòu)
8.3.4算法效率
8.401背包問題
8.4.101背包問題的回溯算法
8.4.2改進上界函數(shù)
8.5n皇后問題
8.5.1n皇后問題分析
8.5.2n皇后問題的回溯算法
8.6效率改進與估計
8.6.1效率估計
8.6.2效率改進
8.6.3適用條件
習題八
第9章分支限界
9.101背包問題
9.1.101背包問題的隊列式分支限界
9.1.201背包問題的優(yōu)先隊列式分支限界
9.1.301背包問題的優(yōu)先級改進
9.2旅行商問題
9.2.1旅行商問題的優(yōu)先隊列式分支限界
9.2.2旅行商問題的優(yōu)先級改進
9.3分支限界算法
9.3.1分支限界方式
9.3.2分支限界與回溯算法
9.3.3剪枝函數(shù)
9.3.4雙向廣度搜索
9.4算法總結(jié)
習題九
第10章網(wǎng)絡(luò)流算法
10.1最大流和最小割
10.1.1最大流
10.1.2最小割
10.1.3最大流算法
10.2最大流算法改進
10.2.1容量縮放算法
10.2.2最短增廣路算法
10.3預(yù)流推進算法
10.4最大流算法推廣
10.4.1多源點多匯點問題
10.4.2無向圖的最大流問題
10.4.3頂點容量限制問題
10.4.4帶需求的流通問題
10.4.5帶需求和下界的流通
10.4.6調(diào)查設(shè)計
10.5最小費用流
10.5.1最小費用路算法
10.5.2最小逃逸問題
10.6二分測試與二分匹配
10.6.1二分測試
10.6.2二分匹配
10.6.3網(wǎng)絡(luò)流算法
10.6.4匈牙利算法
10.7應(yīng)用實例
10.7.1二分匹配公式
10.7.2二分匹配應(yīng)用
10.8二分圖匹配
習題十
第11章隨機算法
11.1隨機算法概述
11.1.1確定性算法和隨機算法
11.1.2隨機算法分類
11.1.3偽隨機數(shù)
11.1.4模運算
11.2數(shù)值隨機算法
11.2.1計算π值
11.2.2計算定積分
11.3舍伍德算法
11.3.1隨機快速排序算法
11.3.2隨機選擇算法
11.3.3隨機洗牌算法
11.3.4搜索有序表
11.4拉斯維加斯算法
11.5蒙特卡洛算法
11.5.1主元素問題
11.5.2素數(shù)檢測
習題十一
第12章計算復雜性
12.1P與NP
12.1.1易解與難解問題
12.1.2判定與優(yōu)化問題
12.1.3計算模型
12.1.4P類
12.1.5NP類
12.1.6COOK歸約與KARP歸約
12.1.7多項式時間變換
12.2NP完全問題
12.2.1NP完全
12.2.2COOK定理
12.3NP完全問題證明
12.3.1局部替換技術(shù)
12.3.2分支設(shè)計技術(shù)
12.3.3限制技術(shù)
12.4NP完全問題求解
12.4.1求解策略
12.4.2子問題求解
12.4.3參數(shù)化算法
12.4.4圖著色問題
12.5coNP和PSPACE
12.5.1coNP
12.5.2PSPACE
習題十二
第13章近似算法
13.1非常近似算法
13.2相對近似算法
13.2.1相對近似算法概述
13.2.2貪心
13.2.3組合技術(shù)
13.2.4定價法
13.2.5線性規(guī)劃和舍入
13.3多項式時間近似方案
13.3.101背包問題的近似算法
13.3.201背包問題的多項式時間近似方案
13.3.301背包問題的完全多項式時間近似方案
習題十三
第14章圖算法
14.1基本概念
14.1.1無向圖與有向圖
14.1.2握手定理
14.1.3圖的表示
14.1.4路徑
14.1.5賦權(quán)圖
14.2可圖性
14.2.1可圖性概述
14.2.2圖的同構(gòu)
14.3圖的遍歷
14.3.1深度優(yōu)先搜索
14.3.2廣度優(yōu)先搜索
14.4無向連通圖
14.4.1無向連通圖概述
14.4.2生成樹
14.4.3圖的連通度
14.4.4割點與橋
14.4.5雙連通分量
14.4.6點連通度
14.4.7邊連通度
14.5有向連通圖
14.5.1有向連通圖概述
14.5.2強連通分量
14.5.3拓撲排序
14.5.4傳遞閉包
14.6可行遍性
14.6.1無向歐拉圖
14.6.2有向歐拉圖
14.6.3歐拉圖判定
14.6.4歐拉回路
14.6.5哈密頓圖
14.7平面圖
14.7.1平面圖概述
14.7.2圖著色問題
14.7.3圖著色算法
14.7.4圖的轉(zhuǎn)化
習題十四
第15章字符串匹配算法
15.1單模式串匹配算法
15.1.1字符串
15.1.2KMP算法
15.1.3RK算法
15.1.4BM算法
15.1.5Sunday算法
15.2多模式串匹配算法
15.2.1Trie樹
15.2.2后綴Trie的模式匹配算法
15.2.3AC自動機
習題十五
參考文獻
書單推薦
