前言

本書是在我的在線算法課程基礎(chǔ)之上編寫的，是“算法詳解”系列圖書4卷中的第4卷。這個(gè)在線課程 2012 年起就定期發(fā)布，它建立在我在斯坦福大學(xué)講授多年的本科課程的基礎(chǔ)之上。在閱讀本書之前，讀者需要熟悉漸進(jìn)性分析和大O表示法、圖的搜索和最短路徑算法、貪心算法和動(dòng)態(tài)規(guī)劃（以上內(nèi)容在“算法詳解”系列圖書第1～3卷均有講述）。

本書涵蓋的內(nèi)容

“算法詳解”系列圖書第4卷介紹了NP-Hard問題（后簡稱NP問題）以及相關(guān)的概念。

處理NP問題的算法工具

許多現(xiàn)實(shí)世界的問題都是NP問題，無法由“算法詳解”系列圖書前3卷所描述的始終快速且正確的算法所解決。當(dāng)我們在工作中遇到NP問題時(shí)，必須在正確性或速度上做出妥協(xié)。我們將會(huì)看到實(shí)現(xiàn)“近似正確性”的快速啟發(fā)式算法的舊技巧（例如貪心算法）和新技巧（例如局部搜索），及其在作業(yè)調(diào)度、社交網(wǎng)絡(luò)的影響最大化和旅行商問題上的應(yīng)用等。我們還將討論開發(fā)明顯快于窮舉搜索的算法的舊技巧（例如動(dòng)態(tài)規(guī)劃）和新技巧（例如MIT和SAT解決程序）。這些技巧的應(yīng)用包括旅行商問題、在生態(tài)網(wǎng)絡(luò)中尋找信道通路以及美國的一家電視臺(tái)在最近的一次高風(fēng)險(xiǎn)頻譜拍賣中重新安置問題等。

識(shí)別NP問題

本書還將訓(xùn)練讀者快速識(shí)別NP問題，使讀者不至于浪費(fèi)時(shí)間試圖為這類問題設(shè)計(jì)一種過于美好但難以成真的算法。讀者將熟悉許多著名且基本的NP問題，范圍包括可滿足性問題、圖形著色問題和漢密爾頓路徑問題等。通過實(shí)踐，讀者將會(huì)掌握通過轉(zhuǎn)化證明NP問題的技能。

關(guān)于本書內(nèi)容的更詳細(xì)概述，可以閱讀每章的本章要點(diǎn)，它對每一章的內(nèi)容特別是那些重要的概念進(jìn)行了總結(jié)。本書的后記的標(biāo)題是算法設(shè)計(jì)實(shí)戰(zhàn)指南，從大局上概述了如何把本書所討論的話題應(yīng)用于具體的算法場景。

書中帶星號(hào)的章節(jié)是難度較高的章節(jié)。時(shí)間較為緊張的讀者在第一遍閱讀時(shí)可以跳過這些章節(jié)，這并不會(huì)影響本書閱讀的連續(xù)性。

“算法詳解”系列圖書前三卷所涵蓋的主題

“算法詳解”系列圖書的第1卷討論了漸進(jìn)性表示法（大O表示法以及相關(guān)表示法）、分治算法和主方法，隨機(jī)化的QuickSort及其分析以及線性時(shí)間的選擇算法。“算法詳解”系列圖書的第2卷重點(diǎn)討論了數(shù)據(jù)結(jié)構(gòu)（堆、平衡搜索樹、散列表、布隆過濾器）、圖形基本單元（寬度和深度優(yōu)先的搜索、連通性、最短路徑）以及它們的應(yīng)用（從去除重復(fù)到社交網(wǎng)絡(luò)分析）。“算法詳解”系列圖書的第3卷則重點(diǎn)討論了貪心算法（調(diào)度、最小生成樹、集群、哈夫曼編碼）和動(dòng)態(tài)規(guī)劃算法（背包、序列對齊、最短路徑、最佳搜索樹）。

讀者的收獲

精通算法需要大量的時(shí)間和精力，那為什么要學(xué)習(xí)算法呢？

成為更優(yōu)秀的程序員

讀者將學(xué)習(xí)一些令人炫目的用于處理數(shù)據(jù)的高速程序以及一些實(shí)用的數(shù)據(jù)結(jié)構(gòu)，它們用于組織數(shù)據(jù)，可以直接部署到自己的程序中。實(shí)現(xiàn)和使用這些算法將擴(kuò)展并提高讀者的編程技巧。讀者還將學(xué)習(xí)基本的算法設(shè)計(jì)范式，它們與許多不同領(lǐng)域的不同問題密切相關(guān)，并且可以作為預(yù)測算法性能的工具。這些“算法設(shè)計(jì)模式”可以幫助讀者為自己碰到的問題設(shè)計(jì)新算法。

加強(qiáng)分析技巧

讀者將獲得大量對算法進(jìn)行描述和推導(dǎo)的實(shí)踐機(jī)會(huì)。通過數(shù)學(xué)分析，讀者將對“算法詳解”系列圖書所涵蓋的特定算法和數(shù)據(jù)結(jié)構(gòu)有深刻的理解。讀者還將掌握一些廣泛用于算法分析的實(shí)用數(shù)學(xué)技巧。

形成算法思維

在學(xué)習(xí)了算法之后，很難發(fā)現(xiàn)有什么地方?jīng)]有它們的蹤影。無論是坐電梯、觀察鳥群，還是管理自己的投資組合，甚至是觀察嬰兒的認(rèn)知，算法思維如影隨形。算法思維在計(jì)算機(jī)科學(xué)之外的領(lǐng)域，包括生物學(xué)、統(tǒng)計(jì)學(xué)和經(jīng)濟(jì)學(xué)，越來越實(shí)用。

