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