黨的二十大報(bào)告指出： 教育、科技、人才是全面建設(shè)社會(huì)主義現(xiàn)代化國家的基礎(chǔ)性、戰(zhàn)略性支撐。必須堅(jiān)持科技是第一生產(chǎn)力、人才是第一資源、創(chuàng)新是第一動(dòng)力，深入實(shí)施科教興國戰(zhàn)略、人才強(qiáng)國戰(zhàn)略、創(chuàng)新驅(qū)動(dòng)發(fā)展戰(zhàn)略，這三大戰(zhàn)略共同服務(wù)于創(chuàng)新型國家的建設(shè)。高等教育與經(jīng)濟(jì)社會(huì)發(fā)展緊密相連，對促進(jìn)就業(yè)創(chuàng)業(yè)、助力經(jīng)濟(jì)社會(huì)發(fā)展、增進(jìn)人民福祉具有重要意義。

算法在計(jì)算機(jī)科學(xué)中扮演著重要角色，算法設(shè)計(jì)與分析課程是計(jì)算機(jī)科學(xué)與技術(shù)等相關(guān)專業(yè)的核心必修課，其目標(biāo)是培養(yǎng)學(xué)生分析問題和解決問題的能力，使學(xué)生掌握算法設(shè)計(jì)的基本技巧和算法分析的基本技術(shù)，并能熟練運(yùn)用常用算法設(shè)計(jì)策略解決一些較綜合的問題，為學(xué)生進(jìn)一步學(xué)習(xí)后續(xù)課程奠定良好的基礎(chǔ)。本書是依據(jù)上述課程目標(biāo)并參考ACM/IEEE計(jì)算課程體系規(guī)范CC2020算法領(lǐng)域的4個(gè)績效能力(驗(yàn)證理論結(jié)果、對程序設(shè)計(jì)問題能給出解決方案、能開發(fā)出概念驗(yàn)證性程序和判斷是否能開發(fā)出更快的解決方案)所編寫的。

1．本書內(nèi)容

全書由12章構(gòu)成，各章的內(nèi)容如下：

第1章為緒論，介紹算法的概念、算法分析方法和STL在算法設(shè)計(jì)中的應(yīng)用。

第2章為遞歸算法設(shè)計(jì)技術(shù)，介紹遞歸的概念、遞歸模型、遞歸算法設(shè)計(jì)方法和遞歸的經(jīng)典應(yīng)用示例，包括直接插入排序、0/1背包問題和求表達(dá)式值，以及遞推式計(jì)算方法，包括直接展開法、遞歸樹方法、主方法和特征方程方法。

第3章為窮舉法，介紹窮舉法的特點(diǎn)、各種列舉方法和窮舉法的經(jīng)典應(yīng)用示例，包括求冪集、求全排列、0/1背包問題和旅行商問題等。

第4章為分治法，介紹分治法的特點(diǎn)、分治法的基本步驟和分治法的經(jīng)典應(yīng)用示例，包括快速排序、二路歸并排序、二分查找及其擴(kuò)展、求最大連續(xù)子序列和、棋盤覆蓋問題、循環(huán)日程安排問題和旅行商問題等。

第5章為回溯法，介紹解空間概念、回溯法解空間類型、子集樹回溯算法框架、排列樹回溯算法框架和回溯法的經(jīng)典應(yīng)用示例，包括構(gòu)造表達(dá)式、圖著色問題、子集和問題、0/1背包問題、完全背包問題、n皇后問題、任務(wù)分配問題和旅行商問題等。

第6章為分支限界法，介紹廣度優(yōu)先搜索的特性、分支限界法的特點(diǎn)、分支限界法的主要類型和分支限界法的經(jīng)典應(yīng)用示例，包括圖的單源最短路徑、0/1背包問題、任務(wù)分配問題和旅行商問題等，以及A*算法的原理及其應(yīng)用。

第7章為動(dòng)態(tài)規(guī)劃，介紹動(dòng)態(tài)規(guī)劃的特點(diǎn)、動(dòng)態(tài)規(guī)劃求解問題應(yīng)具有的性質(zhì)、動(dòng)態(tài)規(guī)劃的求解步驟、滾動(dòng)數(shù)組的應(yīng)用和動(dòng)態(tài)規(guī)劃的經(jīng)典應(yīng)用示例，包括求最大連續(xù)子序列和、最長遞增子序列、三角形最小路徑和、最長公共子序列、編輯距離、0/1背包問題、完全背包問題、扔雞蛋問題、資源分配問題、旅行商問題、最少士兵數(shù)問題和矩陣連乘問題等。

第8章為貪心法，介紹貪心法的特點(diǎn)、貪心法求解問題應(yīng)具有的性質(zhì)和貪心法的經(jīng)典應(yīng)用示例，包括區(qū)間問題、背包問題、田忌賽馬問題、零錢兌換問題和哈夫曼編碼，以及擬陣的概念、帶期限和懲罰的任務(wù)調(diào)度問題的求解過程。

第9章為圖算法，討論構(gòu)造圖最小生成樹的兩種算法(Prim和Kruskal)、求圖的最短路徑的4種算法(Dijkstra、Bellman�睩ord、SPFA和Floyd)和網(wǎng)絡(luò)流的相關(guān)概念，以及求最大流的相關(guān)算法。

