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

《動態(tài)規(guī)劃淺談》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、動態(tài)規(guī)劃淺談動態(tài)規(guī)劃(dynamicprogramming)算法是解決多階段決策過程最優(yōu)化問題的一種常用方法，難度比較大，技巧性也很強(qiáng)。利用動態(tài)規(guī)劃算法，可以優(yōu)雅而高效地解決很多貪婪算法或分治算法不能解決的問題。動態(tài)規(guī)劃算法的基本思想是：將待求解的問題分解成若干個相互聯(lián)系的子問題，先求解子問題,然后從這些子問題的解得到原問題的解；對于重復(fù)出現(xiàn)的子問題，只在第一次遇到的時候?qū)λM(jìn)行求解，并把答案保存起來，讓以后再次遇到時直接引用答案，不必重新求解。動態(tài)規(guī)劃算法將問題的解決方案視為一系列決策的結(jié)果，與貪婪算法不同的是，在貪婪算法中，每采用一次貪婪

2、準(zhǔn)則，便做出一個不可撤回的決策；而在動態(tài)規(guī)劃算法中，還要考察每個最優(yōu)決策序列中是否包含一個最優(yōu)決策子序列，即問題是否具有最優(yōu)子結(jié)構(gòu)性質(zhì)。動態(tài)規(guī)劃算法的有效性依賴于待求解問題本身具有的兩個重要性質(zhì)：最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題重疊性質(zhì)。1、最優(yōu)子結(jié)構(gòu)性質(zhì)。如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)(即滿足最優(yōu)化原理)。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決問題提供了重要線索。2、子問題重疊性質(zhì)。子問題重疊性質(zhì)是指在用遞歸算法自頂向下對問題進(jìn)行求解時，每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復(fù)計算多次。動態(tài)規(guī)劃算法

3、正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只計算一次，然后將其計算結(jié)果保存在一個表格中，當(dāng)再次需要計算已經(jīng)計算過的子問題時,只是在表格中簡單地査看一下結(jié)果，從而獲得較高的解題效率。當(dāng)我們己經(jīng)確定待解決的問題需要用動態(tài)規(guī)劃算法求解時，通常可以按照以下步驟設(shè)計動態(tài)規(guī)劃算法：1、分析問題的最優(yōu)解，找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2、遞歸地定義最優(yōu)值；3、采用自底向上的方式計算問題的最優(yōu)值；4、根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。1?3步是動態(tài)規(guī)劃算法解決問題的基本步驟，在只需要計算最優(yōu)值的問題中，完成這三個基本步驟就可以了。如果問題需要

4、構(gòu)造最優(yōu)解，還要執(zhí)行第4步；此時，在第3步通常需要記錄更多的信息，以便在步驟4中，有足夠的信息快速地構(gòu)造出最優(yōu)解。下面通過幾個經(jīng)典例子來演示一下動態(tài)規(guī)劃的具體思想.例1：數(shù)字三角形如下所示的數(shù)字三角形：10從頂向下找出一條權(quán)值最小的路徑。(路徑的權(quán)值等于路徑上各結(jié)點(diǎn)的值的和)用f(i,j)表示位置i,j上最優(yōu)的權(quán)值。則很容易得出遞歸公式：x=f(i+1,j)+a[i,j]y=f(i+,j+l)+a[i,j]f(i,j)=x

5、){intx,y;if(i==n)returnarray[i][j]:x=search(i+1,j)+airay[i][j];y=search(i+1,j+l)+array[i][j];if(x

6、以了。于是動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程就被描述了出來：f(i,j)=a[i,j]+min(f(i+1,j),f(i+1,j+1))我們產(chǎn)取至底向上的求解過程，即先將子問題的最優(yōu)解按照轉(zhuǎn)移方程求解出來，再按照轉(zhuǎn)移方程的要求構(gòu)造出上級問題的解。算法如下：for(i=n-2;i>=0;i—){for(j=0;j<=i;j++){x=array[i][j]+array[i+1][j]:y=array[i][j]+array[i+1][j+1];array[i][j]=x

7、記憶化，將己求解的子問題的解記下來以避免重復(fù)計算。所以動態(tài)規(guī)劃的題目必須滿足重疊子問題的條件。例2：某國為了防御敵國的導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸岀被攔截的導(dǎo)彈飛來時候的高度。SAMPLEINPUT:3892071

8、5530029917015865SAMPLEOUTPUT:638930029917015865因?yàn)橹挥幸惶讓?dǎo)彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達(dá)任意高度外，