《數(shù)據(jù)結(jié)構(gòu)與算法之美》，王爭(zhēng) 著

標(biāo)簽：數(shù)據(jù)結(jié)構(gòu)、算法

第10章 貪心、分治、回溯和動(dòng)態(tài)規(guī)劃

一、貪心算法

這一部分介紹了

• 如何理解貪心算法

• 貪心算法的應(yīng)用示例（分糖果、最短服務(wù)時(shí)間、區(qū)間覆蓋）

• 如何利用貪心算法實(shí)現(xiàn)霍夫曼編碼

筆記：如何貪心，貪心模型是最關(guān)鍵的。嚴(yán)禁的證明貪心算法能得到最優(yōu)解并不是一件容易的事情

二、分治算法

這一部分介紹了

• 如何理解分治算法

• 分治算法的應(yīng)用示例（歸并排序）

• 分治算法在大數(shù)據(jù)處理中的應(yīng)用

• 大規(guī)模計(jì)算框架MapReduce中的分治思想

三、回溯算法

這一部分介紹了

• 如何理解回溯算法

• 八皇后問(wèn)題

• 0-1背包問(wèn)題

• 正則表達(dá)式匹配問(wèn)題

筆記：回溯算法思想非常簡(jiǎn)單，但應(yīng)用廣泛，除了深度優(yōu)先搜索算法，正則表達(dá)式匹配、編譯原理中的語(yǔ)法分析等，還有很多經(jīng)典數(shù)學(xué)問(wèn)題，如數(shù)獨(dú)、八皇后、0-1背包、圖的著色、旅行商、求全排列等。大部分情況下，回溯可用來(lái)解決廣義的搜索問(wèn)題，也就是從一組可能的解中選出一個(gè)滿足要求的解?；厮菟惴ǚ浅＿m合用遞歸來(lái)實(shí)現(xiàn)，在實(shí)現(xiàn)的過(guò)程中，剪枝操作是提高搜索效率的一種技巧。

?四、初始動(dòng)態(tài)規(guī)劃

這一部分介紹了

• 動(dòng)態(tài)規(guī)劃的學(xué)習(xí)路線

• 利用動(dòng)態(tài)規(guī)劃解決0-1背包問(wèn)題

• 0-1背包問(wèn)題的升級(jí)版

• 如何巧妙解決雙11購(gòu)物是的湊單問(wèn)題

五、動(dòng)態(tài)規(guī)劃理論

這一部分介紹了

• 一個(gè)模型和三個(gè)特征理論介紹

• 一個(gè)模型和三個(gè)特征的應(yīng)用示例

• 動(dòng)態(tài)規(guī)劃的兩種解題方法

?六、動(dòng)態(tài)規(guī)劃實(shí)戰(zhàn)：如何實(shí)現(xiàn)搜索引擎中的拼寫糾錯(cuò)功能

這一部分介紹了

• 如何量化兩個(gè)字符串的相似度

• 如何通過(guò)編程計(jì)算萊文斯坦距離

• 如何通過(guò)編程計(jì)算最長(zhǎng)公共子串長(zhǎng)度

?

本章筆記：貪心、分治、回溯和動(dòng)態(tài)規(guī)劃是經(jīng)典的算法思想，是指導(dǎo)算法設(shè)計(jì)的原理，原理解釋起來(lái)都很簡(jiǎn)單，但是要真正掌握并能靈活應(yīng)用，并不是一件容易的事情，讀者只有先學(xué)習(xí)算法設(shè)計(jì)思想，結(jié)合具體的問(wèn)題，通過(guò)應(yīng)用這些算法思想解決問(wèn)題，才能不斷提升算法設(shè)計(jì)能力水平。

?無(wú)數(shù)優(yōu)秀的算法、軟件、系統(tǒng)、框架等設(shè)計(jì)思想源自基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法，這本身就是數(shù)據(jù)結(jié)構(gòu)和算法的魅力，也是為什么在學(xué)習(xí)計(jì)算機(jī)的基礎(chǔ)階段要好好學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的原因。