前言

一、關(guān)于本書

本書是在結(jié)合作者多年教學(xué)經(jīng)驗(yàn)及實(shí)踐的基礎(chǔ)上編寫而成的。它充分考慮了學(xué)生的接受能力，本著“易理解，重實(shí)用”的指導(dǎo)思想，以掌握算法設(shè)計(jì)與分析的基本概念和方法、運(yùn)用算法理論編程解決實(shí)際問(wèn)題、拓展專業(yè)知識(shí)結(jié)構(gòu)為宗旨，按照“算法思想—算法設(shè)計(jì)—構(gòu)造實(shí)例—算法描述—算法分析—C++實(shí)戰(zhàn)”的思路組織內(nèi)容，詳細(xì)講述了多種經(jīng)典算法設(shè)計(jì)策略。縱觀全書，這里并沒(méi)有創(chuàng)造出任何新的算法，因?yàn)樽髡邇H僅希望通過(guò)對(duì)經(jīng)典算法的講解，把算法設(shè)計(jì)與分析中基礎(chǔ)且重要的內(nèi)容用更清晰的思路、更直觀的形式展現(xiàn)給讀者。

二、本書結(jié)構(gòu)

本書以算法策略為知識(shí)單元，共9章內(nèi)容，其中第1章介紹基礎(chǔ)知識(shí)，第2～8章介紹經(jīng)典的算法設(shè)計(jì)策略，第9章簡(jiǎn)單介紹NP完全理論。具體結(jié)構(gòu)安排如下：

第1章：算法基礎(chǔ)。主要介紹算法設(shè)計(jì)與分析的基礎(chǔ)知識(shí)、遞歸、常用的數(shù)據(jù)結(jié)構(gòu)及數(shù)學(xué)公式等。

第2～5章介紹經(jīng)典的算法設(shè)計(jì)策略：貪心算法、分治算法、動(dòng)態(tài)規(guī)劃、搜索算法等。每一種算法設(shè)計(jì)策略均按照“算法思想—算法設(shè)計(jì)—構(gòu)造實(shí)例—算法描述—算法分析—C++實(shí)戰(zhàn)”的思路詳細(xì)講解。

第6章：隨機(jī)化算法。講述了4種類型的隨機(jī)化算法，并結(jié)合實(shí)例講述了每種隨機(jī)化算法的特點(diǎn)。

第7章：線性規(guī)劃問(wèn)題與網(wǎng)絡(luò)流。著重講述線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)化及單純形算法、網(wǎng)絡(luò)流的基本概念及理論、求最大流的增廣路算法、求最小費(fèi)用流的消圈算法。

第8章：數(shù)論算法及計(jì)算幾何算法。數(shù)論算法中介紹了一些簡(jiǎn)單的數(shù)論理論知識(shí)及最大公約數(shù)、一次同余方程和同余方程組的算法；計(jì)算幾何算法中主要介紹叉積的概念和幾何意義，進(jìn)而利用它判斷點(diǎn)與線段、線段與線段之間的關(guān)系；解決凸包問(wèn)題及最接近點(diǎn)對(duì)問(wèn)題的兩種算法的實(shí)現(xiàn)與比較。

第9章：NP完全理論。簡(jiǎn)單介紹了NP完全理論和近似算法，以引起讀者進(jìn)一步學(xué)習(xí)和研究的興趣。

其中，第4～9章由南陽(yáng)理工學(xué)院王秋芬編寫，第1～3章由南陽(yáng)理工學(xué)院趙剛彬編寫，習(xí)題解析由王秋芬編寫。

三、本書特點(diǎn)

本書側(cè)重于算法步驟的設(shè)計(jì)及實(shí)例構(gòu)造，注重算法與數(shù)據(jù)結(jié)構(gòu)的結(jié)合、算法時(shí)間效率分析和實(shí)戰(zhàn)演練。其特色在于針對(duì)每一種算法設(shè)計(jì)策略，按照算法思想設(shè)計(jì)了詳細(xì)的算法步驟，構(gòu)造了具體實(shí)例以展現(xiàn)算法的詳細(xì)演示過(guò)程，最后給出算法描述及C++源代碼。

本書內(nèi)容精練，算法設(shè)計(jì)步驟清晰，實(shí)例構(gòu)造詳盡，算法描述的注釋清楚，源碼完整，閱讀材料豐富，易教、易學(xué)。通過(guò)本書，讀者一方面可以學(xué)習(xí)到基本的算法設(shè)計(jì)策略、分析和實(shí)現(xiàn)方法；另一方面還可以對(duì)當(dāng)今流行算法和算法界的大師有所了解。

在此，謹(jǐn)向清華大學(xué)出版社負(fù)責(zé)本書編輯出版工作的全體人員和每一位曾經(jīng)關(guān)心和支持本書編寫工作的各方面專家表示衷心感謝。

由于編者水平有限，書稿雖幾經(jīng)修改，仍難免有疏漏或不妥之處，歡迎廣大讀者和專家批評(píng)指正。

編　者

2022年9月