動態(tài)規(guī)劃算法舉例分析

1、動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法介紹基本思想是將待求解問題分解成若干子問題，先求解子問題，最后用這些子 問題帶到原問題，與分治算法的不同是，經(jīng)分解得到的子問題往往是不是相互獨 立，若用分治則子問題太多。適用動態(tài)規(guī)劃算法問題的特征（1）最優(yōu)子結(jié)構(gòu)設(shè)計動態(tài)規(guī)劃算法的第一步驟通常是要刻畫最優(yōu)解的結(jié)構(gòu)。當問題的最優(yōu)解 包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu) 性質(zhì)提供了該問題可用動態(tài)規(guī)劃算法求解的重要線索。在動態(tài)規(guī)劃算法中，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)使我們能夠以自底向下的方式遞 歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。同時，它也使我們能在相 對小的子問題空間中考慮問題。（2）重

2、疊子問題可用動態(tài)規(guī)劃算法求解的問題應(yīng)具備的另一基本要素是子問題的重疊性質(zhì)。 在用遞歸算法自頂向下解此問題時，每次產(chǎn)生的子問題并不總是新問題，有些子 問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一 個子問題只解一次，而后將其解保存在一個表格中，當再次需要解此子問題時， 只有簡單地用常數(shù)時間查看一下結(jié)果。通常，不同的子問題個數(shù)隨輸入問題的大 小呈多項式增長。因此，用動態(tài)規(guī)劃算法通常只需要多項式時間，從而獲得較高 的解題效率。（3）備忘錄方法動態(tài)規(guī)劃算法的一個變形是備忘錄方法。備忘錄方法也是一個表格來保存已 解決的子問題的答案，在下次需要解此子問題時，只要簡單地查看該子問題的

3、解 答，而不必重新計算。與動態(tài)規(guī)劃算法不同的是，備忘錄方法的遞歸方式是自頂 向下的，而動態(tài)規(guī)劃算法則是自底向上遞歸的。因此，備忘錄方法的控制結(jié)構(gòu)與 直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了 備忘錄以備需要時查看，避免了相同子問題的重復(fù)求解。備忘錄方法為每個子問題建立一個記錄項，初始化時，該記錄項存入一個特 殊的值，表示該子問題尚未求解。在求解過程中，對每個待求的子問題，首先查 看其相應(yīng)的記錄項。若記錄項中存儲的是初始化時存入的特殊值，則表示該子問 題是第一次遇到，則此時計算出該子問題的解，并保存在其相應(yīng)的記錄項中。若 記錄項中存儲的已不是初始化時存入的特殊值，則表

4、示該子問題已被計算過，其 相應(yīng)的記錄項中存儲的是該子問題的解答。此時，只要從記錄項中取出該子問題 的解答即可?；静襟Ea、找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。b、遞歸地定義最優(yōu)值。以自底向上的方式計算出最優(yōu)值。d、根據(jù)計算最優(yōu)值時得到的信息構(gòu)造一個最優(yōu)解。（可?。├?-1 0/1背包問題問題描述用貪心算法不能保證求出最優(yōu)解。在0/1背包問題中，需要對容量為c的背 包進行裝載。從n個物品中選取裝入背包的物品，每件物品i的重量為七，價 值為七。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳 八ILwx c裝載是指所裝入的物品價值最高，即頃取得最大值。約束條件為 ， x. G 0,出

5、 i n）o在這個表達式中，需要求七的值。七=1表示物品i裝入背包中，七二0 表示物品i不裝入背包。1.找出最優(yōu)解性質(zhì)考察上述0 / 1背包問題。如前所述，在該問題中需要決定x1，xn的 值。假設(shè)按i=1，2,，n的次序來確定xi的值。如果置x1 = 0，則問題 轉(zhuǎn)變?yōu)橄鄬τ谄溆辔锲罚次锲?, 3,，n），背包容量仍為c的背包問題。 若置x1 = 1，問題就變?yōu)殛P(guān)于最大背包容量為c-w1的問題?，F(xiàn)設(shè)rG（c，c-w1） 為剩余的背包容量。在第一次決策之后，剩下的問題便是考慮背包容量為r時的決策。不管x1 是0或是1，x2，xn 必須是第一次決策之后的一個最優(yōu)方案，如果不 是，則會有一個更好的

