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

第3章 动态规划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)•如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法算法总体思想 动态规划基本步骤•找出最优解的性质，并刻划其结构特征•递归地定义最优值•以自底向上的方式计算出最优值•根据计算最优值时得到的信息，构造最优解3.1 矩阵连乘问题n给定n个矩阵￿￿￿￿￿￿￿￿￿￿￿￿￿￿，￿其中￿￿与￿￿￿￿￿是可乘的，￿￿￿￿￿￿￿￿￿￿￿￿￿。

考察这n个矩阵的连乘积￿￿￿￿￿￿￿￿￿￿n由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序这种计算次序可以用加括号的方式来确定n若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积完全加括号的矩阵连乘积（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即 u完全加括号的矩阵连乘积可递归地定义为：每一种完全加括号对应于一个矩阵连乘积得计算次序，而矩阵连乘积的计算次序与其计算量有密切的关系下面是计算两个矩阵乘积的标准算法：完全加括号的矩阵连乘积public static void matrixMultiply(double a[][], double b[][], double c[][], int ra, int ca, int rb, int cb){ if(ca!=rb) throw new IllegalArgumentException(“矩阵不可乘”); for( int i=0;i

这样可以计算每一种完全加括号方式的计算量，如总共有五中完全加括号的方式3.1 矩阵连乘问题 给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少u穷举法穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序 算法复杂度分析：算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：P(n)是随n的增长呈指数增长3.1 矩阵连乘问题u穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为A[i:j] ，这里i≤j 考察计算A[i:j]的最优计算次序设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k

•矩阵连乘计算次序问题的最优解包含着其子问题的最优解这种性质称为最优子结构性质最优子结构性质问题的最优子结构性质是该问题可用动态规划算法求解的显著特征2. 建立递归关系n设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] n当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,nn当i

循环体内的计算量为O(1)，而3重循环的总次数为O(n3)因此算法的计算时间上界为O(n3)算法所占用的空间显然为O(n2)例如：4. 构造最优解算法matrixChain 记录了构造最优解所需的全部信息s[i][j]=k表明计算矩阵链A[i:j]的最佳方式在矩阵Ak和Ak+1之间断开，即最优的加括号方式为(A[i:k])(A[k+1:j])因此，从s[1][n]记录的信息可知计算A[1:n]的最优加括号方式为 (A[1:s[1][n]])(A[s[1][n]+1:n])而A[1:s[1][n]]的最优加括号方式为(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]]) 同理可以确定A[s[1][n]+1:n]的最优加括号方式在s[s[1][n]+1][n]处断开照此递推下去，最终可以得到A[1:n]的最优完全加括号方式，即构造出问题的一个最优解下面算法traceback按算法matrixChain计算出的s输出计算A[i:j]的最优计算次序：public static void traceback(int s[][],int i,int j) { if(i==j) return; traceback(s,i,s[i][j]); traceback(s,s[i][j]+1,j); System.out.println(“Multiply A”+i+”,”+s[i][j]+”and A”+(s[i][j]+1)+”,”+j);}要输出A[1:n]的最优计算次序只需调traceback(s,1,n)即可。

3.1 矩阵连乘问题 给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少动态规划动态规划考察计算A[i:j]的最优计算次序设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤k

