0011算法笔记——【动态规划】最长公共子序列问题(LCS)

问题描述：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}是X的子序列是指存在一个严格递增的下标序列{i1,i2,…,ik}，使得对于所有j=1,2,…,k有Xij=Zj。例如，序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列，相应的递增下标序列为{2,3,5,7}。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}，则序列{B,C,A}是X和Y的一个公共子序列，序列{B,C,B,A}也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。给定两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，要求找出X和Y的一个最长公共子序列。问题解析：设X={A,B,C,B,D,A,B},Y={B,D,C,A,B,A}。求X，Y的最长公共子序列最容易想到的方法是穷举法。对X的多有子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列。由集合的性质知，元素为m的集合共有2^m个不同子序列，因此，穷举法需要指数级别的运算时间。进一步分解问题特性，最长公共子序列问题实际上具有最优子结构性质。设序列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的最长公共子序列。其中，Xm-1={x1,x2……xm-1}，Yn-1={y1,y2……yn-1},Zk-1={z1,z2……zk-1}。递推关系：用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中，Xi={x1,x2……xi}，Yj={y1,y2……yj}。当i=0或j=0时，空序列是xi和yj的最长公共子序列。此时，c[i][j]=0；当i,j0，xi=yj时，c[i][j]=c[i-1][j-1]+1；当i,j0，xi!=yj时，c[i][j]=max{c[i][j-1],c[i-1][j]}，由此建立递推关系如下：构造最优解：由以上分析可知，要找出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的最长公共子序列。设数组b[i][j]记录c[i][j]的值由哪一个子问题的解得到的，从b[m][n]开始，依其值在数组b中搜索，当b[i][j]=1时，表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列。当b[i][j]=2时，表示Xi和Yj的最长公共子序列与Xi-1和Yj-1的最长公共子序列相同。当b[i][j]=3时，表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。代码如下：[cpp]viewplaincopy1.//3d3-1最长公共子序列问题2.#includestdafx.h3.#includeiostream4.usingnamespacestd;5.6.constintM=7;7.constintN=6;8.9.voidoutput(char*s,intn);10.voidLCSLength(intm,intn,char*x,char*y,int**c,int**b);11.voidLCS(inti,intj,char*x,int**b);12.13.intmain()14.{15.//X={A,B,C,B,D,A,B}16.//Y={B,D,C,A,B,A}17.charx[]={'','A','B','C','B','D','A','B'};18.chary[]={'','B','D','C','A','B','A'};19.20.int**c=newint*[M+1];21.int**b=newint*[M+1];22.for(inti=0;i=M;i++)23.{24.c[i]=newint[N+1];25.b[i]=newint[N+1];26.}27.28.cout序列X：endl;29.output(x,M);30.cout序列Y：endl;31.output(y,N);32.33.LCSLength(M,N,x,y,c,b);34.35.cout序列X、Y最长公共子序列长度为：c[M][N]endl;36.cout序列X、Y最长公共子序列为：endl;37.LCS(M,N,x,b);38.coutendl;39.}40.41.voidoutput(char*s,intn)42.{43.for(inti=1;i=n;i++)44.{45.couts[i];46.}47.coutendl;48.}49.50.voidLCSLength(intm,intn,char*x,char*y,int**c,int**b)51.{52.inti,j;53.54.for(i=1;i=m;i++)55.c[i][0]=0;56.for(i=1;i=n;i++)57.c[0][i]=0;58.59.for(i=1;i=m;i++)60.{61.for(j=1;j=n;j++)62.{63.if(x[i]==y[j])64.{65.c[i][j]=c[i-1][j-1]+1;66.b[i][j]=1;67.}68.elseif(c[i-1][j]=c[i][j-1])69.{70.c[i][j]=c[i-1][j];71.b[i][j]=2;72.}73.else74.{75.c[i][j]=c[i][j-1];76.b[i][j]=3;77.}78.}79.}80.}81.82.voidLCS(inti,intj,char*x,int**b)83.{84.if(i==0||j==0)85.{86.return;87.}88.if(b[i][j]==1)89.{90.LCS(i-1,j-1,x,b);91.coutx[i];92.}93.elseif(b[i][j]==2)94.{95.LCS(i-1,j,x,b);96.}97.else98.{99.LCS(i,j-1,x,b);100.}101.}LCSLength函数在计算最优值时，分别迭代X，Y构造数组b,c。设数组每个元素单元计算耗费时间O(1)，则易得算法LCSLength的时间复杂度为O(mn)。在算法LCS中，依据数组b的值回溯构造最优解，每一次递归调用使i，或j减小1。从而算法的计算时间为O(m+n)。LCS的回溯构造最优解过程如下图所示:算法的改进：对于一个具体问题，按照一般的算法设计策略设计出的算法，往往在算法的时间和空间需求上还可以改进。这种改进，通常是利用具体问题的一些特殊性。例如，在算法LCS_length和LCS中，可进一步将数组b省去。事实上，数组元素c[i,j]的值仅由c[i-1][j-1]，c[i-1][j]和c[i][j-1]三个值之一确定，而数组元素b[i][j]也只是用来指示c[i][j]究竟由哪个值确定。因此，在算法LCS中，我们可以不借助于数组b而借助于数组c本身临时判断c[i][j]的值是由c[i-1][j-1]，c[i-1][j]和c[i][j-1]中哪一个数值元素所确定，代价是Ο(1)时间。既然b对于算法LCS不是必要的，那么算法LCS_length便不必保存它。这一来，可节省θ(mn)的空间，而LCS_length和LCS所需要的时间分别仍然是Ο(mn)和Ο(m+n)。另外，如果只需要计算最长公共子序列的长度，则算法的空间需求还可大大减少。事实上，在计算c[i][j]时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。更进一步的分析还可将空间需求减至min(m,n)。[cpp]viewplaincopy1.//3d3-2最长公共子序列问题2.#includestdafx.h3.#includeiostream4.usingnamespacestd;5.6.constintM=7;7.constintN=6;8.9.voidoutput(char*s,intn);10.voidLCSLength(intm,intn,char*x,char*y,int**c);11.voidLCS(inti,intj,char*x,int**c);12.13.intmain()14.{15.//X={A,B,C,B,D,A,B}16.//Y={B,D,C,A,B,A}17.charx[]={'','A','B','C','B','D','A','B'};18.chary[]={'','B','D','C','A','B','A'};19.20.int**c=newint*[M+1];21.for(inti=0;i=M;i++)22.{23.c[i]=newint[N+1];24.}25.26.cout序列X：endl;27.output(x,M);28.cout序列Y：endl;29.output(y,N);30.31.LCSLength(M,N,x,y,c);32.33.cout序列X、Y最长公共子序列长度为：c[M][N]endl;34.cout序列X、Y最长公共子序列为：endl;35.LCS(M,N,x,c);36.coutendl;37.}38.39.voidoutput(char*s,intn)40.{41.for(inti=1;i=n;i++)42.{43.couts[i];44.}45.coutendl;46.}47.48.voidLCSLength(intm,intn,char*x,char*y,int**c)49.{50.inti,j;51.52.for(i=1;i=m;i++)53.c[i][0]=0;54.for(i=1;i=n;i++)55.c[0][i]=0;56.57.for(i=1;i=m;i++)58.{59.for(j=1;j=n;j++)60.{61.if(x[i]==y[j])62.{63.c[i][j]=c[i-1][j-1]+1;64.}65.elseif(c[i-1][j]=c[i][j-1])66.{67.c[i][j]=c[i-1][j];68.}69.else70.{71.c[i][j]=c[i][j-1];72.}73.}74.}75.}76.77.voidLCS(inti,intj,char*x,int**c)78.{79.if(i==0||j==0)80.{81.return;82.}83.if(c[i][j]==c[i-1][j-1]+1)84.{85.LCS(i-1,j-1,x,c);86.coutx[i];87.}88.elseif(c[i-1][j]=c[i][j-1])89.{90.LCS(i-1,j,x,c);91.}92.else93.{94.LCS(i,j-1,x,c);95.}96.}运行结果如下：从运行结果中可以看出，算法LCS回溯算法仅仅打印了其中一条最大公共子序列，如果存在多条公共子序列的情况下。怎么解决？对b[i][j]二维数组的取值添加一种可能