貪婪算法

貪婪算法，也被稱為“貪心算法”。貪婪算法分階段地工作。在每一個階段，都可以認為所作決定是好的，而不考慮將來的后果。一般來說，這意味著選擇的是某個局部的最優(yōu)。這種“眼下能夠拿到的就拿”的策略即是這類算法的來源。當(dāng)算法終止時，我們希望局部最優(yōu)就是全局最優(yōu)。如果是這樣的話，那么算法就是正確的；否則，算法得到的就是一個次優(yōu)解。如果不要求絕對最佳答案，那么有時會用簡單的貪婪算法來生成近似的答案，而不是使用一般產(chǎn)生準(zhǔn)確答案所需要的復(fù)雜算法。

分治算法

分治算法由兩部分組成：

• 分(divide)：遞歸解決較小的問題（當(dāng)然，基本情況除外）。
• 治(conquer)：然后，從子問題的解構(gòu)建原問題的解。

傳統(tǒng)上，在正文中至少含有兩個遞歸調(diào)用的例程叫做分治算法，而正文中只含有一個遞歸調(diào)用的例程不是分治算法。我們一般堅持子問題是不相交的（即基本上不重疊）。

在分治算法中，所有有效的分治算法都是把問題分成一些子問題，每個子問題都是原問題的一部分，然后進行某些附加的工作以算出最后的答案。

回溯算法

在許多情況下，回溯算法相當(dāng)于窮舉搜索的巧妙實現(xiàn)，但性能一般不理性。不過，情況并不總是如此，即使如此，在某些情況下下它相比蠻力(brute force)窮舉搜索，工作量也有顯著的節(jié)省。當(dāng)然，性能是相對的；對于排序而言，O(N^2)的算法是相當(dāng)差的，但對旅行售貨員（或任何 NP-完全）問題，O(N^2)算法則是里程碑式結(jié)果。

動態(tài)規(guī)劃

任何數(shù)學(xué)遞歸共識都可以直接翻譯成遞歸算法，但是基本現(xiàn)實是編譯器常常不能正確對待遞歸算法，結(jié)果導(dǎo)致低效的算法。當(dāng)我們懷疑很可能是這種情況時，我們必須再給編譯器提供一些幫助，將遞歸算法重新寫成非遞歸算法，讓后者把那些子問題的答案系統(tǒng)地記錄在一個表內(nèi)。利用這種方法的一種技巧叫做動態(tài)規(guī)劃(dynamic programming)。

區(qū)別和聯(lián)系

如果我們將這四種算法思想分一下類，那貪心、回溯、動態(tài)規(guī)劃可以歸為一類，而分治單獨可以作為一類，因為它跟其他三個都不大一樣。為什么這么說呢？前三個算法解決問題的模型，都可以抽象成我們今天講的那個多階段決策最優(yōu)解模型，而分治算法解決的問題盡管大部分也是最優(yōu)解問題，但是，大部分都不能抽象成多階段決策模型。

回溯算法是個“萬金油”?；旧夏苡玫膭討B(tài)規(guī)劃、貪心解決的問題，我們都可以用回溯算法解決。回溯算法相當(dāng)于窮舉搜索。窮舉所有的情況，然后對比得到最優(yōu)解。不過，回溯算法的時間復(fù)雜度非常高，是指數(shù)級別的，只能用來解決小規(guī)模數(shù)據(jù)的問題。對于大規(guī)模數(shù)據(jù)的問題，用回溯算法解決的執(zhí)行效率就很低了。

盡管動態(tài)規(guī)劃比回溯算法高效，但是，并不是所有問題，都可以用動態(tài)規(guī)劃來解決。能用動態(tài)規(guī)劃解決的問題，需要滿足三個特征，最優(yōu)子結(jié)構(gòu)、無后效性和重復(fù)子問題。在重復(fù)子問題這一點上，動態(tài)規(guī)劃和分治算法的區(qū)分非常明顯。分治算法要求分割成的子問題，不能有重復(fù)子問題，而動態(tài)規(guī)劃正好相反，動態(tài)規(guī)劃之所以高效，就是因為回溯算法實現(xiàn)中存在大量的重復(fù)子問題。

貪心算法實際上是動態(tài)規(guī)劃算法的一種特殊情況。它解決問題起來更加高效，代碼實現(xiàn)也更加簡潔。不過，它可以解決的問題也更加有限。它能解決的問題需要滿足三個條件，最優(yōu)子結(jié)構(gòu)、無后效性和貪心選擇性（這里我們不怎么強調(diào)重復(fù)子問題）。

其中，最優(yōu)子結(jié)構(gòu)、無后效性跟動態(tài)規(guī)劃中的無異?！柏澬倪x擇性”的意思是，通過局部最優(yōu)的選擇，能產(chǎn)生全局的最優(yōu)選擇。每一個階段，我們都選擇當(dāng)前看起來最優(yōu)的決策，所有階段的決策完成之后，最終由這些局部最優(yōu)解構(gòu)成全局最優(yōu)解。