動態(tài)規(guī)劃入門論文

1、面這個模型狀態(tài)動態(tài)規(guī)劃思想入門作者：陳喻( 2008年 10月 7 日)關(guān)鍵字：動態(tài)規(guī)劃，最優(yōu)子結(jié)構(gòu)，記憶化搜索引言 動態(tài)規(guī)劃 (dynamic programming) 是運籌學(xué)的一個分支，是求解決策過程 (decisionprocess) 最優(yōu) 化的數(shù)學(xué)方法 。20 世紀(jì) 50 年代初美國數(shù)學(xué)家 R.E.Bellman 等人在研究多階段決策過程 (multistep decision process) 的優(yōu) 化問題時，提出了著名的最優(yōu)化原理 (principle of optimality) ，把多階段過程 轉(zhuǎn)化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法 動態(tài)規(guī)劃。

2、1957 年出版了他的名著 Dynamic Programming ，這是該領(lǐng) 域的第一本著作。動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得 到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載 等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題， 但是一些與 時間無關(guān)的靜態(tài)規(guī)劃 ( 如線性規(guī)劃、非線性規(guī)劃 ) ，只要人為地引進(jìn)時間因素，把 它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。動態(tài)規(guī)劃的基本思想 動態(tài)規(guī)劃是：將待求的問題分解成若干個相互聯(lián)系的子問題， 先求解子問題， 然 后從這些子

3、問題的解得到原問題的解； 對于重復(fù)出現(xiàn)的子問題， 只在第一次遇到 的時候?qū)λ苯忧蠼猓?并把答案保存起來， 讓以后再次遇到是直接引用答案， 不 必從新求解，其實質(zhì)是分治思想和解決冗余。例 1：求 A >B 的最短路徑這是一個利用動態(tài)規(guī)劃思想的經(jīng)典問題， 通過直接觀察圖 1 我們可以枚舉出20 多條路徑，并可以計算出其中最短的路徑長度為 16用動態(tài)規(guī)劃的思想來分析，我們可以把這個問題轉(zhuǎn)換成階段圖2將問題按時間或空間特征分解為若干相互聯(lián)系的階段。在本例中，我們根據(jù)空間特性將問題分成了 6 個階段狀態(tài)： 各階段的開始條件，本例中， A,B,CP這些節(jié)點都屬于狀態(tài)，表示從該點到B的最短路徑，在這

4、里我們計做 S(i)，表示從第 i個節(jié)點(狀態(tài))到 B的最 短路徑 決策：某階段狀態(tài)確定后，從該狀態(tài)到下階段某狀態(tài)的選擇。比如 S(A) ，它可以 選擇通過 C到達(dá) B，也可以選擇通過 D到達(dá)B。 狀態(tài)轉(zhuǎn)移方程：系統(tǒng)由某階段的一個狀態(tài)轉(zhuǎn)變到下一階段的另一狀態(tài)稱狀態(tài)轉(zhuǎn) 移，體現(xiàn)轉(zhuǎn)移規(guī)律的方程稱狀態(tài)轉(zhuǎn)移方程。在本例中，我們不難推出S(A)=MINS(C)+4,S(D)+3,S(C)=MINS(E)+5,S(F)+3 S(B)=0 ，由此我 們可以得出狀態(tài)轉(zhuǎn)移方程 (i)=MINS(j)+Vij(j 為與i相鄰接的節(jié)點， Vij 表示鄰接 節(jié)點 i，j之間的距離 )。一個動態(tài)規(guī)劃模型應(yīng)該滿足以下幾個

5、性質(zhì)：1.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)可這樣闡述： 一個最優(yōu)化策略具有這樣的性質(zhì)， 不論過去狀態(tài)和 決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。 簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。例如在圖 2 的模型中， S(A) 是A到B的最短路徑 (最優(yōu)策略)，而它所依賴的 S(C)和S(D)作為 S(A)的子策略 分別是 C到B 的最短路徑和 D到B的最短路徑，也是最優(yōu)的。因此根據(jù)最優(yōu)子 結(jié)構(gòu)性質(zhì)我們得出了上面的狀態(tài)轉(zhuǎn)移方程。證明：如圖 2 設(shè)路線 W1=(A,C),(C,F),(F,J)W2=(J,M),(M,O),(O,B)若路線 W1 和 W2 是 A 到 B 的最

