算法設計與分析05動態(tài)規(guī)劃課件

1、第七章 動態(tài)規(guī)劃主要內(nèi)容介紹7.1 一般方法和基本要素7.2 最大字段和7.3 每對結(jié)點間的最短路徑7.4 矩陣連乘問題7.5 最長公共子序列問題7.6最優(yōu)二叉搜索樹主要內(nèi)容介紹7.7 0-1背包問題7.8流水作業(yè)調(diào)度引言動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題。經(jīng)分解得到的子問題往往不是互相獨立的。不同子問題的數(shù)目常常只有多項式量級。在用分治法求解時，有些子問題被重復計算了許多次。如果能夠保存已解決的子問題的答案，而在需要時再找出已求得的答案，就可以避免大量重復計算，從而得到多項式時間算法。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=nT(n)=

2、n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Those who cannot remember the past are doomed to repeat it.George Santayana, The life of Reason, Book I: Int

3、roduction and Reason in Common Sense (1905)第七章 動態(tài)規(guī)劃7.1 一般方法1. 多階段決策問題 多階段決策過程：問題的活動過程分為若干相互聯(lián)系的階段，任一階段i以后的行為僅依賴于i階段的過程狀態(tài)，而與i階段之前的過程如何達到這種狀態(tài)的方式無關。在每一個階段都要做出決策，這決策過程稱為多階段決策過程(multistep decision process) 。 最優(yōu)化問題：問題的每一階段可能有多種可供選擇的決策，必須從中選擇一種決策。各階段的決策構(gòu)成一個決策序列。決策序列不同，所導致的問題的結(jié)果可能不同。 多階段決策的最優(yōu)化問題就是：求能夠獲得問題最優(yōu)解

4、的決策序列最優(yōu)決策序列。2. 多階段決策過程的求解策略1）枚舉法 窮舉可能的決策序列，從中選取可以獲得最優(yōu)解的決策序列2）動態(tài)規(guī)劃 20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動態(tài)規(guī)劃。 動態(tài)規(guī)劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學方法。 應用領域：動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛

5、的應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。3. 最優(yōu)性原理(Principle of Optimality) 過程的最優(yōu)決策序列具有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。 利用動態(tài)規(guī)劃求解問題的前提 1) 證明問題滿足最優(yōu)性原理 如果對所求解問題證明滿足最優(yōu)性原理，則說明用動態(tài)規(guī)劃方法有可能解決該問題 2) 獲得問題狀態(tài)的遞推關系式 獲得各階段間的遞推關系式是解決問題的關鍵。Divide-and-conquer技術(shù)的問題子問題是相互獨立的如果子問題不是相互

6、獨立的，分治方法將重復計算公共子問題，效率很低優(yōu)化問題給定一組約束條件和一個代價函數(shù)，在解空間中搜索具有最小或最大代價的優(yōu)化解很多優(yōu)化問題可分為多個子問題，子問題相互關聯(lián)，子問題的解被重復使用Why? Dynamic Programming特點把原始問題劃分成一系列子問題求解每個子問題僅一次，并將其結(jié)果保存在一個表中，以后用到時直接存取，不重復計算，節(jié)省計算時間自底向上地計算適用范圍一類優(yōu)化問題：可分為多個相關子問題，子問題的解被重復使用What? 使用Dynamic Programming的條件Optimal substructure（優(yōu)化子結(jié)構(gòu)）當一個問題的優(yōu)化解包含了子問題的優(yōu)化解時，我

7、們說這個問題具有優(yōu)化子結(jié)構(gòu)?？s小子問題集合，只需那些優(yōu)化問題中包含的子問題，減低實現(xiàn)復雜性優(yōu)化子結(jié)構(gòu)使得我們能自下而上地完成求解過程Subteties（重疊子問題）在問題的求解過程中，很多子問題的解將被多次使用How? Dynamic Programming算法的設計步驟分析優(yōu)化解的結(jié)構(gòu)遞歸地定義最優(yōu)解的代價自底向上地計算優(yōu)化解的代價保存之， 并獲取構(gòu)造最優(yōu)解的信息根據(jù)構(gòu)造最優(yōu)解的信息構(gòu)造優(yōu)化解 多段圖問題多段圖G=(V,E)是一個有向圖，且具有特性: 結(jié)點：結(jié)點集V被分成k2個不相交的集合Vi，1ik， 其中V1和Vk分別只有一個結(jié)點：s(源結(jié)點)和t(匯點)。 段： 每一集合Vi定義圖中的

8、一段共k段。 邊： 所有的邊(u,v)均具有如下性質(zhì)： 若E，則 若uVi，則uVi1,即該邊將是從某段i指向i+1段， 1ik1。 成本：每條邊(u,v)均附有成本c(u,v)。 s到t的路徑：是一條從第1段的源點s出發(fā)，依次經(jīng)過第2段的某結(jié)點v2,i，經(jīng)第3段的某結(jié)點v3,j、最后在第k段的匯點t結(jié)束的路徑。 該路徑的成本是這條路徑上邊的成本和。 多段圖問題：求由s到t的最小成本路徑。7.1.2 多段圖問題12345678910111297324327111181456356425V1V2V3V4V55段圖7.1.2 多段圖問題1. 問題的描述 在多段圖中求從s到t的一條最小成本的路徑，可

