2010-2011-2《算法分析》ppt-7动态规划--2

最长公共子序列LCSLongestCommonSubsequence两个一维事物比较：相似：LCS算法比较完全相等:一一对应，概率算法等相等部分相等:模式匹配--Horspool算法最长公共子序列：应用：打字比赛（规则，中外区别）SARS病毒文件比较等等两个一维事物的比较定义：与子串的区别算法：穷举法，动态规划法代码实现：用C•若给定序列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个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。穷举法:若要求两个序列X，Y的最长公共子序列，先取得X，Y的所有子序列，并进行一一比较，共有如下不同的组合：共要进行不同的比较：nnnnnmmmmmCCCCCC2...2...2121nm2最长公共子序列的结构我们用Xm表示{x1,x2,…,xm}Xm-1表示{x1,x2,…,xm-1}……X1表示{x1}同样可以定义Yn,Yn-1,…,Y1。最长公共子序列的结构设序列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的最长公共子序列。最长公共子序列的结构knkmnmknkmnmnmmnmnmkzyzxifYXLCSzyzxifYXLCSyxifxYXLCSYXLCSZYXLCSZ,,,,,,,,,,1111由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。最长公共子序列的结构子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用C[i][j]记录序列和的最长公共子序列的长度。其中，Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。其它情况下，由最优子结构性质可建立递归关系如下：jijiyxjiyxjijijiCjiCjiCjiC;0,;0,0,0]}][1[],1][[max{1]1][1[0]][[子问题的递归结构计算最长公共子序列的长度voidLCSLength(charx[],chary[],intm，intn){intC[m][n],i，j;for(i=0;i=m;i++)C[i][0]=0;for(i=0;i=n;i++)C[0][i]=0;for(i=1;i=m;i++)for(j=1;j=n;j++){if(x[i]==y[j])C[i][j]=C[i-1][j-1]+1;elseif(C[i-1][j]=C[i][j-1])C[i][j]=C[i-1][j];elseC[i][j]=C[i][j-1];returnC[m][n];}时间复杂度：由于在所考虑的子问题空间中，总共有θ(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。例子：填充表格ij012345601d2b3c4b5a6d7bbacdbd从表中找出最长公共子序列的方法：（1）从(m,n)到(0,0)（2）若当前格与左边一格相同，则画“”;若当前格与上边一格相同，则画“”;以上两者都不符合，从当前格到左上格画“”（3）从当前格向箭头方向前进一格，对此格进行（2）（4）从(m,n)到(0,0)的不同路径中，“”相对应的格的元素构成最长公共子序列。找出最长公共子序列ij01234560000000010000111d20111122b30112222c40112233b50122233a60122334d70122344bbacdbd（bcbd,bcdb,badb）求最长公共子序列voidLCS(chara[],intL[][],intm,intn){inti,j,k;charZ[m];i=m;j=n;k=m;do{if(C[i][j]==C[i-1][j])i--;elseif(C[i][j]==C[i]j-1])j--;else{Z[k]=a[i];k--;i--;j--;}}while(i0&&j0);printf(“%s”,Z+k+1);}时间复杂度为：m+n=O(n)求最长公共子序列算法的改进•如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算C[i][j]时，只用到数组C的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n))。•思考题：如何对程序进行改正，作为思考题。子串比较：Google.com等搜索工具的目的是从信息海洋中进行串匹配查找。最著名的子串匹配算法是KMP算法。KMP算法利用关键词内部的相似特点，节省了时间复杂度：O（m+n)数据结构中相关内容矩阵连乘积问题矩阵连乘积问题矩阵连乘积可定义为：给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。},...,,{21nAAAiA1iA1,...,2,1ninAAA...21矩阵连乘积问题若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。设有四个矩阵A,B,C,D，它们的维数分别是：A=50*10,B=10*40,C=40*30,D=30*5总共有五中完全加括号的方式(A((BC)D))(A(B(CD)))((AB)(CD))(((AB)C)D)((A(BC))D)16000,10500,36000,87500,34500回顾矩阵相乘：mlmmllnlnnllmnmmnnlmlnnmzzzzzzzzzyyyyyyyyyxxxxxxxxxZYX,...,,..................,...,,,...,,,...,,.....................,...,,,...,,,...,,...................,...,,,...,,212222111211212222111211212222111211nkjkkijibaz1,,,回顾矩阵相乘：单个乘法次数：n单个加法次数：n-1总的乘法次数：m*n*l总的加法次数：m*(n-1)*l矩阵连乘积问题给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。矩阵连乘积问题穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：穷举法复杂度分析：)/4()(11)()(1)(2/311nnfnnknfkfnfnnk动态规划将矩阵连乘积简记为A[i:j]，这里i≤j考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤kj，则其相应完全加括号方式为计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量jiiAAA...1)...)(...(211jkkkiiAAAAAA分析最优解的结构特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。建立递归关系设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]当i=j时，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n当ij时，jkipppjkmkimjim1],1[],[],[这里的维数为iAiipp1建立递归关系jipppjkmkimjijimjki}],1[],[{min0],[1jki可以递归地定义m[i,j]为：的位置只有种可能kij计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。)(22nnn计算最优值用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法举例：设有以下四个矩阵m12=35*40*20=28000m23=40*20*10=8000m34=20*10*15=3000m13=min{m12+35*20*10,m23+35*40*10}=min{28000+7000,8000+14000}=22000同样有：m24=14000m14=min{m24+35*40*15,m12+m34+35*20*15,m13+35*10*15}=min{14000+21000,28000+3000+10500,22000+5250}=min{35000,41500,27250}=27250最佳乘法顺序为:((A1(A2A3))A4)1510,41020,32040,24035,1,,,jijijijiaAaAaAaA用动态规划法求最优解的代码voidMatrixChain(int*p，intn，int**m，int**s){for(inti=1;i=n;i++)m[i][i]=0;for(intr=2;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。A1A2A3A4A5A63035351515551010202025