1、動態規劃思想入門作者：陳喻(2008年10月7日)關鍵字：動態規劃，最優子結構，記憶化搜索引言動態規劃(dynamicprogramming)是運籌學的一個分支，是求解決策過程(decisionprocess)最優化的數學方法。20世紀50年代初美國數學家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優化問題時，提出了著名的最優化原理(principleofoptimality),把多階段過程轉化為一系列單階段問題，逐個求解，創立了解決這類過程優化問題的新方法動態規劃。1957年出版了他的名著DynamicProgramming,這是該領域

2、的第一本著作。動態規劃問世以來，在經濟管理、生產調度、工程技術和最優控制等方面得到了廣泛的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態規劃方法比用其它方法求解更為方便。雖然動態規劃主要用于求解以時間劃分階段的動態過程的優化問題，但是一些與時間無關的靜態規劃(如線性規劃、非線性規劃)，只要人為地引進時間因素，把它視為多階段決策過程，也可以用動態規劃方法方便地求解。動態規劃的基本思想動態規劃是：將待求的問題分解成若干個相互聯系的子問題，先求解子問題，然后從這些子問題的解得到原問題的解；對于重復出現的子問題，只在第一次遇到的時候對它直接求解，并把答案保存起來，讓以后再次

3、遇到是直接引用答案，不必從新求解，其實質是分治思想和解決冗余。例1:求A>B的最短路徑這是一個利用動態規劃思想的經典問題，通過直接觀察圖1我們可以枚舉出20多條路徑，并可以計算出其中最短的路徑長度為16用動態規劃的思想來分析，我們可以把這個問題轉換成下面這個模型階段：根據問題的特點和需要，將問題按時間或空間特征分解為若干相互聯系的階段。在本例中，我們根據空間特性將問題分成了6個階段。狀態：各階段的開始條件，本例中，A,B,CP這些節點都屬于狀態，表示從該點到B的最短路徑，在這里我們計做S(i),表示從第i個節點(狀態)到B的最短路徑決策：某階段狀態確定后，從該狀態到下階段某狀態的選擇。比

4、如S(A),它可以選擇通過C到達B,也可以選擇通過D到達B。狀態轉移方程：系統由某階段的一個狀態轉變到下一階段的另一狀態稱狀態轉移，體現轉移規律的方程稱狀態轉移方程。在本例中，我們不難推出S(A)=MINS(C)+4,S(D)+3,S(C)=MINS(E)+5,S(F)+3S(B)=0,由此我們可以得出狀態轉移方程S(i)=MINS(j)+Vij(j為與i相鄰接的節點,Vij表示鄰接節點i,j之間的距離)一個動態規劃模型應該滿足以下幾個性質：1 .最優子結構性質最優子結構可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略

5、。簡而言之，一個最優化策略的子策略總是最優的。例如在圖2的模型中，S(A)是A到B的最短路徑(最優策略)，而它所依賴的S(C)和S(D)作為S(A)的子策略分別是C到B的最短路徑和D到B的最短路徑，也是最優的。因此根據最優子結構性質我們得出了上面的狀態轉移方程。證明：如圖2設路線W1=(A,C),(C,F),(F,J)W2=(J,M),(M,O),(O,B)若路線W1和W2是A到B的最優路徑，則根據最優化原理，路線W2必是從J到B的最優路線。用反證法證明：假設有另一路徑W2'是J到B的最優路徑，則A到B的路線取W1和W2'比W1和W2更優，矛盾。從而證明W2'必是J到B

6、的最優路徑W2。最優子結構性質是動態規劃的基礎，任何問題，如果失去了最優子結構性質的支持，就不可能用動態規劃方法計算。根據最優子結構性質導出的動態規劃狀態轉移方程是解決一切動態規劃問題的基本方法。可以看出，圖2的模型是滿足最優子結構性質的。2 .子問題重疊性質在我們根據狀態轉移方程用遞歸算法自頂向下對問題進行求解時，每次產生的子問題并不總是新的，而且某些子問題會被重復計算多次，比如，在求S(C)時需要遞歸求出S(F)的值，而在求S(D)時也需要遞歸求出S(F)的值，因此整個求解過程中S(F)的值會被求解兩次，如果我們能把這多余的一次重復計算剔除，將可以最大程度的提高程序執行效率；動態規劃正是利

