貪心算法、分治算法、動態(tài)規(guī)劃算法間的比較

題目：貪心算法、分治算法、動態(tài)規(guī)劃算法間的比較貪心算法：貪心算法采用的是逐步構(gòu)造最優(yōu)解的方法。在每個階段，都在一定的標(biāo)準(zhǔn)下做出一個看上去最優(yōu)的決策。決策一旦做出，就不可能再更改。做出這個局部最優(yōu)決策所依照的標(biāo)準(zhǔn)稱為貪心準(zhǔn)則。分治算法：分治法的思想是將一個難以直接解決大的問題分解成容易求解的子問題，以便各個擊破、分而治之。動態(tài)規(guī)劃：將待求解的問題分解為若干個子問題，按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。二、算法間的關(guān)聯(lián)與不同1、分治算法與動態(tài)規(guī)劃分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)?？s小到一定程度就可以容易地解決。該問題可以分為若干個較小規(guī)模的相似的問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。利用該問題分解出的子問題的解可以合并為該問題的解。該問題所分解出的各個子問題是相互獨立的且子問題即之間不包含公共的子問題。上述的第一條特征是絕大多數(shù)問題都可以滿足的，因為問題的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加；第二條特征是分治法應(yīng)用的前提，它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮貪心算法或動態(tài)規(guī)劃算法；第四條特征涉及到分治法的效率，如果各個子問題不是獨立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。這類問題雖然可以用分治法解決，但用動態(tài)規(guī)劃算法解決效率更高。當(dāng)問題滿足第一、二、三條，而不滿足第四條時，一般可以用動態(tài)規(guī)劃法解決，可以說，動態(tài)規(guī)劃法的實質(zhì)是：分治算法思想+解決子問題冗余情況2、貪心算法與動態(tài)規(guī)劃算法多階段逐步解決問題的策略就是按一定順序或一定的策略逐步解決問題的方法。分解的算法策略也是多階段逐步解決問題策略的一種表現(xiàn)形式，主要是通過對問題逐步分解，然后又逐步合并解決問題的。貪心算法每一步都根據(jù)策略得到一個結(jié)果，并傳遞到下一步，自頂向下，一步一步地做出貪心決策。動態(tài)規(guī)劃算法的每一步?jīng)Q策給出的不是唯一結(jié)果，而是一組中間結(jié)果，而且這些結(jié)果在以后各步可能得到多次引用，只是每走一步使問題的規(guī)模逐步縮小，最終得到問題的一個結(jié)果。舉例：如圖1有一三角形數(shù)塔，求一自塔頂?shù)剿椎穆窂?，要求該路徑上結(jié)點的值的和最大。圖1圖2貪心算法解題過程：自頂向下從第一層9開始，到第二層，選數(shù)值較大的15，第三層，在可選路徑中選數(shù)值較大的8,同理，第四層選9，第五層選10,這樣就確定了一條路徑：9一15—8—9一10。動態(tài)規(guī)劃算法接題過程：如圖2，階段1：自第五層開始，對經(jīng)過第四層的2的路徑,在第五層的19、7中選擇數(shù)值較大的19,同理,對經(jīng)過第四層18的路徑,選10,對經(jīng)過第四層9的路徑,選10,對經(jīng)過5的路徑選16。以上是一次決策過程,也是一次遞推過程和降階過程。因為以上的決策結(jié)果將5階數(shù)塔問題變?yōu)?階子問題,遞推出第四層與第五層和為:21(2+19),28(18+10),19(9+10),21(5+16)用同樣的方法還可以將4階數(shù)塔問題變?yōu)?階數(shù)塔問題，……，最后得到1階數(shù)塔問題，這樣也確定了一條路徑：9-12-10-18-10,就是真?zhèn)€問題的最優(yōu)解。顯然，以上數(shù)塔問題用貪心算法得不到最優(yōu)解，這里只是用作與動態(tài)規(guī)劃算法的比較。三、適用條件貪心算法：①貪心選擇性質(zhì)：在求解一個問題的過程中，如果再每一個階段的選擇都是當(dāng)前狀態(tài)下的最優(yōu)選擇，即局部最優(yōu)選擇，并且最終能夠求得問題的整體最優(yōu)解，那么說明這個問題可以通過貪心選擇來求解，這時就說明此問題具有貪心選擇性質(zhì)。②最優(yōu)子結(jié)構(gòu)性質(zhì)：當(dāng)一個問題的最優(yōu)解包含了這個問題的子問題的最優(yōu)解時，就說明該問題具有最優(yōu)子結(jié)構(gòu)。分治算法：見二、算法間的關(guān)聯(lián)與不同中的①②③④。動態(tài)規(guī)劃：(1)最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理。(2)無后效性：即某階段狀態(tài)一旦確定，就不受這個狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。(3)有重迭子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。四、優(yōu)勢：采用動態(tài)規(guī)劃方法，可以高效地解決許多用貪婪算法或分而治之算法無法解決的問題。但貪心算法也有它的優(yōu)勢：構(gòu)造貪心策略不是很困難，而且貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法。參考文獻：《算法設(shè)計