动态规划(一)最长公共子序列问题 LCS 总结

发布时间:2014-10-22 18:34:10编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"动态规划(一)最长公共子序列问题 LCS 总结",主要涉及到动态规划(一)最长公共子序列问题 LCS 总结方面的内容,对于动态规划(一)最长公共子序列问题 LCS 总结感兴趣的同学可以参考一下。

第一部分、什么是动态规划算法  Longest Common Sequence 动态规划一般也只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。 动态规划算法分以下4个步骤: 描述最优解的结构递归定义最优解的值按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础。由计算出的结果构造一个最优解。 //此步如果只要求计算最优解的值时,可省略。 好,接下来,咱们讨论适合采用动态规划方法的最优化问题的俩个要素:最优子结构性质,和子问题重叠性质。 最优子结构 如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。意思就是,总问题包含很多个子问题,而这些子问题的解也是最优的。 重叠子问题 子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。 第二部分、动态规划算法解LCS问题 2.0、LCS问题描述 56.最长公共子序列。 题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中, 则字符串一称之为字符串二的子串。 注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。 请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子序列,则输出它们的长度4,并打印任意一个子序列。 事实上,最长公共子序列问题也有最优子结构性质。 记: Xi=﹤x1,⋯,xi﹥即X序列的前i个字符 (1≤i≤m)(前缀) Yj=﹤y1,⋯,yj﹥即Y序列的前j个字符 (1≤j≤n)(前缀) 假定Z=﹤z1,⋯,zk﹥∈LCS(X , Y)。 若xm=yn(最后一个字符相同),则不难用反证法证明:该字符必是X与Y的任一最长公共子序列Z(设长度为k)的最后一个字符,即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。此时,问题化归成求Xm-1与Yn-1的LCS(LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1)。 若xm≠yn,则亦不难用反证法证明:要么Z∈LCS(Xm-1, Y),要么Z∈LCS(X , Yn-1)。由于zk≠xm与zk≠yn其中至少有一个必成立,若zk≠xm则有Z∈LCS(Xm-1 , Y),类似的,若zk≠yn 则有Z∈LCS(X , Yn-1)。此时,问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS。LCS(X , Y)的长度为:max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}。 由于上述当xm≠yn的情况中,求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度,这两个问题不是相互独立的:两者都需要求LCS(Xm-1,Yn-1)的长度。另外两个序列的LCS中包含了两个序列的前缀的LCS,故问题具有最优子结构性质考虑用动态规划法。 也就是说,解决这个LCS问题,你要求三个方面的东西: 1、LCS(Xm-1,Yn-1)+1; 2、LCS(Xm-1,Y),LCS(X,Yn-1); 3、max{LCS(Xm-1,Y),LCS(X,Yn-1)}。 2.1、最长公共子序列的结构 最长公共子序列的结构有如下表示: 设序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的一个最长公共子序列Z=<z1, z2, …, zk>,则: 若xm=yn,则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列;若xm≠yn且zk≠xm ,则Z是Xm-1和Y的最长公共子序列;若xm≠yn且zk≠yn ,则Z是X和Yn-1的最长公共子序列。 其中Xm-1=<x1, x2, …, xm-1>,Yn-1=<y1, y2, …, yn-1>,Zk-1=<z1, z2, …, zk-1>。 2.2、子问题的递归结构 由最长公共子序列问题的最优子结构性质可知,要找出X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列,可按以下方式递归地进行:当xm=yn时,找出Xm-1和Yn-1的最长公共子序列,然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时,必须解两个子问题,即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算X和Y的最长公共子序列时,可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题,即计算Xm-1和Yn-1的最长公共子序列。 与矩阵连乘积最优计算次序问题类似,我们来建立子问题的最优值的递归关系。用c[i,j]记录序列Xi和Yj的最长公共子序列的长度。其中Xi=<x1, x2, …, xi>,Yj=<y1, y2, …, yj>。当i=0或j=0时,空序列是Xi和Yj的最长公共子序列,故c[i,j]=0。其他情况下,由定理可建立递归关系如下: 2.3、计算最优值(LCS长度) 将上面C可以直接改为LCS()函数即可方便写出纯递归解法: 代码如下: #include<stdio.h> #include<string.h> using namespace std; #define N 1000 char a[N],b[N]; int lena,lenb; int LCS(int,int);///两个参数分别表示数组a的下标和数组b的下标 int main() { int n; scanf("%d",&n); while(n--) { scanf("%s",&a); scanf("%s",&b); lena=strlen(a); lenb=strlen(b); printf("%d\n",LCS(0,0)); } return 0; } int LCS(int i,int j) { if(i>=lena || j>=lenb) return 0; if(a[i]==b[j]) return 1+LCS(i+1,j+1); else return LCS(i+1,j)>LCS(i,j+1)? LCS(i+1,j):LCS(i,j+1); }也可以从后即两串的末尾开始递归,代码如下: #include<iostream> #include<cstring> using namespace std; #define N 1000 char a[N],b[N]; int lena,lenb; int LCS(int,int);///两个参数分别表示数组a的下标和数组b的下标 int main() { int n; cin>>n; while(n--) { cin>>a>>b; lena=strlen(a); lenb=strlen(b); cout<<LCS(lena-1,lenb-1)<<endl; } return 0; } int LCS(int i,int j) { if(i==-1||j==-1) return 0; if(a[i]==b[j]) return 1+LCS(i-1,j-1); else return LCS(i-1,j)>LCS(i,j-1)? LCS(i-1,j):LCS(i,j-1); } 但是这种方法容易超时,重复了很多相同的递归,所以此种方法不妥!由于在所考虑的子问题空间中,总共只有θ(m*n)个不同的子问题,因此,用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度,b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的,这在构造最长公共子序列时要用到。最后,X和Y的最长公共子序列的长度记录于c[m,n]中。 int LCS_LENGTH(char x[],char y[]) { m=strlen(x+1); n=strlen(y+1); int i,j; for(i=1;i<=m;++i) c[i][0]=0; for(j=0;j<=n;++j) c[0][j]=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; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } return 0; } 由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=<x1, x2, …, xm>和Y=<y1, y2, …, yn>的最长公共子序列。首先从b[m,n]开始,沿着其中的数字标记在数组b中搜索。 当b[i,j]中遇到"1"时(意味着xi=yi是LCS的一个元素),表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列;当b[i,j]中遇到"2"时,表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同;当b[i,j]中遇到"3"时,表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。 2.4、构造最长公共子序列 下面的算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。通过算法的调用LCS(length[X],length[Y],X,b),便可打印出序列X和Y的最长公共子序列。 递归打印: void LCS(int i,int j,char x[],int b[N][N]) { if(i+j==0) return; if(b[i][j]==1) { LCS(i-1,j-1,x,b); cout<<x[i]; } else if(b[i][j]==2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b) 递推打印: for(i=m,j= n;i>=1&&j>=1;) { if(x[i]==y[j]) { cout<<x[i]<<" ";//倒序打印的 i--; j--; } else { if(c[i][j-1]>c[i-1][j]) { j--; } else { i--; } } }*/ for(i=0;i<=m;i++) { for(j=0;j<=n;j++) { cout<<c[i][j]<<" "; } cout<<endl; } for(i=1,j=1;i<=m&&j<=n;) { if(x[i]==y[j]) { cout<<x[i]<<" ";//正序打印的 i++; j++; } else { if(c[i][j-1]>c[i-1][j]) { j++; } else { i++; } } } 完整代码: #include<iostream> #include<cstring> using namespace std; #define N 1000 int c[N][N],n,m,b[N][N]; int LCS_LENGTH(char x[],char y[]) { m=strlen(x+1); n=strlen(y+1); int i,j; for(i=1;i<=m;++i) c[i][0]=0; for(j=0;j<=n;++j) c[0][j]=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; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } } } return 0; } /*void LCS(int i,int j,char x[],int b[N][N]) { if(i+j==0) return; if(b[i][j]==1) { LCS(i-1,j-1,x,b); cout<<x[i]; } else if(b[i][j]==2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); }*/ int main() { int p;cin>>p; while(p--) { char x[N+1],y[N+1]; cin>>x+1>>y+1; LCS_LENGTH( x, y); //LCS(m,n,x,b); cout<<c[m][n]<<endl; } return 0; } 3、将最长公共子序列问题转化为最长上升子序列问题 LCS ->LIS:设有序列A,B。记序列A中各个元素在B中的位子(降序排列),然后按在A中的位置依次列出然后求A的最长递增子序列。 例如: A串位置             1 2 3 4                             B串位置:        1 2 3 4                 A串: 4 3 5 2                                            B串: 2 5 4 3 A串在B串--位置  3 4 2 1  因为B串已经顺序了,只要求出这行的最长递增子序列 就是最长公共子序列的长度了。   例如:有A={a,b,a,c,x},B={b,a,a,b,c,a}则有a={6,3,2},b={4,1},c={5};x=/;(注意降序排列) 然后按A中次序排出{a(6,3,2),b(4,1),a(6,3,2),c(5),x()}={6,3,2,4,1,6,3,2,5};对此序列求最长递增子序列即可 4、o(n^2)解法 分析: dp[i][j]表示 s1 以 i 结尾和 s2 以 j  结尾的最长公共子序列长度;  if(i==0||j==0) dp[i][j]=0 ; if(s1[i]==s2[j])  dp[i][j]=dp[i-1][j-1]+1 else     dp[i][j]=max(dp[i][j-1],dp[i-1][j]); 动规方程: dp[i][j]=max( dp[i-1][j-1] + (a[i]==b[j]) , max( dp[i-1][j] , dp[i][j-1] ) ) #include<iostream> #include<cstring> #define N 1010 using namespace std; int dp[N][N]; char s1[N],s2[N]; int max(int a,int b) { return a>=b?a:b; } int main() { int test,i,j,len1,len2; cin>>test; while(test--) { cin>>s1+1>>s2+1; len1=strlen(s1+1); len2=strlen(s2+1); for(i=0;i<=len1;i++) dp[i][0]=0; for(i=0;i<=len2;i++) dp[0][i]=0; for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(s1[i]==s2[j]) { dp[i][j]=dp[i-1][j-1]+1; } else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } cout<<dp[len1][len2]<<endl; } return 0; } 5、滚动数组解法 dp[i][j] 来自于 dp[i-1][j-1] 和 dp[i-1][j] 和 dp[i][j-1]。也就是来自于前一层和同一层的前一个元素,所以滚动数组两层的结构可以用上去~ 首先我们利用 前一层的 dp[i-1][j-1] 和 dp[i-1][j] 算出 dp[i][j] ,然后得到当前层的 dp[i] 的所有值后,再 j 从1到 len 地对 dp[i][j] 取 max (dp[i][j] , dp[i][j-1] ),这样就达到上面dp式子的效果了。 #include<iostream> #include<cstring> #define N 1010 using namespace std; int dp[2][N]; char s1[N],s2[N]; int max(int a,int b) { return a>=b?a:b; } int main() { int test,i,j,len1,len2; cin>>test; while(test--) { cin>>s1+1>>s2+1; len1=strlen(s1+1); len2=strlen(s2+1); memset(dp,0,sizeof(dp)); for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { if(s1[i]==s2[j]) dp[i%2][j]=dp[(i-1)%2][j-1]+1; else dp[i%2][j]=max(dp[(i-1)%2][j],dp[i%2][j-1]); } } cout<<dp[len1%2][len2]<<endl; } return 0; } 例题:南阳理工题目36。17


上一篇:STM32时钟配置
下一篇:linux中如何查看,安装,卸载程序

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款