算法分析与设计 矩阵连乘问题

1、3.1矩阵连乘问题3.2动态规划算法的基本要素3.3最长公共子序列3.4 0-1背包问题本章主要知识点： 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。nT(n)=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) 如果能

2、够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。n给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,.,21nAAAiA1iA1,.,2 , 1ninAAA

3、.21（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 AABC)(BCAu完全加括号的矩阵连乘积可递归地定义为：每一种完全加括号对应于一个矩阵连乘积得计算次序，而矩阵连乘积的计算次序与其计算量有密切的关系。下面是计算两个矩阵乘积的标准算法：public static void matrixMultiply(double a, double b, double c, int ra, int ca, int rb, int cb) if(ca!=rb) throw new IllegalArgumentExcepti

4、on(“矩阵不可乘”); for( int i=0;ira;i+) for(int j=0;jcb;j+) int sum=ai0*b0j; for(int k=1;kca;k+) sum=sum+aik*bkj; cij=sum;设有四个矩阵 ，它们的维数分别是：DCBA , , ,1050A4010B3040C530D)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500通过矩阵乘积标准算法可知：若矩阵A是 矩阵，B是 矩阵，则乘积C=AB是 矩阵，总共需要 次数乘得到。pqqrprpqr这样可以计算每一种完全加括号方

5、式的计算量，如总共有五中完全加括号的方式 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2 ,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。 算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：P(n)是随n的增长呈指数增长。)/4()(11)()(1)(2/ 311

6、nnPnnknPkPnPnnku穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为Ai:j ，这里ij jiiAAA.1考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量 特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法

7、求解的显著特征。n设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n n当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,nn当ij时，n可以递归地定义mi,j为：jkipppjkmkimjim1, 1,这里 的维数为 iAiipp1jipppjkmkimjijimjki, 1,min0,1jki 的位置只有 种可能kij n对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有n由此可见，在递归计算时，许多子问题被重复计算多许多子问题被重复计算多次次。这也是该问题可用动态规划算法求解的又一显著特征。n用动态规划算法解此问

8、题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法)(22nnnpublic 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;

9、 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*pj; if (t mij) mij = t; sij = k; 算法复杂度分析：算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。A1A2A3A4A5A63035 3515 155 510 1020 20251137520

10、10350437555427125205351000262554 3213000201535250005322min52541531521pppmmpppmmpppmmm例如：4. 构造最优解算法matrixChain 记录了构造最优解所需的全部信息。sij=k表明计算矩阵链Ai:j的最佳方式在矩阵Ak和Ak+1之间断开，即最优的加括号方式为(Ai:k)(Ak+1:j)。因此，从s1n记录的信息可知计算A1:n的最优加括号方式为 (A1:s1n)(As1n+1:n)。而A1:s1n的最优加括号方式为(A1:s1s1n)(As1s1n+1:s1s1n)。 同理可以确定As1n+1:n的最优加括号

11、方式在ss1n+1n处断开。照此递推下去，最终可以得到A1:n的最优完全加括号方式，即构造出问题的一个最优解。下面算法traceback按算法matrixChain计算出的s输出计算Ai:j的最优计算次序：public static void traceback(int s,int i,int j) if(i=j) return; traceback(s,i,sij); traceback(s,sij+1,j); System.out.println(“Multiply A”+i+”,”+sij+”and A”+(sij+1)+”,”+j);要输出A1:n的最优计算次序只需调traceback

12、(s,1,n)即可。 给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2 ,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。动态规划动态规划考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为).)(.(211jkkkiiAAAAAA计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量将矩阵连乘积 简记为Ai:j ，这里ij jiiAAA.1public static void matrixChain(int p, int m, int

13、 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*pj; if (t mij) mij = t; sij = k; 从计算矩阵连乘积最优

14、计算次序的动态规划算法可以看出，动态规划算法的有效性依赖于问题本身的两个性质： 最优子结构性质最优子结构性质 子问题的重叠性质子问题的重叠性质从一般意义上，问题所具有的这两个性质是该问题可用动态规划算法求解的基本要素。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用

15、动态规划算法求解的前提。注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。 为了说明这一点,利用递归式直接计算Ai:j的递归算法如下：public static int recurMatrx

16、iChain(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;例如：备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。另外，备忘录方法的递归方式是自顶向下的，而动态规划算

17、法是自底向上递归的。public static int memoizedmatrixChain(int n) for (int i=1; i =n; i+) for(int j=i;j 0) return mij;/子问题已经被计算过 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,j) + pi-1*pk*pj; if (t u) u = t; sij = k;

18、 mij = u;/保存将子问题的解 return u; 算法复杂度分析：算法复杂度分析：备忘录算法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的子序列是指存在一个严格递增下标序列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，当另一序列Z既是X的子

19、序列又是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的最长公共子序列。的最长公共子序列。设序列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且zkyn，则Z是X和Yn-1的最长公共子序列。由此可见，2个序列的最长公共子

20、序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结最优子结构性质构性质。 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijicjicjicjic; 0,; 0,0, 01,1max1 110由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率

21、。 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=3;16: return cmn;public static void lc

22、s(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. 构造最长公共子序列构造最长公共子序列下面算法实现b的内容打印出Xi和Yj的最长公共子序列。在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助

23、于数组b而仅借助于c本身在O(1)时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。从计算矩阵连乘积最优计算次序的动态规划算法可以看出，动态规划算法的有效性依赖于问题本身的两个性质： 最优子结构性质最优子结构性质 子问题的重叠性质子问题的重叠性质从一般意义上，问题所具有的这两个性质是该问题可用动态规划算法求解的基本要素。备忘录方法的控制

24、结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。另外，备忘录方法的递归方式是自顶向下的，而动态规划算法是自底向上递归的。public static int memoizedmatrixChain(int n) for (int i=1; i =n; i+) for(int j=i;j 0) return mij;/子问题已经被计算过 if (i = j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j;

25、 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; 若给定序列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，当另一序列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的的最长公共子序列。最长公共子序列。niiixv1maxnixCxwiniii1,1 , 01给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，