9、以看 作是在k-2個段作出某種決策的結(jié)果。 第i次決策決定Vi+1中的哪個結(jié)點在這條路徑上，這里 1ik-2； 最優(yōu)性原理對多段圖問題成立 多段圖問題的多階段決策過程：生成從s到t的最小成本路徑是在k-2個階段（除s和t外）進行某種決策的過程：從s開始，第i次決策決定Vi+1(1ik-2)中的哪個結(jié)點在從s到t的最短路徑上。 最優(yōu)性原理對多段圖問題成立 假設s,v2,v3,vk-1,t是一條由s到t的最短路徑。 初始狀態(tài)：s 初始決策：(s,v2)， v2V2 初始決策產(chǎn)生的狀態(tài)：v2 則，其余的決策：v3,.,vk-1相對于v2將構(gòu)成一個最優(yōu)決策序列最優(yōu)性原理成立。 反證：若不然，設v2,q

10、3,qk-1,t是一條由v2到t的更短的路徑，則s, v2,q3,qk-1,t將是比s,v2,v3,vk-1,t更短的從s到t的路徑。與假設矛盾。 故，最優(yōu)性原理成立即，是v2 v3,.,vk-1t構(gòu)成從v2至t的最短路徑4. 最優(yōu)決策序列的表示 設 S0：問題的初始狀態(tài) n次決策：問題需要做n次決策 xi：i階段的決策值，1in。 設X1=r1,1,r1,2,r1,p1是x1可選決策值的集合，S1,j1是在選擇決策值r1,j1之后所產(chǎn)生的狀態(tài)“初始決策”所產(chǎn)生的狀態(tài)。 設1,j1是相應于狀態(tài)S1,j1的最優(yōu)決策序列。則，相應于S0的最優(yōu)決策序列就是r1,j11,j1|1j1p1中最優(yōu)的序列，

11、記為 就一個特定的r1,j1而言s0r1,1r1,2.r1,p1sn1,j11,11,21p1 若已經(jīng)做了k-1次決策，1k-1n，設x1,x2,xk-1的最優(yōu)決策值是r1,r2,rk-1，所產(chǎn)生的狀態(tài)依次為S1,S2,Sk-1。 設Xk=rk,1,rk,2,rk,pk是xk可能的決策值的集合，Sk,jk是在選擇決策值rk,jk之后所產(chǎn)生的狀態(tài), 1jkpk。 k,jk是相應于狀態(tài)Sk,jk的最優(yōu)決策序列。則，相應于Sk-1的最優(yōu)決策序列是 相應于S0的最優(yōu)決策序列為r1,rk-1，rk, k就一個特定的rk,jk而言s0 s1 s2. sk-1rk,1rk,2.rk,pksnk,jkk,1k

12、,2kpk2. 向前處理策略求解 設 P(i,j)是一條從Vi中的結(jié)點j到匯點t的最小成本路徑， COST(i,j)是這條路徑的成本。 1) 向前遞推式 2) 遞推過程 第k-1段 c(j,t) E COST(k-1,j) = l1l2.lpi+1tjViVi+112345678910111297324227111181456356425V1V2V3V4V55段圖各遞推結(jié)果第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5第3段 COST(3,6) = min6+COST(4,9),5+

13、COST(4,10) = 7 COST(3,7) = min4+COST(4,9),3+COST(4,10) = 5 COST(3,8) = min5+COST(4,10),6+COST(4,11) = 7第2段 COST(2,2) = min4+COST(3,6) , 2+COST(3,7), 1+COST(3,8) = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15第1段 COST(1,1) = min9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5) = 16S到t的最小成本路徑的成本 16 最小成