3.2 动态规划算法的基本要素一、最优子结构一、最优子结构•矩阵连乘计算次序问题的最优解包含着其子问题的最优解这种性质称为最优子结构性质最优子结构性质•在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾 •利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解最优子结构是问题能用动态规划算法求解的前提注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）二、重叠子问题二、重叠子问题•递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次这种性质称为子问题的重叠性质子问题的重叠性质•动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果 •通常不同的子问题个数随问题的大小呈多项式增长因此用动态规划算法只需要多项式时间，从而获得较高的解题效率 为了说明这一点,利用递归式直接计算A[i:j]的递归算法如下：public static int recurMatrxiChain(int I,int j){ if(i==j) return 0; int u=recurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(int k=i+1;k

另外，备忘录方法的递归方式是自顶向下的，而动态规划算法是自底向上递归的public static int memoizedmatrixChain(int n) { for (int i=1; i < =n; i++) for(int j=i;j<=n;j++) m[i][j]=0; return lookupChain(1,n); }其中，lookupChain()方法由下面函数给出•为了区分子问题未被计算过，首先初始化m[i][j]的值为0private static int lookupChain(int i, int j) { if (m[i][j] > 0) return m[i][j];//子问题已经被计算过 if (i == j) return 0; int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = 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] = u;//保存将子问题的解 return u; }算法复杂度分析：算法复杂度分析：备忘录算法memoizedmatrixChain的耗时为O(n3)。

事实上，共有O(n2)个备忘记录项m[i][j],i=1,2,…n,j=1,2,…,n每次填入时，不包括填入记录的时间，共耗时O(n)3.3 最长公共子序列•若给定序列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的最长公共子序列的最长公共子序列1. 最长公共子序列的结构设序列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)若xm≠yn且zk≠xm，则Z是Xm-1和Y的最长公共子序列3)若xm≠yn且zk≠yn，则Z是X和Yn-1的最长公共子序列由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列因此，最长公共子序列问题具有最优子结最优子结构性质构性质 2. 子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系用c[i][j]记录序列和的最长公共子序列的长度其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}当i=0或j=0时，空序列是Xi和Yj的最长公共子序列故此时C[i][j]=0其他情况下，由最优子结构性质可建立递归关系如下：3. 计算最优值由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率 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 int[m+1][n+1];4: for(int i=1;i<=m;i++) {c[i][0]=0; c[0][i]=0;}5: for (int i = 1; i <= m; i++)6: for (int j = 1; j <= n; j++) 7: if (x[i]==y[j]) {8: c[i][j]=c[i-1][j-1]+1;9: b[i][j]=1;}10: else if (c[i-1][j]>=c[i][j-1]) {11: c[i][j]=c[i-1][j];12: b[i][j]=2;}13: else {14: c[i][j]=c[i][j-1];15: b[i][j]=3;}}16: return c[m][n];}public static void lcs(int i,int j,char [] x,int [][] b) { if (i ==0 || j==0) return; if (b[i][j]== 1){ lcs(i-1,j-1,x,b); System.out.print(x[i]); } else if (b[i][j]== 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); }4. 构造最长公共子序列构造最长公共子序列下面算法实现b的内容打印出Xi和Yj的最长公共子序列。

5. 算法的改进•在算法lcsLength和lcs中，可进一步将数组b省去事实上，数组元素c[i][j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]这3个数组元素的值所确定对于给定的数组元素c[i][j]，可以不借助于数组b而仅借助于c本身在O(1)时间内确定c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个值所确定的•如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行因此，用2行的数组空间就可以计算出最长公共子序列的长度进一步的分析还可将空间需求减至O(min(m,n))3.2 动态规划算法的基本要素从计算矩阵连乘积最优计算次序的动态规划算法可以看出，动态规划算法的有效性依赖于问题本身的两个性质：• 最优子结构性质最优子结构性质• 子问题的重叠性质子问题的重叠性质从一般意义上，问题所具有的这两个性质是该问题可用动态规划算法求解的基本要素三、备忘录方法三、备忘录方法•备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。

另外，备忘录方法的递归方式是自顶向下的，而动态规划算法是自底向上递归的public static int memoizedmatrixChain(int n) { for (int i=1; i < =n; i++) for(int j=i;j<=n;j++) m[i][j]=0; return lookupChain(1,n); }其中，lookupChain()方法由下面函数给出•为了区分子问题未被计算过，首先初始化m[i][j]的值为0private static int lookupChain(int i, int j) { if (m[i][j] > 0) return m[i][j];//子问题已经被计算过 if (i == j) return 0; int u = lookupChain(i+1,j) + p[i-1]*p[i]*p[j]; s[i][j] = i; for (int k = i+1; k < j; k++) { int t = 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] = u;//保存将子问题的解 return u; }3.3 最长公共子序列•若给定序列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的最的最长公共子序列长公共子序列3.4 0-1背包问题给定n种物品和一背包物品i的重量是wi，其价值为vi，背包的容量为C问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题1. 最优子结构性质设(y1,y2,…,yn)是所给0-1背包问题的一个最优解，则(y2,…,yn)是下面相应子问题的一个最优解2. 递归关系设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下3. 算法描述•当 为正整数时，用二维数组m[][]存储m(i,j)的相应值，可设计解0-1背包问题的动态规划算法如下：public static void knapsack(int []v,int []w,int c,int [][]m){ int n=v.length-1; int jMax=Math.min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i--){//可以改写为for(int i=n-1;i>=1;i--) jMax=Math.min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=Math.max(m[i+1][j],m[i+1][j-w[i]]+v[i]);} m[1][c]m[2][c];//可以省略 if(c>=w[1])//可以省略 m[1][c]=Math.max(m[1][c],m[2][c-w[1]]+v[1]);//可以省略}算法复杂度分析：算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。

当背包容量c很大时，算法需要的计算时间较多例如，当c>2n时，算法需要Ω(n2n)计算时间 public static void traceback(int [][]m,int []w,int []x){ int n=w.length-1; for(int i=1;i0) x[n]=1; else x[n]=0;}。