第10章為計(jì)算幾何，介紹計(jì)算幾何中常用的向量運(yùn)算，以及求解凸包問題、最近點(diǎn)對問題和最遠(yuǎn)點(diǎn)對問題的典型算法。

第11章為計(jì)算復(fù)雜性，介紹易解問題和難解問題、圖靈機(jī)計(jì)算模型、P類和NP類問題以及NP完全問題。

第12章為概率算法和近似算法，介紹這兩類算法的特點(diǎn)和基本的算法設(shè)計(jì)方法。

書中帶*符號(hào)的部分作為選學(xué)內(nèi)容。

2．本書特色

本書具有如下鮮明的特色。

(1) 由淺入深，循序漸進(jìn)。每種算法設(shè)計(jì)策略從設(shè)計(jì)思想和算法框架入手，由易到難地講解相關(guān)經(jīng)典問題的求解過程，使讀者既能學(xué)到求解問題的方法，又能通過對算法設(shè)計(jì)策略的反復(fù)應(yīng)用掌握其核心原理，以收到融會(huì)貫通之效。

(2) 示例豐富，重視啟發(fā)。書中列舉大量經(jīng)典示例和有代表性的在線編程示例(選自LeetCode、LintCode、POJ和HDU)，深入剖析其求解思路，展示其算法設(shè)計(jì)的清晰過程，并舉一反三，激發(fā)讀者學(xué)習(xí)算法設(shè)計(jì)的興趣。

(3) 注重求解問題的多維性。同一個(gè)問題采用多種算法策略實(shí)現(xiàn)，例如0/1背包問題采用遞歸法、窮舉法、回溯法、分支限界法和動(dòng)態(tài)規(guī)劃求解，旅行商問題采用窮舉法、分治法、回溯法、分支限界法和動(dòng)態(tài)規(guī)劃求解。通過比較不同算法策略，使讀者體會(huì)每種算法策略的特點(diǎn)，以提高利用不同算法策略解決復(fù)雜問題的能力。

(4) 強(qiáng)調(diào)算法實(shí)現(xiàn)和對動(dòng)手能力的培養(yǎng)。算法設(shè)計(jì)僅會(huì)紙上談兵是不夠的，必須具備從問題建模、算法設(shè)計(jì)、算法實(shí)現(xiàn)到驗(yàn)證的能力，書中精選了大量難度適中的在線編程實(shí)驗(yàn)題，通過這些題目的訓(xùn)練，不僅可以提高讀者的編程能力，還可以幫助讀者直面各類競賽和求職市場。

(5) 本書配套有《算法設(shè)計(jì)與分析（第3版）學(xué)習(xí)指導(dǎo)》和《算法設(shè)計(jì)與分析（第3版）在線編程實(shí)驗(yàn)指導(dǎo)》(李春葆等，清華大學(xué)出版社，2024)，涵蓋所有練習(xí)題和在線編程題的參考答案。

3．教學(xué)資源

為了方便教師教學(xué)和學(xué)生學(xué)習(xí)，本書提供了全面且豐富的教學(xué)資源，包括以下內(nèi)容。

(1) 教學(xué)PPT： 提供全部教學(xué)內(nèi)容的精美PPT課件，供任課教師在教學(xué)中使用。

(2) 程序源代碼： 所有源代碼按章組織，例如ch2文件夾中存放第2章的源代碼(在Dev C 5．11中調(diào)試通過)。

(3) 教學(xué)大綱和電子教案： 包含32和48課堂講授學(xué)時(shí)的教學(xué)內(nèi)容安排及相應(yīng)的實(shí)驗(yàn)教學(xué)內(nèi)容安排，供教師參考。

（4） 與各章知識(shí)點(diǎn)對應(yīng)的題庫： 包括單項(xiàng)選擇題、填空題和算法設(shè)計(jì)的上機(jī)實(shí)驗(yàn)題。

(5) 絕大部分知識(shí)點(diǎn)的教學(xué)視頻： 視頻采用微課碎片化形式組織，含170個(gè)視頻，累計(jì)超過34小時(shí)。

資源下載提示

課件等資源： 掃描封底的課件下載二維碼，在公眾號(hào)書圈下載。

素材（源碼）等資源： 掃描目錄上方的二維碼下載。

在線自測題： 掃描封底的作業(yè)系統(tǒng)二維碼，再掃描自測題二維碼在線做題。

微課視頻： 掃描封底的文泉云盤防盜碼，再掃描書中相應(yīng)章節(jié)的視頻講解二維碼，可以在線學(xué)習(xí)。

4．致謝

本書的編寫得到101計(jì)劃和武漢大學(xué)計(jì)算機(jī)學(xué)院相關(guān)課程教學(xué)研究項(xiàng)目的大力支持，清華大學(xué)出版社的魏江江分社長和王冰飛老師提供了全方位的幫助和精心的編輯工作，LeetCode和相關(guān)在線編程平臺(tái)給予了無私的幫助，編者在此一并表示衷心的感謝。

盡管編者不遺余力，但由于水平所限，本書仍存在疏漏和不足之處，敬請教師和同學(xué)們批評指正。

編者

2024年1月