6、優(yōu)路徑， 則根據(jù)最優(yōu)化原理， 路線 W2 必是從 J 到 B 的最優(yōu)路線。用反證法證明：假設(shè)有另一路徑 W2'是 J 到B 的最優(yōu)路徑， 則 A 到 B 的路線取 W1 和 W2' 比 W1 和 W2 更優(yōu)，矛盾。從而證明 W2' 必是 J 到 B 的最優(yōu)路徑 W2 。最優(yōu)子結(jié)構(gòu)性質(zhì)是動態(tài)規(guī)劃的基礎(chǔ)， 任何問題， 如果失去了最優(yōu)子結(jié)構(gòu)性質(zhì) 的支持，就不可能用動態(tài)規(guī)劃方法計算。 根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)導(dǎo)出的動態(tài)規(guī)劃狀 態(tài)轉(zhuǎn)移方程是解決一切動態(tài)規(guī)劃問題的基本方法?？梢钥闯?，圖 2 的模型是滿足最優(yōu)子結(jié)構(gòu)性質(zhì)的。2子問題重疊性質(zhì) 在我們根據(jù)狀態(tài)轉(zhuǎn)移方程用遞歸算法自頂向下對問題進(jìn)行

7、求解時， 每次產(chǎn)生的子 問題并不總是新的，而且某些子問題會被重復(fù)計算多次，比如，在求S（ C）時需要遞歸求出 S（F）的值，而在求 S（D）時也需要遞歸求出 S（F）的值，因此 整個求解過程中 S（ F）的值會被求解兩次，如果我們能把這多余的一次重復(fù)計 算剔除，將可以最大程度的提高程序執(zhí)行效率； 動態(tài)規(guī)劃正是利用了這種子問題 的重疊性質(zhì)， 對每個子問題只計算一次， 然后將其結(jié)果保存在一個表格中， 當(dāng)再 次需要計算已經(jīng)計算過的子問題時， 只是在表格中簡單的查詢一下結(jié)果， 從而獲 得較高的解題效率， 這個方法就是我們常說的 記憶化搜索 。因此，如果我們把第 一次求解出的 S（F）的值用一種數(shù)據(jù)結(jié)構(gòu)

8、保存下來，下次再用到 S（F）時，我 們直接去查，這樣能使程序的時間和空間效率將會大大提高。下面通過對具體實例的分析， 幫助大家領(lǐng)會動態(tài)規(guī)劃的這兩個性質(zhì)和動態(tài)規(guī)劃的 算法設(shè)計思想例：導(dǎo)彈攔截某國為了防御敵國的導(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)

9、彈 ,并依次輸出被攔截的導(dǎo)彈飛來時候的高度 .樣例:INPUT 389 207 155 300 299 170 158 65OUTPUT 6 （ 最多能攔截的導(dǎo)彈數(shù) ）389 300 299 170 158 65分析: 因為只有一套導(dǎo)彈攔截系統(tǒng) ,并且這套系統(tǒng)除了第一發(fā)炮彈能到達(dá)任意高 度外,以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度 ;所以,被攔截的導(dǎo)彈應(yīng)該 按飛來的高度組成一個非遞增序列 .題目要求我們計算這套系統(tǒng)最多能攔截的導(dǎo) 彈數(shù),并依次輸出被攔截導(dǎo)彈的高度 ,實際上就是要求我們在導(dǎo)彈依次飛來的高 度序列中尋找一個最長非遞增子序列 .解決思路：設(shè) X=x 1 ,x 2 , ,x n 為

10、依次飛來的導(dǎo)彈序列 , Y=y 1 ,y 2 , ,y k 為問題的最優(yōu)解 （即 X 的最長非遞增子序列 ）, s 為問題的狀態(tài) （表 示導(dǎo)彈攔截系統(tǒng)當(dāng)前發(fā)送炮彈能夠到達(dá)的最大高度 ,初值為 s= 第一發(fā) 炮彈能夠到達(dá)任意的高度 ）.如果 y 1 =x 1 , 即飛來的第一枚導(dǎo)彈被成功攔截 .那 么,根據(jù)題意 "每一發(fā)炮彈都不能高于前一發(fā)的高度 ",問題的狀態(tài)將由 s= 變 成 sx 1 （ x 1 為第一枚導(dǎo)彈的高度 ）; 在當(dāng)前狀態(tài)下 ,序列 Y 1 =y 2 , ,y k 也應(yīng)該是序列 X 1 =x 2 , ,x n 的最長非遞增子序列 （用反證法很容易證 明）.也就

