黨的二十大報(bào)告指出： 教育、科技、人才是全面建設(shè)社會(huì)主義現(xiàn)代化國(guó)家的基礎(chǔ)性、戰(zhàn)略性支撐。必須堅(jiān)持科技是第一生產(chǎn)力、人才是第一資源、創(chuàng)新是第一動(dòng)力，深入實(shí)施科教興國(guó)戰(zhàn)略、人才強(qiáng)國(guó)戰(zhàn)略、創(chuàng)新驅(qū)動(dòng)發(fā)展戰(zhàn)略，這三大戰(zhàn)略共同服務(wù)于創(chuàng)新型國(guó)家的建設(shè)。高等教育與經(jīng)濟(jì)社會(huì)發(fā)展緊密相連，對(duì)促進(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è)績(jī)效能力(驗(yàn)證理論結(jié)果、對(duì)程序設(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ù)子序列和、最長(zhǎng)遞增子序列、三角形最小路徑和、最長(zhǎng)公共子序列、編輯距離、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)對(duì)問題和最遠(yuǎn)點(diǎn)對(duì)問題的典型算法。

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

(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)對(duì)應(yīng)的題庫(kù)： 包括單項(xiàng)選擇題、填空題和算法設(shè)計(jì)的上機(jī)實(shí)驗(yàn)題。

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

資源下載提示

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

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

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

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

4．致謝

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

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

編者

2024年1月