Chapter4DynamicProgramming王子磊(Zilei: 理解動態(tài)規(guī)劃算法掌握動態(tài)規(guī)劃算法的基本最優(yōu)子結(jié)構(gòu)子問題性掌握設(shè)計動態(tài)規(guī)劃算找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)遞歸地定義最優(yōu)以自底向上的方式計算出最優(yōu)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)USTC矩陣連乘問最長公共子最大子段凸多邊形最優(yōu)三角多邊形圖像壓電路流水作業(yè)調(diào)背包問最優(yōu)二叉搜USTC=nUSTC=n=nUSTC=n=n T(n/4)T(n/4)T(n/4) USTCUSTCAA2個完全加括號的矩陣連乘積B和C的乘積并加括號，即設(shè)有四個矩陣A,B,C,D，它們的維數(shù)分別是： B=10x40C=40x30D=30x5 16000,10500,36000,87500,34500USTCn個矩陣{A1A2An}，其中AiAi+1i=1,2,n- 這n2個矩陣相乘USTCn個矩陣｛A1,A2,…,An｝AiAi+1nnP(n)(A1...Ak)(Ak+1…AnP(n))1Pn1)(4n/nUSTCAiAi+1…AjA[i:j計算A[i:j]的最優(yōu)計算次序：設(shè)這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，i≤k<j，則其相應(yīng)完全加括號方式為：(AiAi+1…Ak)(Ak+1Ak+2…Aj)計算量：計算量：A[i:kA[k+1:jA[i:kA[k+1:jUSTC特征A[i:jA[k+1:j矩陣連乘計算次序問題的最優(yōu)解包含著其子問題最優(yōu)USTC當i<j時，m[ijm[ikm[k+1,jpi-1pkAipi-1×m[i,j]m[i,j]min{m[i,k]m[k1,j]0i pp i這里，k的位置只有(j-iUSTC對于1≤i≤j≤n(ij n(n22這也是該問題可用動在計算過程每個子問題只計算一次，而在后面需要時只要簡單查一下，從避免大量的重復(fù)計USTCvoidMatrixChain(int*p，intn，int**m，int{for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)for(inti=1;i<=n-r+1;i++)m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++)intt=m[i][k]+m[k+1][j]+p[i-if(t<m[i][j]){m[i][j]=t;s[i][j]=}}}USTCm[2][5] m[2][2]m[3][5]pp 02500m[2][5] [2][3]m[4][5]pp 35520 m[2][4]m[5][5]pp 43750351020 算法matrixChain的主要計算量取決于算法中對r，i和k的3重循循環(huán)體內(nèi)的計算量為O(1)，而3重循環(huán)的總次數(shù)為O(n3)，因此算的計算時間上界為O(n3)；算法所占用的空間顯然為O(n2)USTC包含著其子問題的最優(yōu)解稱為在()利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的優(yōu)解逐步構(gòu)造出整個最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前同同一個問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)度更快（空間占用小，問題的維度低USTC 多次，這種性質(zhì)稱為 性動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表中，當再次需要解此通常不同的子問題個數(shù)隨問題的大小呈多項式增因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效USTC備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)intLookupChain(inti，int{if(m[i][j]>0)returnif(i==j)returnintu=LookupChain(i，i)+LookupChain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++)intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(t<u){u=t;s[i][j]=k;}}m[i][j]=return}USTCX={x1x2xm}Z={z1z2zk}，是X的子序列是指存在一個嚴格遞增下標序列{i1,i2,…,ik}使得對于所有j=1,2,…,k，有：zj=xij例如，序列={B，，D，B}X={，B，，，D，，B}的子序列，相應(yīng)的遞增下標序列為{2，3，，2個序列X和YZXY的子序列時，稱ZX和Y的2個序列X={x1,x2xm和Y={y1,y2yn}X和YUSTC????, =??(min??2??,??2??USTC獲取長度后再擴張算法以求解最長公共子序列X[1…i]和Y[1…j]X[1…m],Y[1…n]with(i=m,j=n)記錄求解每個子序列長度的狀態(tài)，用于推導(dǎo)USTCX={x1x2xm和Y={y1y2yn子序列為Z={z1,z2zkxm=ynzk=xm=ynZk-1是Xm-1和Yn-1xm≠ynzk≠xmZXm-1和Yxm≠ynzk≠ynZX和Yn-1由此可見，由此可見，2個序列的最長公共子序列包含了這2個序列的USTC用c[i][j]記錄序列和的最長公共子序列的長度，其中，Xi={x1x2xi}；Yj={y1y2yj}i=0j=0時，空序列是Xi和Yj的最長公共子序列，故此時c[i][j]=0；其它情 i0,jc[i][j] c[i1][j1]max{c[i][j1],c[i1][

i,j0;xiyi,j0;xiyUSTC由于在所考慮的子問題空間中，總共有由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，USTC由于在所考慮的子問題空間中，總共有θ(mn由于在所考慮的子問題空間中，總共有θ(mn)個不同的子問題，voidLCSLength(intm，intn，char*x，char*y，int**c，int**b){intfor(i=1;i<=m;i++)c[i][0]=for(i=1;i<=n;i++)c[0][i]=for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j])elseif(c[i-1][j]>=c[i][j-1])c[i][j]=c[i-1][j];else{c[i][j]=c[i][j-1];b[i][j]=3;}}voidLCS(inti，intj，char*x，int{if(i==0||j==0)if(b[i][j]==1){LCS(i-1，j-1，x，b);cout<<x[i];}elseif(b[i][j]==2)LCS(i-1，j，x，b);elseLCS(i，j-}USTClcsLengthlcs中，可進一步將數(shù)組b事實上，數(shù)組元素c[i][j]的值僅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]3個數(shù)組元素的值所確對于給定的數(shù)組元素c[i][j]，可以不借助于數(shù)b而僅借助于c本身在時間內(nèi)確c[i][j的值是由c[i-1][j-1]，c[i-1][jc[i][j-1]中哪用2行的數(shù)組空間就可以計算出最長公共子序列的長進一步的分析還可將空間需求減至USTC用多邊形頂點的逆時針序列表示凸多邊形，即P={v0v1vn-1表示具有nvivj2vivj稱為2個多邊形{vivi+1vj形的弦的集合TUSTCUSTC給定凸多邊形P

33

3 3

USTC一個表達式的完全加語法例如，完全加括號的矩陣連乘積((A1(A2A3))(A4(A5A6)))所相應(yīng)語法樹如圖(a)所凸多邊形{v0,v1,…vn-1}的三角剖分也可以用語法樹表例如，圖(b)中凸多邊形的三角剖分可用圖(a)所示的語法樹表矩陣連乘積中的每個矩陣Ai對應(yīng)于凸(n+1)邊形中的一條邊vi-三角剖分中的一條弦vivj，i<j，對應(yīng)于矩陣連乘積USTC事實上，若凸(n+1)邊形P={v0,v1,…,vn}的最優(yōu)三角剖T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個部分權(quán)的和：三角形v0vkvn的權(quán)、子多邊形{v0,v1,…,vk}和{vk,vk+1,…,vn可以斷言，由T2個子多邊形的三角剖分因為若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小權(quán)的三角剖USTCt[i][j]，1≤i<j≤n為凸子多邊形{vi-1,vi,…,vj的最優(yōu)三角為方便起見， 的多邊形{vi-1,vi} 值要計算的凸(n+1)邊形P的最優(yōu)權(quán)值為當j-i≥1時，凸子多邊形至少有3個頂點。由最優(yōu)子結(jié)構(gòu)性質(zhì)形其中i≤k≤j-由于在計算時還不知道k的確切位置，而k的所有可能位置只有j-i因此可以在這j-i個位置中選出使t[i][j]值達到最小的位USTCt[i][jtt[i][j]min{t[i][k]t[k1][j]0vv jii?? 2

=USTC多邊形游戲是一個單人玩的游戲，開始時有一個由n個運算符“+”或“*1n編號n-1選擇一條邊EE2v1用一個新的頂點取代邊E以及由E連接著的2個頂點v1和v2，將由頂點v1和v2的整數(shù)值通過邊E上的運算得到的結(jié)果USTC+??1(-+

??0

+??6×??5

??1+

??0,6+×

??5??2

??2 ×

(-1)

??4

??3(-1)

??4USTC的順時針鏈p(i，j)可表示為v[i]，op[i+1]，…，v[i+j-如果這條鏈的最后一次合并運算在op[i+s]處發(fā)生(1≤s≤j-1)，則在op[i+s處將鏈分割2個子p(i，sp(i+s，j-將圖轉(zhuǎn)換為

??3(-

??4 ??5 ??6

??0

??1(-

??2USTCm1是對子p(i，s的任意一種合并方式得到的值，而ab分中得到的最小值和最大值，依此定義有a≤m1≤b，c≤m2≤d(1)當op[i+s]=‘+’時，顯然有(2)當op[i+s]=‘*'時，有換句話說，主鏈的最大值和最USTCi 0≤pi≤255分割成m個連續(xù)段S1,S2,…,Sm。第i個象素段Si中i設(shè)t[il[k]iSiSi={pt[i]+1k設(shè)h

t[i]1k m如果限制1l[i]255，則需要用8位表示l[i]。因此，第i個象 空間為l[i]*b[i]+11位。按此格式 m列{p1,p2,…,pn}，需要l[i]*b[i]11m位 USTC圖像壓縮問題要求確定象素序列{p1,p2,…,pn}的最優(yōu)分段，使得依此分段所需的空間最少，每個分段的長度不超過256位？l[i]，b[i]，是{p1,p2,…,pn}l[i]，b[i]，是{pt[i]+1pt[i]+l[i]}的最優(yōu)分段USTC ] minik]k*ik)}bmax(i,j)logmax{p ik 算算法復(fù)雜度分析由于算法compressk的循環(huán)次數(shù)不超這256，故對每一個確定的可在時間O(1)內(nèi)完成的計算，因此整個算法所需的計算時間為USTC在一塊電路板的2端分別有n個接線柱，根據(jù)電路設(shè)計，要求用導(dǎo)線(i,π(i))將上端接線柱與下端接線柱相連，如圖所示。其中π(i){1,2,…,n}的一個排列，導(dǎo)線(i,π(i))稱為該電路板上的第i條連線。對于何1≤i<j≤ni條連線和第j條連線相交的充分必要條件 USTC記N(i,j)t|t,(tNets,ti,(t)j}，N(i,j)集為MNS(ij)，Size(ij)=|MNS(i當i=1

MNS(1,j)N(1,j)

j當i>1

jj<π(i)，此時，(i,(i))N(i,j)，故在這種情況下，N(i,j)=N(i-1,j)Size(ij)=Size(i-j≥π(i)，(i,π(i))∈MNS(i,j)，則對任意(t,π(t))∈MNS(i,j)有t<iπ(t)<π(i)。在這種情況下，MNS(i,j)-{(i,π(i))} N(i-1,π(i)-1)的大不相交子若(i,π(i?MNS(ij，則對任意(t,π(t∈MNS(ijt<i。從而MNS(i,j)N(i1,j)，因此，Size(i,j)≤Size(i-1,j)；另一方面MNS(i1,jN(i,j)，故又有Size(ij)≥Size(i-1從而Size(ij)=Size(i-1USTC(1)當i=1Size(1,j)jj(2)當i>1Size(i,j)max{Size(i1,j),Size(i1,(i)1)Size(i1,jjUSTCn個作業(yè){1，2，…，n}要在2臺機器M1M2組成的流水線上完成加工，每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1M2加工作i所需的時間分別為ai和bi。流水作業(yè)調(diào)度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成

USTC直觀上，一個最優(yōu)調(diào)度應(yīng)使機器M1沒有空閑時間，且機器M2的空閑時間最少N={1，2，…，n}，SNN的作在一般情況下，機器M1開始加工S中作業(yè)時，機器M2還在工其它作業(yè)，要等時間t后才可利將這種情況下完成S中作業(yè)所需的最短時間記為T(S流水作業(yè)調(diào)度問題的最優(yōu)值USTC設(shè)是所給n個流水作業(yè)的一個最優(yōu)調(diào)度，它所需的加工時a(1)+T’TM2b(1時，安排作業(yè)(2)，…，(n)所需的時間S=N-{(1)}T’=T(SS在機器M2的等待時間b(1情況下的一個最優(yōu)調(diào)’(2)，…，’(n)是N的一個調(diào)度，且該調(diào)度所需的時間為a(1)+T(S,<a(1)+T’，這與是N的最優(yōu)調(diào) 。故T’T(S,b(1))，從而b(1))。這就證明了流水作業(yè)調(diào)度問題具有最優(yōu)子結(jié)構(gòu)的性USTCT(N,0)min{aiT(N{i},biT(S,t)min{aiT(S{i},bimax{tai?? =?? USTC設(shè)SM2t時的任一最優(yōu)調(diào)度,若(1)=i,(2)=j，則由動態(tài)規(guī)劃遞歸式可得:T(S,t)=ai+T(S-{i},bi+max{t-ai,0})=ai+aj+T(S-ttbjmax{bimax{tai,0}ajbjbiajmax{max{tai,0},ajbjbiajmax{tai,ajbibjbiajaimax{t,aiajbi,ai}ijmin{bi,ajmin{bj,ai}iUSTCbjbiajaimax{t,aiajbi,ai}ijS的另一調(diào)度，它所需的加工時間為T’(S,t)=ai+aj+T(S-{i,j},tji)ttbjbiajaimax{t,aiajbj,ajij滿足Johnson不等式時，max{max{bi,aj}max{bj,aiaiajmax{bi,aj}aiajmax{bj,ai}max{aiajbi,ai}max{aiajbj,aj}max{t,aiajbi,ai}max{t,aiajbj,aj}USTC由此可見，ijJohnson不等式時，交換對于流水作業(yè)調(diào)度問題，必存在最優(yōu)調(diào)度(i(i+1)滿足JohnsonJohnsoni<jmin{min{b(i),a(j)}min{b(j),a(i)由此可知，所有滿足JohnsonUSTC令N1i|aibiN2i|ai將N1中作業(yè)依ai的非減序排序；將N2中作業(yè)依bi的非增序排序N1中作業(yè)接N2中作業(yè)構(gòu)成滿足Johnson法則的最優(yōu)調(diào)→證明：分三種情況O(nlogn)USTC給定n種物品和一背包，物品i的重量是wi，其價值為vi，背包的容量為C。問：應(yīng)如何選擇裝入背包的物品，使得裝入背nn1i USTCm(im(i，j的遞歸式容易看出，算法O(nc計算時間。當背c很大時，算法需要的計c>2n時，算法需Ω(n2n)的計算時m(i，j)，即m(i，j是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i，j)的遞歸式如下：m(i,j)

max{m(i1,j),m(i1,jwi)vi

jm(n,j)

m(i1,j0j

0jUSTC由m(i,j)的遞歸式容易證明，在一般情況下，對每一個確定的i(1≤i≤n)，函數(shù)m(i,j)是關(guān)于變量j的階梯狀單調(diào)不減函數(shù)，跳躍點是這一類函數(shù)的描述特征。在一般情況下，函數(shù)m(i,j)由對每一個確定的i(1≤i≤n)，用一個表p[i] 函數(shù)m(i,j)的全部跳躍點。表p[i]可依計算m(i,j)的遞歸式遞歸地由表p[i+1]計算，初始時p[n+1]={(0，0)}USTC

x

m(4,x-x

x(0,0)(2,1 x

m(3,x-3)+2xm(2,x-

(0,0)x

(3,2)(3,2)(0,0)x

(0,0)(2,x

xUSTC函數(shù)m(i,j)是由函數(shù)m(i+1,j)與函數(shù)m(i+1,j-wi)+vi作max運算得到的，因此，函數(shù)m(i,j)的全部跳躍點包含于函數(shù)m(i+1,j)的跳躍點集p[i+1]與函數(shù)m(i+1,j-wi)+vi的跳躍點集q[i+1]的并集中。易知，(s, 且僅當wisc且(s-wi,t-vi)p[i+1]。因此，容易由p[i+1]確定跳躍點集q[i+1]如下:q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)|(j,m(i,j))p[i+1]}另一方面，設(shè)(a，b)和(c，d)是p[i+1]q[i+1]中的2個跳躍點，則當ca且d<b時，(c，d)受控于(a，b)，從而(c，d)不是p[i]中的跳躍點。除受控跳躍點外，p[i+1]q[i+1]中的其它跳躍點均為p[i]中的跳躍點由此可見，在遞歸地由表p[i+1]計算表p[i]時，可先由p[i+1]計算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳躍點得到表USTC初始時p[6]={(0,0)}，(w5,v5)=(4,6)。因此q[5]=p[5](w4,v4)={(5,4),(