11、是說 ,在當(dāng)前狀態(tài) sx 1 下,問題的最優(yōu)解 Y 所包含的子問題 （序列 X 1 ） 的解（序列 Y 1 ） 也是最優(yōu)的 .這就是攔截導(dǎo)彈問題的最優(yōu)子結(jié)構(gòu)性質(zhì) .根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)推出狀態(tài)轉(zhuǎn)移方程：設(shè) D（i） 為第 i 枚導(dǎo)彈被攔截之后 ,這 套系統(tǒng)最多還能攔截的導(dǎo)彈數(shù) （包含被攔截的第 i 枚）.我們可以設(shè)想 ,當(dāng)系統(tǒng)攔 截了第 k 枚導(dǎo)彈 x k , 而 x k 又是序列 X=xk , ,xn 中的最小值 ,即第 k 枚導(dǎo)彈之后飛來的導(dǎo)彈高度都比它高 ,則有 D（k）=1 ; 當(dāng)系統(tǒng)攔截了最后一枚導(dǎo) 彈 x n , 那么,系統(tǒng)最多也只能攔截這一枚導(dǎo)彈了 ,即 D（n）=1 ; 其它情況

12、下 ,也1 （i=n 或者 xi=minxi Xn）D（i）=MaxD（j）+1 （j>i 且 j<=n 且 xj<=xi）應(yīng)該有 D(i) 1 .根據(jù)以上分析 ,可歸納出問題的動態(tài)規(guī)劃遞歸方程為假設(shè)系統(tǒng)最多能攔截的導(dǎo)彈數(shù)為 dmax ( 即問題的最優(yōu)值 ), 則dmax ( i 為被系統(tǒng)攔截的第一枚導(dǎo)彈的順序號 )所以,要計算問題的最優(yōu)值 dmax , 需要分別計算出 D(1) , D(2) , D(n) 的 值,然后將它們進(jìn)行比較 ,找出其中的最大值 .即： dmax=maxD(i)(1<=i且i<=n)分析子問題重疊，解決冗余根據(jù)上面分析出來的遞歸方程 ,我

13、們完全可以設(shè)計一個遞歸函數(shù) , 采用自頂向下 的方法計算 D(i) 的值.然后, 對 i 從 1 到 n 分別調(diào)用這個遞歸函數(shù) ,就可以計 算出 D(1) , D(2) , D(n) . 程序如下：int D(int i)int j,max=0;if(i=n)|(min(x,i,n)=xi)/min(x,i,n) 返回數(shù)組 x 在下標(biāo) i n 之間的最小值return 1;elsefor(j=i+1;j<=n;j+)if(xj<=xi)if(D(j)+1>max)max=D(j)+1;return max;從這個程序的遞歸模型中可以看出，會有大量的子問題被重復(fù)計算. 比如在調(diào)

14、用遞歸函數(shù)計算 D(1) 的時候,可能需要先計算 D(5) 的值; 之后在分別調(diào)用遞歸 函數(shù)計算 D(2) , D(3) , D(4)的時候 ,都有可能需要先計算 D(5) 的值.如此一來,在整個問題的求解過程中 , D(5) 可能會被重復(fù)計算很多次 ,從而造成了冗 余 ,降低了程序的效率 .其實,通過以上分析 ,我們已經(jīng)知道 : D(n)=1 . 如果將 n 作為階段對問題進(jìn)行劃 分,根據(jù)問題的動態(tài)規(guī)劃遞歸方程 , 我們可以采用自底向上的方法依次計算出 D(n-1) , D(n- 2) , D(1)的 值.這樣,每個 D(i) 的值只計算一次 ,并在計算 的同時把計算結(jié)果保存下來 ,程序如下

15、：void D()int i,j;for( i=1;i<=n;i+)d(i)=1for(i=n-1;i>=1;i-)for(j=i+1;j<=n;j+)if (x(j)<=x(i) && d(i)=d(j)+1>dmax)dmax=d(i);xh=i;由此我們出了最大攔截數(shù)的第一枚導(dǎo)彈的順序號xh，即 d(xh)為問題的解從而避免了有些子問題被重復(fù)計算的情況發(fā)生 ,提高了程序的效率 .在實際應(yīng)用中， 許多問題的階段劃分并不明顯， 這時如果刻意地劃分階段反而麻 煩。一般來說， 只要該問題可以劃分成規(guī)模更小的子問題， 并且原問題的最優(yōu)解 中包含了子問題

