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

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