14、本路徑的求取 記 D(i,j)每一COST(i,j)的決策 即，使c(j,l)+COST(i+1,l)取得最小值的l值。 例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8 D(1,1) = 2 根據(jù)D(1,1)的決策值向后遞推求取最小成本路徑： v2=D(1,1)=2 v3 = D(2,D(1,1) = 7 v4 = D(3,D(2,D(1,1) = D(3,7) = 10 故由s到t的最小成本路徑是：1271012 3) 算法描述 結(jié)點的編號規(guī)則 源點s編號為1,然后依次對V2

15、、V3Vk-1中的結(jié)點編號，匯點t編號為n。 目的：使對COST和D的計算僅按n-1,n-2,1的次序計算即可，無需考慮標示結(jié)點所在段的第一個下標。 算法描述算法7.1 多段圖的向前處理算法 procedure FGRAPH(E,k,n,P) /輸入是按段的順序給結(jié)點編號的，有n個結(jié)點的k段圖。E是邊 集，c(i,j)是邊的成本。P(1:k)帶出最小成本路徑/ real COST(n); integer D(n-1),P(k),r,j,k,n COST(n)0 for jn-1 to 1 by -1 do /計算COST(j)/ 設r是具有性質(zhì)：E且使c(j,r)+COST(r)取最小值的結(jié)點

16、 COST(j)c(j,r) + COST(r) D(j) r /記錄決策值/ repeat P(1)1; P(k)n for j2 to k-1 do /找路徑上的第j個結(jié)點/ P(j) D(P(j-1) /回溯求出該路徑/ repeat end FGRAPH算法的時間復雜度 若G采用鄰接表表示，總計算時間為：3. 向后處理策略求解 設 BP(i,j)是一條從源點s到Vi中的結(jié)點j的最小成本路徑， BCOST(i,j)是這條路徑的成本。 1) 向后遞推式 2) 遞推過程 第2段 c(1,j) E COST(2,j) = 123456789101112973242271111814563564

17、25V1V2V3V4V55段圖各遞推結(jié)果第2段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2第3段 BCOST(3,6) = minBCOST(2,2)+4,BCOST(2,3)+2 = 9 BCOST(3,7) = minBCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11 = 11 BCOST(3,8) = minBCOST(2,4)+11, BCOST(2,5)+8 = 10第4段 BCOST(4,9) = minBCOST(3,6)+6,BCOST(3,7)+4 = 15 BCOST(

18、4,10) = minBCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5 = 14 BCOST(4,11) = minBCOST(3,8)+6 = 16第5段 BCOST(5,12) = minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5 = 16S到t的最小成本路徑的成本 16 最小成本路徑的求取 記 BD(i,j)每一COST(i,j)的決策 即，使COST(i-1,l)+c(l,j)取得最小值的l值。 例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5 BD(4,9) = 6, BD(4,10)

19、= 7, BD(4,11) = 8 BD(5,12) = 10 根據(jù)D(5,12)的決策值向前遞推求取最小成本路徑： v4 = BD(5,12)=10 v3 = BD(4,BD(5,12) = 7 v2 = BD(3,BD(4,BD(5,12) = BD(3,7) = 2 故由s到t的最小成本路徑是：1271012 算法7.2 多段圖的向后處理算法 procedure BGRAPH(E,k,n,P) /輸入是按段的順序給結(jié)點編號的，有n個結(jié)點的k段圖。E是邊 集，c(i,j)是邊的成本。P(1:k)帶出最小成本路徑/ real BCOST(n); integer BD(n-1),P(k),r,

20、j,k,n BCOST(1)0 for j2 to n do /計算BCOST(j)/ 設r是具有E且使BCOST(r)+ c(r,j)取最小值性質(zhì)的結(jié)點 BCOST(j) BCOST(r)+ c(r,j) BD(j) r /記錄決策值/ repeat P(1)1; P(k)n for jk-1 to 2 by -1 do /找路徑上的第j個結(jié)點/ P(j) D(P(j+1) /回溯求出該路徑/ repeat end BGRAPH4. 多段圖問題的應用實例資源的分配問題 將n個資源分配給r個項目的問題：如果把j個資源，0jn，分配給項目i，可以獲得N(i,j)的凈利。 問題：如何將這n個資源分

21、配給r個項目才能使各項目獲得的凈利之和達到最大。 轉(zhuǎn)換成一個多段圖問題求解。 用r1段圖描述該問題： 段： 1到r之間的每個段i表示項目i。 結(jié)點： i=1時，只有一個結(jié)點源點s =V(1,0) 當2ir時，每段有n+1個結(jié)點，每個結(jié)點具有形式 V(i,j)：表示到項目i之前為止，共把j個資源分配給了 前i-1個項目，j=0,1,n。 匯點t=V(r+1,n) 邊的一般形式：,jl,1ir 成本： 當jl且1ir時，邊賦予成本 N(i,l-j),表示給項目i分配l-j個資源所可能獲得的凈利。 當jn且i=r時，此時的邊為：,該邊賦 予成本：指向匯點的邊注，并不是分給的資源越多，得到的凈利就越大

22、實例：將4個資源分配給3個項目。構(gòu)成一個4段圖。 問題的解：資源的最優(yōu)分配方案由一條s到t的最大成本路徑給出改變邊成本的符號，從而將問題轉(zhuǎn)換成為求取最小成本路徑問題。7.2 最大子段和問題描述：給定由n個整數(shù)（包含負整數(shù)）組成的序列a1,a2,.,an，求該序列子段和的最大值。當所有整數(shù)均為負值時定義其最大子段和為0。依此定義，所求的最優(yōu)值為： 例如，當(a1,a2, a3, a4, a5,a6)=(-2,11,-4,13,-5,-2)時，最大子段和為： 1. 一個簡單算法一個簡單算法：int MaxSum(int n, a, &besti, &bestj)int sum=0;for(i=1;

23、i=n;i+)for(j=1;j=n;j+)int thissum=0;for(k=i;ksum)sum=thissum;besti=i;Bestj=j;return sum;算法有3重循環(huán)，復雜性為O(n3)。由于有：算法可作如下改進：int MaxSum(int n, a, &besti, &bestj)int sum=0;for(i=1;i=n;i+)int thissum=0;for(j=1;jsum)sum=thissum;besti=i;bestj=j;改進后的算法復雜性為O(n2) 。2. 分治方法求解從問題的解的結(jié)構(gòu)可以看出，它適合于用分治策略求解：如果將所給的序列a1:n分為

24、長度相等的兩段a1:n/1和an/2+1:n，分別求出這兩段的最大子段和，則a1:n的最大子段和有三種情形：a1:n的最大子段和與a1:n/2的最大子段和相同；a1:n的最大子段和與an/2+1:n的最大子段和相同；a1:n的最大子段和為下面的形式。A、B這兩種情形可遞歸求得。對于情形C，容易看出，an/2與an/2+1在最優(yōu)子序列中。因此，我們可以在a1:n/2和an/2+1:n中分別計算出如下的s1和s2。則s1+s2即為出現(xiàn)情形C使得最優(yōu)值。 從而設計出下面所示的分治算法。int MaxSubSum(int a, int left, int right) int sum=0; if (l

25、eft=right)sum=aleft0?aleft:0; elseint center=(left+right)/2; int leftsum=MaxSubSum(a,left,center); int rightsum=MaxSubSum(a,center+1,right); int s1=0;lefts=0; for (int i=center;i=left;i-) lefts+=ai; if (leftss1) s1=lefts; int s2=0;rights=0; for (int i=center+1;is2) s2=rights; sum=s1+s2; if (sumlefts

26、um) sum=leftsum; if (sum0時bj=bj-1+aj，否則bj=aj。由此可得計算bj的動態(tài)規(guī)劃遞歸式bj=maxbj-1+aj，aj，1jn。據(jù)此，可設計出求最大子段和的動態(tài)規(guī)劃算法如下：int MaxSum(int n, int a)int sum=0; b=0;for (i=1;i0) b+=ai; else b=ai;if (bsum) sum=b;return sum;顯然該算法的計算時間為O(n)。4. 算法的推廣最大矩陣和問題，略最大m子段和問題，略7.3 每對結(jié)點之間的最短路徑1. 問題描述 設G=(V,E)是一個有n個結(jié)點的有向圖，C是G的成本鄰接矩陣，C

27、中元素有： 0 ，i j c(i,j)= 邊的成本，ij且E(G) ，ij且 其中，1i，jn 每對結(jié)點之間的最短路徑問題：求滿足下述條件的矩陣A，A中的任一元素A(i,j)代表結(jié)點i到結(jié)點j的最短路徑長度。分析： 利用單源最短路徑算法求解 計算n個結(jié)點的單源最短路徑。 時間復雜度：(n3)利用動態(tài)規(guī)劃策略求解 將求解G中每對結(jié)點之間的最短路徑問題轉(zhuǎn)化成一個多階段決策過程。 決策什么？ 最優(yōu)性原理對于該問題是否成立？2. 動態(tài)規(guī)劃求解策略1）最優(yōu)性原理對于每對結(jié)點之間的最短路徑問題成立 對G的一條由i到j的最短路徑（假設該路徑中不包含環(huán)），設k是該路徑上的一個中間結(jié)點： i,.,k,j 由i到

28、k的最短路徑 k是中間結(jié)點 由k到i的最短路徑 則，由i到k和k到j的兩條子路徑將分別是由i到k和由k到j的最短路徑。（反證，否則i,.,k,j也將不是由i到j的最短路徑） 故，最優(yōu)性原理對于該問題成立。2）多階段決策過程 所有n個結(jié)點從1到n依次編號。 設k是由i到j的最短路徑上編號最高的中間結(jié)點： i,.,k,j k是編號最高的中間結(jié)點 則由i到k的子路徑上將不會有比編號k-1更大的結(jié)點；同理，由k到j的子路徑上也將不會有比編號k-1更大的結(jié)點。 構(gòu)造多階段決策過程：對由i到j的最短路徑，首先決策哪一個結(jié)點是該路徑上具有最大編號的中間結(jié)點k，然后再去求取由i到k和由k到j的最短路徑其中應不

29、包含比k-1還大的中間結(jié)點。3）遞推關系式 記Ak(i,j)表示從i到j并且不經(jīng)過比k還大的結(jié)點的最短路徑長度。則， A(i,j) = An(i,j) 即，由i到j的最短路徑不通過編號比n還大的結(jié)點。 注：該路徑可以經(jīng)過結(jié)點n，也可以不經(jīng)過結(jié)點n。 若該路徑經(jīng)過結(jié)點n，則 An(i,j) An-1(i,n) + An-1(n,j) 若該路徑不經(jīng)過結(jié)點n，則 An(i,j) An-1(i,j) 故可得， An(i,j) = minAn-1(i,j) ，An-1(i,n) + An-1(n,j) 不經(jīng)過n結(jié)點 經(jīng)過n結(jié)點 對任意的k， k1，有， Ak(i,j) = minAk-1(i,j) ，A

30、k-1(i,k) + Ak-1(k,j) 不經(jīng)過結(jié)點k 剛好經(jīng)過結(jié)點k 初值： A0(i,j)= C(i,j)，1in，1jn遞推計算： A1(i,j), A2(i,j), An(i,j)= A (i,j)3. 算法描述算法7.3 每對結(jié)點之間的最短路徑長度 procedure ALL-PATHS(COST,A,n) /COST(n,n)是n結(jié)點圖的成本鄰接矩陣；A(i,j)是結(jié)點vi到vj的最短路 徑的成本；COST(i,i)=0,1in/ integer I,j,k,n; real COST(n,n),A(n,n) for i1 to n do for j1 to n do A(i,j)

31、COST(i,j) /用COST(i,j)對A0賦初值/ repeat repeat for k1 to n do for i1 to n do for j1 to n do A (i,j) minA (i,j) ，A (i,k) + A (k,j) repeat repeat repeat end ALL-PATHS算法的設計說明1） Ak(i,k) = Ak-1(i,k) Ak(k,j) = Ak-1(k,j) (i,j)(i,k)(k,j)(k,k)ik且kj,則有Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak-1(k,j) 在第i-1到第i次的迭代過程中，A的第k

32、行、第k列元素不變ki且jk,則有Ak(i,j) minAk-1(i,j), Ak-1(i,k) + Ak(k,j) (k,k)(k,j)(i,k)(i,j)(k,j)(k,k)(i,j)(i,k)ki且kj,則有Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak(k,j) Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak-1(k,j) Ak(i,j) minAk-1(i,j), Ak-1(i,k) + Ak(k,j) Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak(k,j) Ak(i,j) minAk-1(i,j), Ak-1(i,

33、k) + Ak-1(k,j) 在算法的計算過程中取消了A的上標，并保證了每次計算 的 Ak(i,j)即為 minAk-1(i,j), Ak-1(i,k) + Ak-1(k,j) 2）如何求每對結(jié)點之間的路徑？例7.3 有向圖如圖所示A0123104112602330A11231041126023370A2123104626023370A3123104625023370642 113v1v2v3123104112602330求圖中所有結(jié)點間最短路徑的成本矩陣注： A(i,j) = 表明G中從i到j沒有有向路徑性能分析 計算時間 注：該時間與A的值無關： for k1 to n do 迭代n次 f

34、or i1 to n do 迭代n次 for j1 to n do 迭代n次 A (i,j) minA (i,j) ，A (i,k) + A (k,j) repeat repeat repeat7.4 矩陣連乘問題給定n個矩陣A1,A2,.,An，其中Ai與Ai+1是可乘的，i=1,2,.,n-1。考察這n個矩陣的連乘積A1A2.An。由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調(diào)用2個矩陣相乘的標準算法計算出矩陣連乘積。7.4 矩陣連乘問題完全加括

35、號的矩陣連乘積可遞歸地定義為：單個矩陣是完全加括號的；矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)。7.4矩陣連乘問題設有四個矩陣A,B,C,D，它們的維數(shù)分別是：A=5010，B=1040，C=4030，D=305總共有五種完全加括號的方式：(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)其數(shù)乘次數(shù)分別為：16000, 10500, 36000, 87500, 345007.4 .1 窮舉搜索法問題描述：給定n個矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1，2，n-1。如何確定計算矩

36、陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。窮舉法：列舉出所有可能的計算次序，并計算出每一種計算次序相應需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。 7.4.1 窮舉搜索法算法復雜度分析：對于n個矩陣的連乘積，設其不同的計算次序為P(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1.Ak)(Ak+1An)可以得到關于P(n)的遞推式如下： P(n)是隨n的增長成指數(shù)增長的。動態(tài)規(guī)劃法1.分析最優(yōu)解的結(jié)構(gòu)預處理：將矩陣連乘積A1A2.An簡記為Ai:j，這里ij?？疾煊嬎鉇i:j的最優(yōu)計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i

37、kj，則其相應完全加括號方式為（A1A2. Ak）（Ak+1 Ak+2. An ）。計算量：Ai:k的計算量加上Ak+1:j的計算量，再加上Ai:k和Ak+1:j相乘的計算量。動態(tài)規(guī)劃法1.分析最優(yōu)解的結(jié)構(gòu)分析最優(yōu)解的結(jié)構(gòu)特征：計算Ai:j的最優(yōu)次序所包含的計算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。2.建立遞歸關系設計算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n。當i=j時，Ai:j=Ai，因此，mi,i=0，

38、i=1,2,n。當ij時，mi,j=mi,k+mk+1,j+pi-1pkpj，這里Ai的維數(shù)為pi-1pi?？梢赃f歸地定義mi,j為： k的位置只有j-1種可能。3.計算最優(yōu)值對于1ijn不同的有序?qū)?i,j)對應于不同的子問題。因此，不同子問題的個數(shù)最多只有在遞歸計算時，許多子問題被重復計算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進行計算。在計算過程中，保存已解決的子問題答案。每個子問題只計算一次，而在后面需要時只要簡單查一下，從而避免大量的重復計算，最終得到多項式時間的算法。7.3.3矩陣連乘算法算法描述【程序73】矩陣連

39、乘算法class MatrixChainpublic: MatrixChain(int mSize,int *q); int MChain(); int LookupChain(); void Traceback(); private: void Traceback(int i,int j); int LookupChain(int i, int j); int *p,*m,*s,n; int MatrixChain:MChain() /求A0:n-1的最優(yōu)解值 for (int i=0;in;i+) mii=0; for (int r=2; r=n;r+) for (int i=0;i=n-

40、r;i+) int j=i+r-1; mij=mi+1j+pi*pi+1*pj+1; sij=i; for (int k=i+1;kj;k+) int t=mik +mk+1j+pi*pk+1*pj+1; if (tmij) mij=t;sij=k; return m0n-1;void MatrixChain:Traceback(int i,int j) if(i=j) coutAi;return; if (isij) cout(; Traceback(i,sij);if (isij)cout); if(sij+1j)cout(; Traceback(sij+1,j);if(sij+1j) c

41、out);void MatrixChain:Traceback() cout(; Traceback(0,n-1);cout); cout 0) return mij;if (i = j) return 0;int u = LookupChain(i，i) + LookupChain(i+1，j) + pi-1*pi*pj;sij = i;for (int k = i+1; k j; k+) int t = LookupChain(i，k) + LookupChain(k+1，j) + pi-1*pk*pj;if (t u) u = t; sij = k;mij = u;return u;算法

42、復雜性：T(n)=O(n3)關于動態(tài)規(guī)劃算法和備忘錄方法的適用條件矩陣連乘積的最優(yōu)計算次序問題可用自頂向下的備忘錄方法或自底向上的動態(tài)規(guī)劃算法在O(n3)計算時間內(nèi)求解。這兩個算法都利用了子問題重疊性質(zhì)?？偣灿?n2)個不同的子問題，對每個子問題兩種算法都只解一次并記錄答案。當再次遇到該子問題時，簡單地取用已得到的答案，節(jié)省了計算量，提高了算法的效率。關于動態(tài)規(guī)劃算法和備忘錄方法的適用條件適用條件：一般來說，當一個問題的所有子問題都至少要解一次時，用動態(tài)規(guī)劃算法比用備忘錄方法好。此時，動態(tài)規(guī)劃算法沒有任何多余的計算，還可以利用其規(guī)則的表格存取方式來減少在動態(tài)規(guī)劃算法中的計算時間和空間需求。當子

43、問題空間中部分子問題可以不必求解時，易用備忘錄方法則較為有利，因為從其控制結(jié)構(gòu)可以看出，該方法只解那些確實需要求解的子問題。7.5 Longest Common Susequence 問題的定義 最長公共子序列 (LCS) 結(jié)構(gòu)分析 建立求解LCS長度的遞歸方程 自底向上LCS長度的計算 構(gòu)造優(yōu)化解定義：若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk，是X的子序列是指存在一個嚴格遞增下標序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相應的遞增下標序列為2，3，5，7。給定2個序列X和Y，

44、當另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列。給定2個序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最長公共子序列。 最長公共子序列（LCS）問題輸入：X = (x1,x2,.,xn)，Y = (y1,y2,.ym)輸出：Z = X與Y的最長公共子序列最長公共子序列結(jié)構(gòu)分析第i前綴設X=(x1, x2, ., xn)是一個序列，X的第i前綴Xi是一個序列，定義為Xi=(x1, ., xi ) 例. X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D)優(yōu)化子結(jié)構(gòu)定理1（優(yōu)化子結(jié)構(gòu)）設X=(x1, ., xm

45、)、Y=(y1, ., yn)是兩個序列，Z=(z1, ., zk)是X與Y的LCS，我們有： 如果xm=yn, 則zk=xm=yn, Zk-1是Xm-1和Yn-1的LCS， 即，LCSXY = LCSXm-1Yn-1+ . 如果xmyn，且zkxm，則Z是Xm-1和Y的LCS，即LCSXY= LCSXm-1Y 如果xmyn,且zkyn,則Z是X與Yn-1的LCS，即LCSXY= LCSXYn-1最長公共子序列的結(jié)構(gòu)設序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則若xm=yn，則zk=xm=yn，且zk-1是xm-1和yn-1的最長公共子序列。若xm