16、的最優(yōu)解 （即滿足最優(yōu)子化原理） ，則可以考慮用動態(tài)規(guī)劃解決， 也就是分治算法的思想。例 2 ：傳球游戲（ NOIP2008 普及組第三題）【問題描述】上體育課的時候，小蠻的老師經(jīng)常帶著同學(xué)們一起做游戲。這次，老師帶著 同學(xué)們一起做傳球游戲。游戲規(guī)則是這樣的： n 個同學(xué)站成一個圓圈，其中的一個同學(xué)手里拿著一個 球，當(dāng)老師吹哨子時開始傳球， 每個同學(xué)可以把球傳給自己左右的兩個同學(xué)中的 一個（左右任意），當(dāng)老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的 那個同學(xué)就是敗者，要給大家表演一個節(jié)目。聰明的小蠻提出一個有趣的問題： 有多少種不同的傳球方法可以使得從小蠻 手里開始傳的球，傳了 m 次以

17、后，又回到小蠻手里。兩種傳球的方法被視作不 同的方法， 當(dāng)且僅當(dāng)這兩種方法中， 接到球的同學(xué)按接球順序組成的序列是不同 的。比如有 3 個同學(xué) 1 號、2 號、3號，并假設(shè)小蠻為 1 號，球傳了 3 次回到小 蠻手里的方式有 1->2->3->1 和 1->3->2->1 ，共 2 種?！据斎搿枯斎胛募?ball.in 共一行，有兩個用空格隔開的整數(shù) n，m（ 3<=n<=30 ， 1<=m<=30 ）?！据敵觥枯敵鑫募?ball.out 共一行，有一個整數(shù)，表示符合題意的方法數(shù)?！据斎胼敵鰳永縝all.inball.out2【限制

18、】40% 的數(shù)據(jù)滿足： 3<=n<=30 ， 1<=m<=20100% 的數(shù)據(jù)滿足： 3<=n<=30 ， 1<=m<=30解決思路：給 n 個同學(xué)從 1n 編號，設(shè)狀態(tài) Fp,t表示傳了 t 次球后，球在 p 手中，在剩下的 m-t 次傳球中共有多少種方案到達(dá) 1，由于在問題的求解中，球 是從 1 號開始傳，并最后回到 1 號，顯然我們所求的目標(biāo)狀態(tài)就是是 F1,0 。由 于球只能傳遞給左右的兩個同學(xué)， 也只能通過左右的兩個同學(xué)傳遞給自己， 如下 圖：由此，我們分析出 F1,0的解只與 F1,1和 Fn,1有關(guān)，而F1,1和 Fn,1也是最 優(yōu)

19、問題解，因此，該問題符合最優(yōu)子結(jié)構(gòu)性質(zhì)。根據(jù)最優(yōu)性原理我們可以得到以下狀態(tài)轉(zhuǎn)移方程：1 (t=m ， p=1)F(p,t)=，0<=t<m)0 (t=m ， p!=1)FRp,t+1+FLp,t+1 (1<=p<=nRp ： p 右邊同學(xué)的編號Lp ： p 左邊同學(xué)的編號通過以上分析， 根據(jù)狀態(tài)轉(zhuǎn)移方程， 運用記憶化搜索策略， 采用自頂向下的過程 可遞歸求出 F1,0 ，程序如下：#include<stdio.h> #include<stdlib.h>#define maxn 31/ 最大人數(shù)，編號從 1 n#define maxm 30/ 最大

20、傳球次數(shù)long fmaxnmaxm;/ 表示傳了 T 次球以后球在 P 號手里，包括在剩下的 M-T 次傳球中有 多少種方法走到 1long m,n;void find(long p,long t)if(t=m)/ 傳了 M 次球了if(p=1)/ 傳到了 1fpt=1;else/ 沒傳到 1fpt=0;return;if(fpt!=-1) return;/ 如果這個狀態(tài)搜到過了，沒必要再搜fpt=0;/ 標(biāo)記該狀態(tài)被搜過了find(p%n+1,t+1);/ 搜把球傳給 P 右邊的同學(xué)的狀態(tài)fpt+=fp%n+1t+1;int p1=p-1;if(p1=0)p1=n;find(p1,t+1);/ 搜把球傳給 P 左邊的同學(xué)的狀態(tài)fpt+=fp1t+1;main()int i,j;/一開始所有狀態(tài)都沒到過for(i=0;i<maxn;i+) for(j=0;j<maxm;j+) fij=-1;scanf("%d%d",&n,&m);find(1,0);printf("%ld",f10);代入數(shù)據(jù)測算例： input ：3 3數(shù)據(jù)模型如下：可以從記憶數(shù)組中直接獲取；：需搜索記憶的狀態(tài)；由于采用了記憶化搜索， 處于不同位置的相同狀態(tài)不會被多次搜索， 因此可以在 O（m ×n