7、用了這種子問題的重疊性質，對每個子問題只計算一次，然后將其結果保存在一個表格中，當再次需要計算已經計算過的子問題時，只是在表格中簡單的查詢一下結果，從而獲得較高的解題效率，這個方法就是我們常說的記憶化搜索。因此，如果我們把第一次求解出的S（F）的值用一種數據結構保存下來，下次再用到S（F）時，我們直接去查，這樣能使程序的時間和空間效率將會大大提高。下面通過對具體實例的分析，幫助大家領會動態規劃的這兩個性質和動態規劃的算法設計思想例：導彈攔截某國為了防御敵國的導彈襲擊，發展出一種導彈攔截系統.但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮彈都不能高于前一發

8、的高度.某大，雷達捕捉到敵國的導彈來襲.由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈.輸入導彈依次飛來的高度（雷達給出的高度數據是不大于30000的正整數）,計算這套系統最多能攔截多少導彈，并依次輸出被攔截的導彈飛來時候的高度.樣例：INPUT38920715530029917015865OUTPUT6（最多能攔截的導彈數）38930029917015865分析：因為只有一套導彈攔截系統，并且這套系統除了第一發炮彈能到達任意高度外,以后的每一發炮彈都不能高于前一發炮彈的高度；所以,被攔截的導彈應該按飛來的高度組成一個非遞增序列.題目要求我們計算這套系統最多能攔截的導彈

9、數，并依次輸出被攔截導彈的高度，實際上就是要求我們在導彈依次飛來的高度序列中尋找一個最長非遞增子序列.解決思路：設X=x1,x2,xn為依次飛來的導彈序列，Y=y1,y2,yk為問題的最優解（即X的最長非遞增子序列）,s為問題的狀態（表示導彈攔截系統當前發送炮彈能夠到達的最大高度，初值為s=第一發炮彈能夠到達任意的高度）.如果y1=x1,即飛來的第一枚導彈被成功攔截.那么，根據題意"每一發炮彈都不能高于前一發的高度"，問題的狀態將由s=oo變成s<x1（x1為第一枚導彈的高度）；在當前狀態下，序列Y1=y2,yk也應該是序列X1=x2,xn的最長非遞增子序列（用反證法

10、很容易證明）.也就是說，在當前狀態s<x1下，問題的最優解Y所包含的子問題（序列X1）的解（序列Y1）也是最優的.這就是攔截導彈問題的最優子結構性質.根據最優子結構性質推出狀態轉移方程：設D(i)為第i枚導彈被攔截之后，這套系統最多還能攔截的導彈數(包含被攔截的第i枚).我們可以設想，當系統攔截了第k枚導彈xk，而xk又是序列X=xk,xn)中的最小值，即第k枚導彈之后飛來的導彈高度都比它高，則有D(k)=1;當系統攔截了最后一枚導彈xn，那么，系統最多也只能攔截這一枚導彈了，即D(n)=1;其它情況下，也應該有D(i)>1.根據以上分析，可歸納出問題的動態規劃遞歸方程為：11(i

11、=n或者xi=minxiXn)D(i)=VLMaxD(j)+1(j>i且j<=n且xj<=xi)假設系統最多能攔截的導彈數為dmax(即問題的最優值),則dmax(i為被系統攔截的第一枚導彈的順序號)所以,要計算問題的最優值dmax,需要分別計算出D(1),D(2),D(n)的值,然后將它們進行比較，找出其中的最大值.即：dmax=maxD(i)(1<=i且i<=n)分析子問題重疊，解決冗余根據上面分析出來的遞歸方程，我們完全可以設計一個遞歸函數，采用自頂向下的方法計算D(i)的值.然后，對i從1到n分別調用這個遞歸函數，就可以計算出D(1),D(2),D(n).

12、程序如下：intD(inti)intj,max=0;if(i=n)|(min(x,i,n)=xi)/min(x,i,n)返回數組x在下標in之間的最小值return1;elsefor(j=i+1;j<=n;j+)if(xj<=xi)if(D(j)+1>max)max=D(j)+1;returnmax;)從這個程序的遞歸模型中可以看出，會有大量的子問題被重復計算.比如在調用遞歸函數計算D(1)的時候，可能需要先計算D(5)的值；之后在分別調用遞歸函數計算D(2),D(3),D(4)的時候，都有可能需要先計算D(5)的值.如此一來,在整個問題的求解過程中，D(5)可能會被重復計算