6、方案y2,，yn，因而x1，y2,，yn 是一個更好的方案。因此最優(yōu)解符合條件， w x v w y + w x wn0 j wi0 j wi因此，m (1, c)是初始時最優(yōu)問題的最優(yōu)解。(1)(2)現(xiàn)在計算xi值，步驟如下：若m(1 ,c) =m( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩余容量c-w1中尋求最優(yōu)解，用m(2, c-w1)表示最優(yōu)解。依此 類推，可得到所有的xi (i= 1，2,，n)值。0/1背包問題的C語言實現(xiàn)算法#define N 12void Knapsack(int v,int w,int c,int n,int m6N) int i,j,jMa

7、x,k;jMax=(wn-1c?wn-1:c);for(i=0;i=jMax;i+)mni=0;for(i=wn;i1;i)jMax=(wi-1c?wi-1:c);for(j=0;j=jMax;j+)mij=mi+1j;for(j=wi;j=c;j+)k=j-wi;if(mi+1j=w1)k=c-w1;m1c = (m2cm2k+v1)?m2c:m2k+v1;void Traceback(int m6N,int w,int c,int n,int x)int i;for(i=1;iN;i+)if(mic=mi+1c)xi=0;elsexi=1;c-=wi;xn = (mnc)?1:0;main

8、()int i,c=10,n=5,w = 0,2,2,6,5,4,v = 0,6,3,5,4,6;int m6N = 0;int x6 = 0;int j;Knapsack(v,w,c,n,m);for(i=1;i=n;i+)for(j=1;j=c;j+)printf(%3d,mij);printf(n)；Traceback(m,w,c,n,x);for(i=1;i=n;i+)if(xi)printf(4d:%4d，i,vi);printf(n)；例2-1 最短路徑問題問題描述現(xiàn)有一張地圖，各結(jié)點代表城市，兩結(jié)點間連線代表道路，線上數(shù)字表示城 市間的距離。如圖2所示，試找出從結(jié)點1到結(jié)點7的最

9、短路徑。圖2 有向圖找出最優(yōu)解性質(zhì)在第一次決策到達了某個節(jié)點t之后，不管t怎樣確定，剩下的問題就是選 擇從七到vj的最短路徑。在所有點對最短路徑問題（a l l - p a i r sshorest-paths problem） 中，要尋找有向圖G中每對頂點之間的最短路徑。也就是說，對于每對頂點（i, j）， 需要尋找從i到j(luò)的最短路徑及從j到i的最短路徑。因此對于一個n個頂點 的圖來說，需尋找p =n（n-1）條最短路徑。假定圖G中不含有長度為負數(shù)的環(huán) 路，只有在這種假設(shè)下才可保證G中每對頂點（i, j）之間總有一條不含環(huán)路的 最短路徑。遞歸定義最優(yōu)值上述問題已經(jīng)轉(zhuǎn)化為尋找從i到j(luò)的最短路徑

10、。若記最短路徑的長度為eej. 遜縣將其初始值賦值為。設(shè)k為從i到j(luò)中節(jié)點編號中最大的數(shù)，則用C（i，j，k）表示經(jīng)過節(jié)點k 的i，j通路的路徑長度。若 C（i，j，k） eej，則 eej =C（i，j，k）。如此尋遍i, j中每條通路，則得到的eej為i, j的最短路徑長度。最后遞 歸得到從節(jié)點1到節(jié)點7的最短路徑長度。最短路徑問題的C語言算法實現(xiàn)#include #define N 7#define I 999int graphNN = I, 4, 5, 8, I, I, I,I, I, I, 6, 6, I, I,I, I, I, 5, I, 7, I,I, I, I, I, 8, 9

11、, 9,I, I, I, I, I, I, 5,I, I, I, I, I, I, 4,I, I, I, I, I, I, I/*頂點數(shù)目 */*表示無窮大*/*圖的鄰接矩陣*/；int ListN;int TopologicalOrder();/*存放拓撲序列*/*拓撲排序函數(shù)*/void main()/* 主 函 數(shù) */int i, j, k, l;int eeN;/* 最短距離 */int path_eNN, n_eN;/* 記錄路徑數(shù)據(jù) */*初始化數(shù)據(jù)*/for (i = 0; i N; i+) n_ei = 0;eei = I;ee0 = 0;path_e00 = 0;n_e0

12、= 1;/*拓撲排序*/ if (!TopologicalOrder() return;/*到i的最短路線的結(jié)點數(shù)*/*初始化頭結(jié)點*/*提取拓撲序列的元素*/*更新它所指向頂點的所有數(shù)/*對于拓撲序列，運用動態(tài)規(guī)劃步步算出最短路線*/for (i = 0; i N; i+) k = Listi;for (j = 0; j N; j+) 據(jù) */ if (graphkj != I)/*尋找指向的頂點*/*棧頂標志*/*初始化入度*/*如連通*/*入度自增1*/*如入度為零*/* 入棧*/*輸出頂點數(shù)*/*如連通*/if (graphkj + eek eej) /* 如果新路徑更短 */ eej

13、 = graphkj + eek; /* 更新最短路徑長度 */for (l = 0; l n_ek; l+) /* 更新最短路線 */ path_ejl = path_ekl; path_ejl = j; n_ej = l + 1; /*輸出結(jié)果到屏幕*/for (i = 0; i N; i+) printf(shortest(%d): %2d Path: , i + 1, eei); for (j = 0; j n_ei; j+) printf(%d , path_eij + 1);printf(n);int TopologicalOrder()int i, j, top, count;i

14、nt indegreeN, StackN;top = 0;for (i = 0; i N; i+) indegreei = 0;for (j = 0; j N; j+) if (graphji != I) indegreei+;if (!indegreei) Stacktop+ = i;count = 0;while (top != 0)i = Stacktop;Listcount+ = i;if (!(-indegreej) /*而且入度為零*/Stacktop+ = j;/* 入棧*/for (j = 0; j N; j+) if (graphij != I) /* for */* whi

15、le */return （count N） ? 0 : 1;例3 航費問題某航線價格表為：從亞特蘭大到紐約或芝加哥，或從洛杉 磯到亞特蘭大的費用為$ 100；從芝加哥到紐約票價$20；而對于路經(jīng)亞特蘭大的 旅客，從亞特蘭大到芝加哥的費用僅為$20。從洛杉磯到紐約的航線涉及到對中 轉(zhuǎn)機場的選擇。如果問題狀態(tài)的形式為（起點，終點），那么在選擇從洛杉磯到 亞特蘭大后，問題的狀態(tài)變?yōu)椋▉喬靥m大，紐約）。從亞特蘭大到紐約的最便宜 航線是從亞特蘭大直飛紐約，票價$100。而使用直飛方式時，從洛杉磯到紐約的 花費為$200。不過，從洛杉磯到紐約的最便宜航線為洛杉磯-亞特蘭大-芝加哥- 紐約，其總花費為$ 1

16、40 （在處理局部最優(yōu)路徑亞特蘭大到紐約過程中選擇了最 低花費的路徑：亞特蘭大-芝加哥-紐約）。如果用三維數(shù)組（tag，起點，終點）表示問題狀態(tài)，其中tag為0表示轉(zhuǎn) 飛，tqg為1表示其他情形，那么在到達亞特蘭大后，狀態(tài)的三維數(shù)組將變?yōu)椋?， 亞特蘭大，紐約），它對應(yīng)的最優(yōu)路徑是經(jīng)由芝加哥的那條路徑。當最優(yōu)決策序列中包含最優(yōu)決策子序列時，可建立動態(tài)規(guī)劃遞歸方程（dy namic-programming recurrence equation），它可以幫助我們高效地解決問題。動態(tài)規(guī)劃算法與其它算法的比較在比較基本的算法設(shè)計思想里，動態(tài)規(guī)劃是比較難于理解，難于抽象的一種， 但是卻又十分重要。動態(tài)規(guī)劃的實質(zhì)是分治思想和解決冗余，因此它與分治法和 貪心法類似，它們都是將問題的實例分解為更小的、相似的子問題，但是動態(tài)規(guī) 劃又有自己的特點。貪心法的當前選擇可能要依賴于已經(jīng)作出的選擇，但不依賴于還未做出的選 擇和子問題，因此它的特征是由頂向下，一步一步地做出貪心選擇，但不足的是， 如果當前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達到全局最 優(yōu)解。相比而言，動態(tài)規(guī)劃則可以處理不具有貪心實質(zhì)的問題。在用分治法解決問題時，由于子問題的數(shù)目往往是問題規(guī)模的指數(shù)函數(shù)，因