融入計(jì)算機(jī)科學(xué)家的圈子

研究算法就像是觀看計(jì)算機(jī)科學(xué)最近60年發(fā)展的精彩剪輯。當(dāng)讀者參加一場計(jì)算機(jī)科學(xué)界的雞尾酒會(huì)，會(huì)上有人講了一個(gè)關(guān)于Dijkstra算法的笑話時(shí)，你就不會(huì)感覺自己被排除在這個(gè)圈子之外了。在閱讀了本系列圖書之后，讀者將了解許多這方面的知識(shí)。

在技術(shù)訪談中脫穎而出

在過去這些年里，有很多學(xué)生向我講述了“算法詳解”系列圖書是怎樣幫助他們在技術(shù)訪談中大放異彩的。

其他算法教材

“算法詳解”系列圖書只有一個(gè)目標(biāo)：盡可能以讀者容易接受的方式介紹算法的基礎(chǔ)知識(shí)。讀者可以把本書看成專家級(jí)算法教師的課程記錄，老師以課程的形式傳道解惑。

市面上還有一些非常優(yōu)秀的更為傳統(tǒng)、全面的算法教材，它們都可以作為“算法詳解”系列關(guān)于算法的其他細(xì)節(jié)、問題和主題的有益補(bǔ)充。我鼓勵(lì)讀者探索和尋找自己喜歡的其他教材。另外，還有一些圖書的出發(fā)點(diǎn)有所不同，它們偏向于站在程序員的角度尋找一種特定編程語言的成熟算法實(shí)現(xiàn)。網(wǎng)絡(luò)中存在大量免費(fèi)的這類算法的實(shí)現(xiàn)。

本書的目標(biāo)讀者

“算法詳解”系列圖書以及作為其基礎(chǔ)的在線課程的整體目標(biāo)是盡可能地?cái)U(kuò)展讀者群體的范圍。學(xué)習(xí)我的在線課程的人具有不同的年齡、背景、生活方式，有大量來自全世界各個(gè)角落的學(xué)生（包括高中生、大學(xué)生等）、軟件工程師（包括現(xiàn)在的和未來的）、科學(xué)家和專業(yè)人員。

本書并不是討論編程的，理想情況下讀者至少應(yīng)該熟悉一種標(biāo)準(zhǔn)編程語言（例如Java、Python、C、Scala、Haskell等）并掌握了基本的編程技巧。如果讀者想要提高自己的編程技巧，那么可以學(xué)習(xí)一些非常優(yōu)秀的講述基礎(chǔ)編程的免費(fèi)在線課程。

我們還會(huì)根據(jù)需要通過數(shù)學(xué)分析幫助讀者理解算法為什么能夠?qū)崿F(xiàn)目標(biāo)以及它是怎樣實(shí)現(xiàn)目標(biāo)的。Eric Lehman和Tom Leighton關(guān)于計(jì)算機(jī)科學(xué)的數(shù)學(xué)知識(shí)的免費(fèi)課程是極為優(yōu)秀的，可以幫助讀者復(fù)習(xí)數(shù)學(xué)記法（例如Σ和?）、數(shù)學(xué)證明的基礎(chǔ)知識(shí)（歸納、悖論等）、離散概率等更多知識(shí)。

其他資源

“算法詳解”系列圖書的在線課程當(dāng)前運(yùn)行于Coursera和EdX平臺(tái)。另外，還有一些資源可以幫助讀者根據(jù)自己的意愿提升對在線課程的體驗(yàn)。

● 視頻。如果讀者覺得相比閱讀文字，更喜歡聽和看，那么可以在視頻網(wǎng)站的視頻播放列表中觀看。這些視頻涵蓋了“算法詳解”系列的所有主題。我希望它們能夠激發(fā)讀者學(xué)習(xí)算法的持續(xù)熱情。當(dāng)然，它們并不能完全取代書的作用。

● 小測驗(yàn)。讀者怎么才能知道自己是否完全理解了本書所討論的概念呢？散布于全書的小測驗(yàn)及其答案和詳細(xì)解釋就起到了這個(gè)作用。當(dāng)讀者閱讀這塊內(nèi)容時(shí)，最好能夠停下來認(rèn)真思考，然后繼續(xù)閱讀接下來的內(nèi)容。

● 章末習(xí)題。每章的末尾都有一些相對簡單的問題，用于測試讀者對該章內(nèi)容的理解程度。另外，還有一些開放性的、難度更大的挑戰(zhàn)題。

● 章末習(xí)題的答案（分別用（H）或（S）提示難度）在本書的最后。讀者可以與我聯(lián)系或者通過下面的論壇相互交流，對章末習(xí)題進(jìn)行探討。

● 編程題。有幾章的最后是一個(gè)推薦的編程項(xiàng)目，其目的是通過創(chuàng)建自己的算法工作程序，來培養(yǎng)讀者對算法的完全理解。讀者可以在algorithmsilluminated網(wǎng)站上找到數(shù)據(jù)集、測試用例以及它們的答案。

● 論壇。在線課程能夠取得成功的一個(gè)重要原因是它們?yōu)閰⑴c者提供了互相幫助的機(jī)會(huì)，讀者可以通過論壇討論課程材料和調(diào)試程序。本系列圖書的讀者也有同樣的機(jī)會(huì)，可以通過algorithmsilluminated網(wǎng)站參與活動(dòng)。