動態(tài)規(guī)劃和貪心的區(qū)別.docx

《動態(tài)規(guī)劃和貪心的區(qū)別.docx》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、動態(tài)規(guī)劃和貪心算法的區(qū)別動態(tài)規(guī)劃法的基本思路：動態(tài)規(guī)劃是通過拆分問題，定義問題狀態(tài)和狀態(tài)之間的關(guān)系，使得問題能夠以遞推的方式去解決。此算法常用于求解某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多

2、次。如果我們能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算，節(jié)省時間。我們可以用一個表來記錄所有已解的子問題的答案，消除遞歸過程中產(chǎn)生的大量重疊子問題。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。貪心算法的基本思想：在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，貪心算法所得出的解是一系列局部最優(yōu)的選擇。把求解的問題分成若干個子問題，對每一子問題求解，得到子問題的局部最優(yōu)解，把子問題的解局部最優(yōu)解合成原來解問題的一個解。為了解決問題，需

3、要尋找一個構(gòu)成解的候選對象集合，起初，算法選出的候選對象的集合為空。接下來的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對象中選出最有希望構(gòu)成解的對象。如果集合中加上該對象后不可行，那么該對象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)充集合，并檢查該集合是否構(gòu)成解。由以上可知：在貪心算法中，作出的每步貪心決策都無法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留。并且，每一步的最優(yōu)解一定包含上一步的最優(yōu)解。而在動態(tài)規(guī)劃算法中，全局最優(yōu)解中一定包含某個局部最優(yōu)解，但不一定包含前一個局部最優(yōu)解，因

4、此需要記錄之前的所有最優(yōu)解。動態(tài)規(guī)劃的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程，即如何由以求出的局部最優(yōu)解來推導(dǎo)全局最優(yōu)解。也就是說，把一個復(fù)雜問題分解成一塊一塊的小問題，每一個問題得到最優(yōu)解，再從這些最優(yōu)解中獲取更優(yōu)的答案。