一個(gè)人在接受科技教育時(shí)，最有價(jià)值的收獲是能使其終身受益的通用智能工具。
喬治福賽斯
（譯注：原文為T(mén)he most valuable acquisitions in a scientific or technical education are the general-purpose mental tools which remain serviceable for a life-time，出自1968年發(fā)表的What to do till the computer scientist comes。福賽斯(George Forsythe，19171972)1939年在布朗大學(xué)獲得博士學(xué)位，二戰(zhàn)后供職于斯坦福大學(xué)數(shù)學(xué)系，后來(lái)在該校創(chuàng)辦計(jì)算機(jī)系。他先后培養(yǎng)的博士生超過(guò)190名。他與MATLAB之父莫勒合著的《線性代數(shù)系統(tǒng)的計(jì)算機(jī)求解》出版于1967年。）

算法在計(jì)算科學(xué)和計(jì)算實(shí)踐中發(fā)揮著核心作用。基于這樣的認(rèn)知，涌現(xiàn)出大量相關(guān)的著述，尤其是教材。它們?cè)诮榻B算法時(shí)基本上選擇遵循兩種方案。一種是根據(jù)問(wèn)題類(lèi)型對(duì)算法進(jìn)行分類(lèi)。這樣的書(shū)用單獨(dú)的章節(jié)介紹排序、查找以及圖等算法。這種方案的優(yōu)點(diǎn)在于，能立即對(duì)比同一問(wèn)題場(chǎng)景下不同算法的效率。缺點(diǎn)在于，它強(qiáng)調(diào)的是問(wèn)題類(lèi)型，忽略了算法設(shè)計(jì)技術(shù)。
第二種方案是圍繞算法設(shè)計(jì)技術(shù)進(jìn)行組織。采用這種組織方式，如果來(lái)自不同計(jì)算領(lǐng)域的算法采用的是相同的設(shè)計(jì)方法，就把它們歸為一組。我和許多人一樣(例如[BaY95])，認(rèn)為這種組織方式更適合算法設(shè)計(jì)與分析基礎(chǔ)課程。強(qiáng)調(diào)算法設(shè)計(jì)技術(shù)主要有三個(gè)原因。第一，這些技術(shù)為學(xué)生提供了工具來(lái)為新的問(wèn)題設(shè)計(jì)算法。這使學(xué)習(xí)算法設(shè)計(jì)技術(shù)具有實(shí)踐意義上的價(jià)值。第二，它們根據(jù)基本的設(shè)計(jì)理念來(lái)對(duì)眾多已知的算法進(jìn)行分類(lèi)。尋找不同應(yīng)用領(lǐng)域的算法之間的共性，這應(yīng)該是計(jì)算機(jī)科學(xué)教育的一個(gè)主要目標(biāo)。畢竟，每一門(mén)學(xué)科都將其主要課題的分類(lèi)視為其學(xué)科的要點(diǎn)甚至是中心點(diǎn)。第三，在我看來(lái)，算法設(shè)計(jì)技術(shù)作為一般的問(wèn)題解決策略具有實(shí)用性，適用于計(jì)算以外的問(wèn)題。
遺憾的是，無(wú)論從理論還是教育的角度，算法設(shè)計(jì)技術(shù)的傳統(tǒng)分類(lèi)法都有幾個(gè)重大的缺陷。最重要的是沒(méi)有對(duì)許多重要的算法進(jìn)行分類(lèi)。這一不足迫使其他教科書(shū)的作者背離設(shè)計(jì)技術(shù)的組織形式，在書(shū)中加入相應(yīng)的章節(jié)來(lái)處理具體的問(wèn)題類(lèi)型。這樣的轉(zhuǎn)換導(dǎo)致算法課程喪失連貫性，注定會(huì)導(dǎo)致學(xué)生覺(jué)得亂。
算法設(shè)計(jì)技術(shù)的新分類(lèi)法
傳統(tǒng)算法設(shè)計(jì)技術(shù)分類(lèi)法的缺陷讓人感到失望，所以我開(kāi)發(fā)了一套新的分類(lèi)法[Lev99]，這也是本書(shū)的基礎(chǔ)。新的分類(lèi)法主要有下面幾個(gè)優(yōu)點(diǎn)。
新的分類(lèi)法比傳統(tǒng)分類(lèi)法更全面。新加入的蠻力法、減治法、變治法、時(shí)空權(quán)衡和迭代改進(jìn)等策略很少(甚至從未)被認(rèn)為是重要的設(shè)計(jì)范式(design paradigm)。
新的分類(lèi)法自然涵蓋傳統(tǒng)分類(lèi)法無(wú)法歸類(lèi)的許多經(jīng)典算法(歐幾里得算法、堆排序、查找樹(shù)、散列法、拓?fù)渑判�、高斯消去法和霍納規(guī)則等)，所以，新的分類(lèi)法使我們能以統(tǒng)一和連貫的方式呈現(xiàn)經(jīng)典算法的標(biāo)準(zhǔn)體系。
它自然適應(yīng)幾種設(shè)計(jì)技術(shù)的重要變化形式。例如，它能夠涵蓋減治法的三個(gè)變種和變治法的三個(gè)變種。
進(jìn)行效率分析時(shí)，新的分類(lèi)法與分析方法更適合(參見(jiàn)附錄B)。
設(shè)計(jì)技術(shù)作為問(wèn)題求解的一般性策略
本書(shū)主要是將算法設(shè)計(jì)技術(shù)應(yīng)用于計(jì)算機(jī)科學(xué)的經(jīng)典問(wèn)題。唯一的創(chuàng)新是加入了一些關(guān)于數(shù)值算法的內(nèi)容，這些內(nèi)容涵蓋在同一個(gè)通用框架內(nèi)。但是，這些設(shè)計(jì)技術(shù)可以用作通用問(wèn)題求解工具，其應(yīng)用并不限于傳統(tǒng)的計(jì)算和數(shù)學(xué)問(wèn)題。有兩個(gè)因素使這一點(diǎn)顯得特別重要。首先，越來(lái)越多的計(jì)算應(yīng)用超越了傳統(tǒng)領(lǐng)域，而且有理由相信這種趨勢(shì)在未來(lái)會(huì)進(jìn)一步加強(qiáng)。其次，培養(yǎng)學(xué)生解決問(wèn)題的能力被認(rèn)為是大學(xué)教育的一個(gè)主要目標(biāo)。在計(jì)算機(jī)科學(xué)課程體系中安排一門(mén)算法設(shè)計(jì)與分析課程是非常合適的，因?yàn)樗�可以教�?huì)學(xué)生如何應(yīng)用一些特定的策略來(lái)解決問(wèn)題。
我并不是說(shuō)要把算法設(shè)計(jì)與分析課程變成一門(mén)常規(guī)性的問(wèn)題求解課程。但我真心覺(jué)得不宜錯(cuò)過(guò)研究算法設(shè)計(jì)與分析所帶來(lái)的獨(dú)特機(jī)會(huì)�；�于此，我在本書(shū)中加入了謎題和謎題風(fēng)格類(lèi)游戲的應(yīng)用。雖然在算法教學(xué)中使用謎題不是什么新鮮事，但本書(shū)力求以系統(tǒng)化的方式通過(guò)幾個(gè)遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)的例子來(lái)做到這一點(diǎn)。
如何使用本書(shū)
我的目標(biāo)是寫(xiě)一本既不泛泛而談但又可供學(xué)生獨(dú)立閱讀的教材。為了實(shí)現(xiàn)這個(gè)目標(biāo)，本書(shū)做了如下努力。
根據(jù)喬治福賽斯的觀點(diǎn)(參見(jiàn)之前的引文)，我試圖著重強(qiáng)調(diào)隱藏于算法設(shè)計(jì)和分析背后的主要思想。在選擇特定的算法來(lái)闡述這些思想的時(shí)候，我并不傾向于涉及大量的算法，而是選擇那些最能揭示其基本設(shè)計(jì)技術(shù)或分析方法的算法。值得慶幸的是，大多數(shù)經(jīng)典算法都滿(mǎn)足這個(gè)要求。
第2章主要分析算法的效率，該章有意區(qū)分了用于分析非遞歸算法的方法和通常用于分析遞歸算法的方法。這一章還花了一些篇幅來(lái)介紹算法經(jīng)驗(yàn)分析和算法可視化。
書(shū)中以系統(tǒng)化的方式穿插了一些面向讀者的提問(wèn)，其中有些問(wèn)題是我們精心設(shè)計(jì)的，而且答案緊隨其后，其目的是引起讀者的注意或引發(fā)疑問(wèn)。其余問(wèn)題的用意是防止讀者走馬觀花而無(wú)法充分理解本書(shū)的內(nèi)容。
每章結(jié)尾處都會(huì)對(duì)當(dāng)前這一章中最重要的概念和結(jié)論做一個(gè)總結(jié)。
本書(shū)包含600多道習(xí)題。有些習(xí)題供大家練習(xí)用，另外一些則是想要指出書(shū)中正文部分所涉及內(nèi)容的重要意義，或是想要介紹書(shū)中沒(méi)有涉及的一些算法。有一些習(xí)題利用了網(wǎng)上的資源。較難的習(xí)題數(shù)量不多，在教參中用一種特殊的記號(hào)標(biāo)注出來(lái)(有的學(xué)生可能沒(méi)有勇氣做那些有難度標(biāo)注的習(xí)題，所以本書(shū)沒(méi)有為習(xí)題標(biāo)注難度)。謎題類(lèi)的習(xí)題用一種特殊的圖標(biāo)做標(biāo)注。
本書(shū)全部習(xí)題都附有提示。除了編程練習(xí)，習(xí)題的詳細(xì)解法都能在教師資源中找到。請(qǐng)發(fā)送郵件到coo@netease.com，申請(qǐng)教師相關(guān)資源(也可聯(lián)系培生的當(dāng)?shù)劁N(xiāo)售代表，或者訪問(wèn)www.pearsonhighered.com/irc)。
第3版的變化
第3版有若干變化，其中最重要的變化是介紹減治法和分治法的先后順序。第3版先介紹減治法，后介紹分治法，這樣做可以帶來(lái)以下優(yōu)勢(shì)。
相比分治法，減治法更簡(jiǎn)單。
相比分治法，減治法能解決的問(wèn)題更多。
新的編排順序便于先介紹插入排序，后介紹合并排序和快速排序。
數(shù)組劃分的概念通過(guò)選擇問(wèn)題引入，這次利用Lomuto算法的單向掃描來(lái)實(shí)現(xiàn)，而將Hoare劃分方法的雙向掃描留到后文與快速排序一并介紹。
折半查找歸入介紹減常量算法的章節(jié)。
另一個(gè)重要變化是重新編排了第8章關(guān)于動(dòng)態(tài)規(guī)劃的內(nèi)容，具體是指導(dǎo)述部分的內(nèi)容是全新的。在前兩版中用計(jì)算二項(xiàng)式系數(shù)的例子來(lái)引入動(dòng)態(tài)規(guī)劃這一重要技術(shù)，但第3版介紹了三個(gè)基礎(chǔ)性示例，效果更好一些；8.1節(jié)的習(xí)題是全新的，包括前兩版中沒(méi)有涉及的一些流行應(yīng)用；第8章其他小節(jié)的順序有調(diào)整，以便達(dá)到由淺入深、循序漸進(jìn)的效果。
此外，還有其他一些變化。增加了不少與本書(shū)所述算法相關(guān)的應(yīng)用。遍歷圖算法不再隨減治法介紹，而是納入蠻力算法和窮舉查找的范疇，因?yàn)槲艺J(rèn)為這樣更合理。在介紹生成組合對(duì)象的算法時(shí)，新增了格雷碼算法。對(duì)求解最近對(duì)問(wèn)題的分治法有更深入的探討。改進(jìn)的內(nèi)容包括算法可視化和求解旅行商問(wèn)題的近似算法，當(dāng)然參考文獻(xiàn)也有相應(yīng)的更新。
第3版大約新增70道習(xí)題，涉及算法謎題和常見(jiàn)的算法面試題。
先修課程
本書(shū)假定讀者已經(jīng)學(xué)過(guò)離散數(shù)學(xué)的標(biāo)準(zhǔn)課程和一門(mén)基礎(chǔ)性的編程課程。有了這樣的知識(shí)背景，讀者應(yīng)該能夠掌握本書(shū)的內(nèi)容而不會(huì)遇到太大的困難。盡管如此，1.4節(jié)、附錄A和附錄B仍然對(duì)基本的數(shù)據(jù)結(jié)構(gòu)以及肯定會(huì)用到的求和公式與遞推關(guān)系進(jìn)行復(fù)習(xí)和回顧。只有3個(gè)小節(jié)(2.2節(jié)、11.4節(jié)和12.4節(jié))會(huì)用到一些簡(jiǎn)單的微積分知識(shí)，如果讀者缺少必要的微積分知識(shí)，完全可以跳過(guò)這3個(gè)涉及微積分的小節(jié)，這樣做并不妨礙大家對(duì)本書(shū)其余部分的理解。
課程進(jìn)度安排
如果打算開(kāi)設(shè)一門(mén)基礎(chǔ)課來(lái)聚焦于算法設(shè)計(jì)技術(shù)，講解算法設(shè)計(jì)和分析理論，可以采用本書(shū)作為教材。但要想在一個(gè)學(xué)期內(nèi)完成該課程，本書(shū)的內(nèi)容可能就太豐富了。大體上來(lái)說(shuō)，跳過(guò)第3章到第12章的部分內(nèi)容不會(huì)影響讀者對(duì)后面部分的理解。本書(shū)的任何一個(gè)部分都可以安排學(xué)生自學(xué)。尤其是2.6節(jié)和2.7節(jié)，它們分別介紹經(jīng)驗(yàn)分析和算法可視化，這兩個(gè)小節(jié)可以結(jié)合課后練習(xí)一起布置給學(xué)生，讓他們課后完成。
以下教學(xué)計(jì)劃用于一個(gè)學(xué)期的課程，按照40課時(shí)的全日制教學(xué)計(jì)劃來(lái)設(shè)計(jì)。
課次 主題 小節(jié)
1 課程簡(jiǎn)介 1.1～1.3
2，3 分析框架；常用符號(hào)O、和 2.1，2.2
4 非遞歸算法的數(shù)學(xué)分析 2.3
5，6 遞歸算法的數(shù)學(xué)分析 2.4，2.5( 附錄B)
7　 蠻力算法 3.1，3.2( 3.3)
8 窮舉查找 3.4
9 深度優(yōu)先查找和廣度優(yōu)先查找 3.5
10～11 減一算法：插入排序、拓?fù)渑判?4.1，4.2
12 折半查找和其他減常量算法 4.4
13 減變量算法 4.5
14～15 分治法：合并排序、快速排序 5.1～5.2
16 其他分治法示例 5.3、5.4或5.5
17～19 實(shí)例化簡(jiǎn)：預(yù)排序、高斯消去法、平衡查找樹(shù) 6.1～6.3
20 改進(jìn)性能：堆和堆排序或者霍納法則和二進(jìn)制冪 6.4或6.5
21 問(wèn)題化簡(jiǎn) 6.6
22～24 時(shí)空權(quán)衡：串匹配、散列法、B樹(shù) 7.2～7.4
25～27 動(dòng)態(tài)規(guī)劃算法 8.1～8.4(選學(xué)3節(jié))
28～30 貪婪算法：Prim算法、Kruskal算法、Dijkstra算法、哈夫曼算法 9.1～9.4
31～33 迭代改進(jìn)算法 10.1～10.4(選學(xué)3節(jié))
34 下界的參數(shù) 11.1
35 決策樹(shù) 11.2
36 P、NP和NP完全問(wèn)題 11.3
37 數(shù)值算法 11.4( 12.4)
38 回溯法 12.1
39 分支定界法 12.2
40 NP困難問(wèn)題的近似算法 12.3
致謝
我要向本書(shū)的審閱人員表達(dá)衷心的感謝，還要感謝本書(shū)前面兩個(gè)版本的許多讀者，他們提供了許多寶貴的意見(jiàn)和建議來(lái)幫助改進(jìn)和完善本書(shū)。本書(shū)第3版尤其得益于下列審閱人員：芝加哥洛約拉大學(xué)的Andrew Harrington、圣文德大學(xué)的David Levine、加州大學(xué)河濱分校的Stefano Lombardi、賓州曼斯菲爾德大學(xué)的Daniel McKee、弗吉尼亞州立聯(lián)邦大學(xué)的Susan Brilliant、菩及海灣大學(xué)的David Akers以及兩名匿名評(píng)審。
我要感謝培生出版社為本書(shū)付出不懈努力的所有工作人員和相關(guān)人員。尤其要感謝本書(shū)編輯Matt Goldstein、編務(wù)助理Chelsea Bell、市場(chǎng)經(jīng)理Yez Alayan和產(chǎn)品總監(jiān)Kayla Smith-Tarbox。我還要感謝Richard Camp為本書(shū)審稿，感謝Windfall Software的Paul Anagnostopoulos和Jacqui Scarlott為本書(shū)排版并提供項(xiàng)目管理支持，感謝MaryEllen Oliver擔(dān)任本書(shū)校對(duì)。
最后，我要感謝我的兩位家人。相比自己寫(xiě)書(shū)，另一半天天忙著寫(xiě)書(shū)更讓人崩潰，我的妻子Maria包容我多年并任勞任怨地幫助我完成書(shū)中400多個(gè)公式或插圖以及教師手冊(cè)。女兒Miriam是我多年的英語(yǔ)老師，她不但閱讀了本書(shū)大部分內(nèi)容，還幫著我為每章找到了恰如其分的名人名言。

阿納尼樂(lè)維汀(Anany Levitin)