46、yn且zkxm，則Z是xm-1和Y的最長公共子序列。若xmyn且zkyn，則Z是X和yn-1的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 證明: . X=, Y=，則 LCSXY = LCSXm-1Yn-1+ . 設zkxm，則可加xm=yn到Z，得到一個長為k+1的X與Y的公共序列，與Z是X和Y的LCS矛盾。于是zk=xm=yn。 現(xiàn)在證明Zk-1是Xm-1與Yn-1的LCS。顯然Zk-1是Xm-1與Yn-1的公共序列。我們需要證明Zk-1是LCS。 設不然，則存在Xm-1與Yn-1的公共子序列W，W

47、的長大于k-1。增加xm=yn到W，我們得到一個長大于k的X與Y的公共序列，與Z是LCS矛盾。于是，Zk-1是Xm-1與Yn-1的LCS. X=, Y=，xmyn，zkxm，則 LCSXY= LCSXm-1Y 由于zkxm，Z是Xm-1與Y的公共子序列。我們來證Z是Xm-1與Y的LCS。設Xm-1與Y有一個公共子序列W，W的長大于k, 則W也是X與Y 的公共子序列，與Z是LCS矛盾。 同可證。子問題的遞歸結(jié)構(gòu)由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當i=0或j=0時，空序列