13、很多次，從而造成了冗余，降低了程序的效率.其實,通過以上分析，我們已經知道：D(n)=1.如果將n作為階段對問題進行劃分，根據問題的動態規劃遞歸方程，我們可以采用自底向上的方法依次計算出D(n-1),D(n-2),D(1)的值.這樣，每個D(i)的值只計算一次，并在計算的同時把計算結果保存下來，程序如下：voidD()inti,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;）由此我們

14、出了最大攔截數的第一枚導彈的順序號xh,即d（xh）為問題的解從而避免了有些子問題被重復計算的情況發生，提高了程序的效率.在實際應用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段反而麻煩。一般來說，只要該問題可以劃分成規模更小的子問題，并且原問題的最優解中包含了子問題的最優解（即滿足最優子化原理），則可以考慮用動態規劃解決，也就是分治算法的思想。例2:傳球游戲（NOIP2008普及組第三題）【問題描述】上體育課的時候，小蠻的老師經常帶著同學們一起做游戲。這次，老師帶著同學們一起做傳球游戲。游戲規則是這樣的：n個同學站成一個圓圈，其中的一個同學手里拿著一個球，當老師吹哨子時開始傳球，每個

15、同學可以把球傳給自己左右的兩個同學中的一個（左右任意），當老師再次吹哨子時，傳球停止，此時，拿著球沒傳出去的那個同學就是敗者，要給大家表演一個節目。聰明的小蠻提出一個有趣的問題：有多少種不同的傳球方法可以使得從小蠻手里開始傳的球，傳了m次以后，又回到小蠻手里。兩種傳球的方法被視作不同的方法，當且僅當這兩種方法中，接到球的同學按接球順序組成的序列是不同的。比如有3個同學1號、2號、3號，并假設小蠻為1號，球傳了3次回到小蠻手里的方式有1->2->3->1和1->3->2->1,共2種。【輸入】輸入文件ball.in共一行，有兩個用空格隔開的整數n,m（3<

16、;=n<=30,1<=m<=30）o【輸出】輸出文件ball.out共一行，有一個整數，表示符合題意的方法數。【輸入輸出樣例】ball.in33ball.out2【限制】40%的數據滿足：3<=n<=30,1<=m<=20100%的數據滿足：3<=n<=30,1<=m<=30解決思路：給n個同學從1n編號，設狀態Fp,t表示傳了t次球后，球在p手中，在剩下的m-t次傳球中共有多少種方案到達1,由于在問題的求解中，球是從1號開始傳，并最后回到1號，顯然我們所求的目標狀態就是是F1,0o由于球只能傳遞給左右的兩個同學，也只能通過左右

17、的兩個同學傳遞給自己，如下圖：由此，我們分析出F1,0的解只與F1,1和Fn,1有關，而F1,1和Fn,1也是最優問題解，因此，該問題符合最優子結構性質。根據最優性原理我們可以得到以下狀態轉移方程:1(t=m,p=1)F(p,t)=,0<=t<m)00(t=m,p!=1)<FRp,t+1+FLp,t+1(1<=p<=nRp:p右邊同學的編號Lp：p左邊同學的編號通過以上分析，根據狀態轉移方程，運用記憶化搜索策略，采用自頂向下的過程可遞歸求出F1,0,程序如下：#include<stdio.h>#include<stdlib.h>#defin

18、emaxn31最大人數，編號從1n#definemaxm30最大傳球次數longfmaxnmaxm;/表示傳了T次球以后球在P號手里，包括在剩下的M-T次傳球中有多少種方法走到1longm,n;voidfind(longp,longt)if(t=m)傳了M次球了if(p=1)/傳到了1fpt=1;else/沒傳到1fpt=0;return;if(fpt!=-1)return;/如果這個狀態搜到過了，沒必要再搜fpt=0;/標記該狀態被搜過了find(p%n+1,t+1);/搜把球傳給P右邊的同學的狀態fpt+=fp%n+1t+1;intp1=p-1;if(p1=0)p1=n;find(p1,t+1);/搜把球傳給P左邊的同學的狀態fpt+=fp1t+1;main()inti,j;一開始所有狀態都沒到過for(i=0;i<maxn;i+)for(j=0;j<maxm;j+)fij=-1;scanf("%d%d",&n,&m);find(1,0);代入數據測算例：input:33數據模型如下：_:可以從記憶數組中直接獲取；二：需搜索記憶的狀態；由于采用了記憶化搜索，處于不同位置的相同狀態不會被多次搜索，因此可以在O(mxn)的時間復雜度內完成任務，同樣避免了子問題被重復計算的情況。由此可