算法及設(shè)計A03_2

1、3.1矩陣連乘問題3.2動態(tài)規(guī)劃算法的基本要素3.3最長公共子序列3.4 0-1背包問題本章主要知識點： 給定n個矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1,2 ,n-1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少。動態(tài)規(guī)劃動態(tài)規(guī)劃考察計算Ai:j的最優(yōu)計算次序。設(shè)這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號方式為).)(.(211jkkkiiAAAAAA計算量：Ai:k的計算量加上Ak+1:j的計算量，再加上Ai:k和Ak+1:j相乘的計算量將矩陣連乘積 簡記為Ai:j ，這里ij jiiAAA.1public

2、 static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i = n; i+) mii = 0;/ i=j for (int r = 2; r = n; r+)/控制矩陣的鏈長度2n for (int i = 1; i = n - r+1; i+) /1=ij=n int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; /k=i sij = i; for (int k = i+1; k j; k+) / ikj int t = mik + mk+1j + pi-1*pk*p

3、j; if (t mij) mij = t; sij = k; 從計算矩陣連乘積最優(yōu)計算次序的動態(tài)規(guī)劃算法可以看出，動態(tài)規(guī)劃算法的有效性依賴于問題本身的兩個性質(zhì)： 最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 子問題的重疊性質(zhì)子問題的重疊性質(zhì)從一般意義上，問題所具有的這兩個性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的基本要素。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以

4、自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。注意：同一個問題可以有多種方式刻劃它的最優(yōu)子結(jié)構(gòu)，有些表示方法的求解速度更快（空間占用小，問題的維度低）遞歸算法求解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)子問題的重疊性質(zhì)。動態(tài)規(guī)劃算法，對每一個子問題只解一次，而后將其解保存在一個表格中，當(dāng)再次需要解此子問題時，只是簡單地用常數(shù)時間查看一下結(jié)果。 通常不同的子問題個數(shù)隨問題的大小呈多項式增長。因此用動態(tài)規(guī)劃算法只需要多項式時間，從而獲得較高的解題效率。 為了說明這一點,利用遞歸式直接

5、計算Ai:j的遞歸算法如下：public static int recurMatrxiChain(int I,int j) if(i=j) return 0; int u=recurMatrixChain(i+1,j)+pi-1*pi*pj; sij=i; for(int k=i+1;kj;k+) int t=recurMatrixChain(i,k)+recurMatrixChain(k+1,j)+pi-1*pk*pj; if(tu) u=t; sij=k; return u;例如：備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查

6、看，避免了相同子問題的重復(fù)求解。另外，備忘錄方法的遞歸方式是自頂向下的，而動態(tài)規(guī)劃算法是自底向上遞歸的。public static int memoizedmatrixChain(int n) for (int i=1; i =n; i+) for(int j=i;j 0) return mij;/子問題已經(jīng)被計算過 if (i = j) return 0; int u = 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

7、,j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u;/保存將子問題的解 return u; 算法復(fù)雜度分析：算法復(fù)雜度分析：備忘錄算法memoizedmatrixChain的耗時為O(n3)。事實上，共有O(n2)個備忘記錄項mij,i=1,2,n,j=1,2,n。每次填入時，不包括填入記錄的時間，共耗時O(n)。 若給定序列X=x1,x2,xm，則另一序列Z=z1,z2,zk是X的子序列是指存在一個嚴(yán)格遞增下標(biāo)序列i1,i2,ik使得對于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序

8、列，相應(yīng)的遞增下標(biāo)序列為2，3，5，7。 給定2個序列X和Y，當(dāng)另一序列Z既是X的子序列又是Y的子序列時，稱Z是序列X和Y的公共子序列公共子序列。 給定給定2 2個序列個序列X=xX=x1 1,x,x2 2,x,xm m 和和Y=yY=y1 1,y,y2 2,y,yn n ，找出，找出X X和和Y Y的最長公共子序列。的最長公共子序列。設(shè)序列X=x1,x2,xm和Y=y1,y2,yn的最長公共子序列為Z=z1,z2,zk ，則(1)若xm=yn，則zk=xm=yn，且Zk-1是Xm-1和Yn-1的最長公共子序列。(2)若xmyn且zkxm，則Z是Xm-1和Y的最長公共子序列。(3)若xmyn且

9、zkyn，則Z是X和Yn-1的最長公共子序列。由此可見，2個序列的最長公共子序列包含了這2個序列的前綴的最長公共子序列。因此，最長公共子序列問題具有最優(yōu)子結(jié)最優(yōu)子結(jié)構(gòu)性質(zhì)構(gòu)性質(zhì)。 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列和的最長公共子序列的長度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列。故此時Cij=0。其他情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由于在所考慮的子問題空間中，總共有(m

10、n)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 public static int lcsLength(char x,char y,int b)1: int m=x.length-1;2: int n=y.length-1;3: int c=new intm+1n+1;4: for(int i=1;i=m;i+) ci0=0; c0i=0;5: for (int i = 1; i = m; i+)6: for (int j = 1; j =cij-1) 11: cij=ci-1j;12: bij=2;13: else 14: cij=cij-1;15: bij=

11、3;16: return cmn;public static 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); System.out.print(xi); else if (bij= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); 4. 構(gòu)造最長公共子序列構(gòu)造最長公共子序列下面算法實現(xiàn)b的內(nèi)容打印出Xi和Yj的最長公共子序列。在算法lcsLength和lcs中，可進(jìn)一步將數(shù)組b省去。事實上，數(shù)組元素cij的值僅由ci-1j-1，ci-1j和cij-1這3個數(shù)組元素的值所確定。對于給定的數(shù)組元素cij，可以不