48、是Xi和Yj的最長公共子序列。故此時Cij=0。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關系如下： 計算最優(yōu)值由于在所考慮的子問題空間中，總共有(mn)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j;for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i = 0;for (i = 1; i = m; i+)for (j = 1; j =cij-1) cij=ci-1j; bij=

49、2;else cij=cij-1; bij=3; 構(gòu)造最長公共子序列算法描述：void LCS(int i，int j，char *x，int *b)if (i =0 | j=0) return;if (bij= 1) LCS(i-1，j-1，x，b); coutT01(左子樹），T24(右子樹） T01=1 =T00(左子樹），T11(右子樹） T24=3 =T22(左子樹），T34(右子樹） T34=4 =T33(左子樹），T44(右子樹） 0123402,0,03,0,01,0,01,0,01,0,018,8,17,7,23,3,33,3,4212,19,19,12,25,8,3316,

50、25,211,19,2416,32,2W(j,j+i),C(j,j+i),R(j,j+i)ji樹的形態(tài)ifdoreadwhile3.計算時間 當j-i=m時，有n-m+1個C(i,j)要計算 C(i,j)的計算：(m) 每個C(i,j)要求找出m個量中的最小值。 則，n-m+1個C(i,j)的計算時間： (nm-m2) 對所有可能的m，總計算時間為： 一種改進措施（克努特）：最優(yōu)的kR(i,j-1),R(i+1,j) Donald E. Knuth Optimum binary search trees Acta Information 1971 4.算法描述 procedure OBST(P

51、,Q,n) /給定n個標識符a1a2an。已知成功檢索的概率P(i),不成功檢索概率Q(i), 0in。算法對于標識符ai+1,aj計算最優(yōu)二分檢索樹Tij的成本C(i,j)、根R(i,j)、權(quán)W(i,j) / real P(1:n),Q(1:n),C(0:n,0:n),W(0:n,0:n);integer R(0:n,0:n) for i0 to n-1 do (W(i,i), R(i,i), C(i,i)(Q(i),0,0) /置初值/ (W(i,i+1), R(i,i+1), C(i,i+1)(Q(i)+Q(i+1)+P(i+1),i+1, Q(i)+Q(i+1)+P(i+1) repe

52、at /含有一個結(jié)點的最優(yōu)樹/ (W(n,n), R(n,n), C(n,n)(Q(n),0,0) for m2 to n do for i0 to n-m do ji+m W(i,j) W(i,j-1)+P(j)+Q(j) k區(qū)間R(i,j-1), R(i+1,j)中使C(i,l-1)+C(l,j)取最小值的l值 /Knuth結(jié)論/ C(i,j) W(i,j)+C(i,k-1)+C(k,j) R(i,j)k repeat repeat end OBSTOBST算法的計算時間:(n2)對滿足動態(tài)規(guī)劃最優(yōu)性原理的多階段決策問題有，當問題的一決策序列為最優(yōu)時，其中任何一段子序列相對于該子序列所對應

53、的子問題構(gòu)成該子問題的最優(yōu)解。但對有些多階段決策問題，盡管存在問題的最優(yōu)決策序列，但最優(yōu)性原理并不一定成立（從而也就不能用動態(tài)規(guī)劃策略求解）。試舉例說明。1. 問題描述 1) KNAP(1,j,X) 目標函數(shù)： 約束條件： 0/1背包問題：KNAP(1,n,M) 最優(yōu)性原理對于0/1背包問題成立 求解策略：向前遞推、向后遞推 7.7 0/1背包問題2) 向后遞推關系式 記fj(X)是KNAP(1,j,X)的最優(yōu)解，則fn(M)有 fn(M) = maxfn-1(M),fn-1(M-wn)+pn 對于任意的fi(X)，i0,有 fi(X) = maxfi-1(X),fi-1(X-wi)+pi 遞

54、推過程： 初始值 0 X0 f0= X0 求出fi在所有可能的X取值情況下的值。 fn(M)=KNAP(1,n,M)例7.11 背包問題 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 遞推計算過程 X0 f0(X)= 0 X0 X0 f1(X)= max0,+1=0 0X2 max0,0+1 = 1 X2 X0 max0,+3=0 0X2 f2(X)= max1,+3=1 2X3 max1,0+2=2 3X5 max1,1+2 = 3 X5 f3(M)= max3,1+5 = 6 M=6盡管X0,但還不足以裝下w1解向量的推導 f3(M)=6 x3

55、=1 P=6-p3=1 KNAP(1,3,6)=6 M=6-w3=2 X=(1,0,1) f2(M)=1 x2=0 f1(M)=1 x1=1 f1,f2,f3計算過程的圖解i:fi-1(x-wi) + pii=0:函數(shù)不存在1234567012i1:f0(x-w1) + p1x1234567012i2:f1(x-w2) + p23x1234567012f1(x)x1234567012f0(x)=0 x12345670123xf2(x)12345670678x1234589i3:f2(x-w3) + p312345670678x1234589f3(x)10注： fi-1(X-wi)+pi曲線的構(gòu)

56、造：將fi-1(X)的曲線在X軸上右移wi個單位，然后上移pi個單位而得到； fi(X)曲線的構(gòu)造：由fi-1(X) 和fi-1(X-wi)+pi的曲線按X相同時f取大值的規(guī)則歸并而成2. 序偶表示 記 fi的序偶集合為 Si = (Pj,Wj)|Wj是fi曲線中使得fi產(chǎn)生一次階躍的X值， 0jr 即Pj=fi(Wj)，r是階躍點個數(shù) (P0,W0)=(0,0) 若共有r個階躍值，則分別對應r個(Pj,Wj)序偶， 1jr 若WjWj+1,則PjPj+1，0jr 若WjXWj+1，fi(X)=fi(Wj) 若XWr，fi(X)=fi(Wr)fi是關于X的階躍函數(shù) Si的構(gòu)造 記 是fi-1(

57、X-wj)+pj的所有序偶的集合，則 其中，Si-1是fi-1的所有序偶的集合 Si的構(gòu)造：由Si-1和 按照支配規(guī)則合并而成。 支配規(guī)則：如果Si-1和 之一有序偶(Pj,Wj),另一有(Pk,Wk)， 且有 WjWk , Pj Pk， 則序偶(Pj,Wj)將被舍棄。 （即取最大值規(guī)則）。 注： Si中的序偶是背包問題KNAP(1,i,X)在X各種 取值下子問題的最優(yōu)解例7.12 例7.11的序偶計算 S0=(0,0) =(1,2) S1=(0,0),(1,2) =(2,3),(3,5) S2=(0,0),(1,2), (2,3),(3,5) =(5,4),(6,6), (7,7),(8,9

58、) S3=(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9) 注：序偶(3,5)被(5,4)“支配”而刪除KNAP(1,n,M)問題的解決策序列的求取 Sn是KNAP(1,n,X)在0XM各種取值下的最優(yōu)解 KNAP(1,n,M)的最優(yōu)解由Sn的最后一對有效序偶給出。xi的推導 xn: 設Sn的最后一對有效序偶是(P1,W1)，W1M，則 (P1,W1)或者是Sn1的最末一對序偶，或者是(Pj+pn,Wj+wn)， 其中 (Pj,Wj) Sn1且Wj是Sn1中滿足Wj+wnM的最大值。 若(P1,W1) Sn1，則Xn0；否則， (P1pn,W1-wn) S

59、n1 ，Xn1 xn-1: 若xn=0，則判斷(P1,W1) Sn2？，以確定Xn-1的值 若xn=1，則依據(jù)(P1pn,W1-wn) Sn2？，以判斷Xn-1的值 xn-2,x1將依次推導得出 例7.13 （例7.12) S0=(0,0) S1=(0,0),(1,2) S2=(0,0),(1,2), (2,3),(3,5) S3=(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9) M=6，f3(6)由S3中的序偶(6,6)給出。 1) (6,6) S2 x3=1 2) (6-p3,6-w3)=(1,2)S2且(1,2)S1 x2=0 3) (1,2) S0

60、 x1=1算法7.6 非形式的背包算法 procedure DKP(p,w,n,M) S0 (0,0) for i1 to n-1 do (P1,W1)|(P1-pi,W1-wi) Si-1 and W1M /生成 / Si MERGE-PURGE(Si-1, ) /將Si-1和 歸并為Si/ repeat (PX,WX) Sn-1的最末一個有效序偶 (PY,WY)(P1pn,W1+wn)，其中，W1是Sn-1中使得WwnM的所有序偶中取最大值得W /沿Sn-1, S1回溯確定xn,xn-1,x1的取值/ if PXPY then xn0 /PX將是Sn的最末序偶/ else xn1 /PY將