算法笔记动态规划最长公共子序列问题（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的集合共有2m个不同子序列，因此，穷举法需要指数级别的运算时间。进一步分解问题特性，最长公共子序列问题实际上具有最优子结构性质。 设序列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,x2xm-1，Yn-1=y1,y2yn-1,Zk-1=z1,z2zk-1。 递推关系：用cij记录序列Xi和Yj的最长公共子序列的长度。其中，Xi=x1,x2xi，Yj=y1,y2yj。当i=0或j=0时，空序列是xi和yj的最长公共子序列。此时，cij=0；当i,j0，xi=yj时，cij=ci-1j-1+1；当i,j0，xi!=yj时，cij=maxcij-1,ci-1j，由此建立递推关系如下：构造最优解：由以上分析可知，要找出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的最长公共子序列。设数组bij记录cij的值由哪一个子问题的解得到的，从bmn开始，依其值在数组b中搜索，当bij=1时，表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列。当bij=2时，表示Xi和Yj的最长公共子序列与Xi-1和Yj-1的最长公共子序列相同。当bij=3时，表示Xi和Yj的最长公共子序列与Xi和Yj-1的最长公共子序列相同。 代码如下：cpp1. /3d3-1最长公共子序列问题2. #includestdafx.h3. #include4. 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,B16. /Y=B,D,C,A,B,A17. 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. ci=newintN+1;25. bi=newintN+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最长公共子序列长度为：cMNendl;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. coutsi;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. ci0=0;56. for(i=1;i=n;i+)57. c0i=0;58. 59. for(i=1;i=m;i+)60. 61. for(j=1;j=cij-1)69. 70. cij=ci-1j;71. bij=2;72. 73. else74. 75. cij=cij-1;76. bij=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(bij=1)89. 90. LCS(i-1,j-1,x,b);91. coutxi;92. 93. elseif(bij=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省去。事实上，数组元素ci,j的值仅由ci-1j-1，ci-1j和cij-1三个值之一确定，而数组元素bij也只是用来指示cij究竟由哪个值确定。因此，在算法LCS中，我们可以不借助于数组b而借助于数组c本身临时判断cij的值是由ci-1j-1，ci-1j和cij-1中哪一个数值元素所确定，代价是(1)时间。既然b对于算法LCS不是必要的，那么算法LCS_length便不必保存它。这一来，可节省(mn)的空间，而LCS_length和LCS所需要的时间分别仍然是(mn)和(m+n)。另外，如果只需要计算最长公共子序列的长度，则算法的空间需求还可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。更进一步的分析还可将空间需求减至min(m, n)。cpp1. /3d3-2最长公共子序列问题2. #includestdafx.h3. #include4. 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,B16. /Y=B,D,C,A,B,A17. 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. ci=newintN+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最长公共子序列长度为：cMNendl;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. coutsi;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. ci0=0;54. for(i=1;i=n;i+)55. c0i=0;56. 57. for(i=1;i=m;i+)58. 59. for(j=1;j=cij-1)66. 67. cij=ci-1j;68. 69. else70. 71. cij=cij-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(cij=ci-1j-1+1)84. 85. LCS(i-1,j-1,x,c);86. coutxi=cij-1)89. 90. LCS(i-1,j,x,c);91. 92. else93. 94. LCS(i,j-1,x,c);95. 96. 运行结果如下： 从运行结果中可以看出，算法LCS回溯算法仅仅打印了其中一条最大公共子序列，如果存在多条公共子序列的情况下。怎么解决？对bij二维数组的取值添加一种可能，等于4，这代表了我们说的这种多支情况，那么回溯的时候可以根据这个信息打印更多可能的选择。你从（7,6)点开始按bij的值指示的方向回溯，把所有的路径遍历一遍，如果是能达到起点（1,1)的路径，就是LCS了，有多少条打印多少条。可是，在回溯路径的时候，如果采用一般的全搜索，会进行了很多无用功。即重复了很多，且会遍历了一些无效路径，因为这些路径最终不会到达终点(1,1)，因此加大算法复杂度和时间消耗。 博文给出了一种矩行搜索的解决办法降低了算法的复杂度。算法主要是利用两个栈store,print，一个用来储存节点，一个用来打印节点。栈的实现代码如下(文件Stack.h)：cpp1. /*2. 头文件-headfile3. */4. 5. template6. classStackNode7. public:8. Tdata;9. StackNode*next;10. ;11. 12. template13. classStack14. public:15. Stack(void):top(NULL)16. boolIsEmpty(void)constreturntop=NULL;17. voidPush(constTdata);18. boolPop(T*data);19. boolPeek(T*data)const;20. StackNode*GetStackNode();21. private:22. StackNode*top;23. ;24. 25. template26. StackNode*Stack:GetStackNode()27. returntop;28. 29. 30. template31. voidStack:Push(constTdata)32. StackNode*node=newStackNode();33. node-data=data;34. node-next=top;35. top=node;36. 37. 38. template39. boolStack:Peek(T*data)const40. if(IsEmpty()returnfalse;41. *data=top-data;42. returntrue;43. 44. 45. template46. boolStack:Pop(T*data)47. if(IsEmpty()returnfalse;48. *data=top-data;49. StackNode*node=top;50. top=top-next;51. delete(node);52. returntrue;53. 所有最长公共子序列问题LCS 矩阵搜索代码如下：cpp1. /3d3-3所有最长公共子序列问题LCS矩阵搜索2. #includestdafx.h3. #includestack.h4. #include5. usingnamespacestd;6. 7. typedefint*Matrix;8. constintM=7;9. constintN=6;10. 11. typedefstruct_Element12. 13. intlcslen;/当前节点的LCS长度14. introw;/当前节点的行坐标15. intcol;/当前节点的列坐标16. Element;17. 18. voidoutput(char*s,intn);19. 20. ElementCreateElement(intnlen,introw,intcol);21. 22. MatrixGreateMatrix(introw,intcol);23. voidDeleteMatrix(Matrixp,introw);24. 25. voidPrintStack(Stack*ps,char*str,intlen);26. voidSearchE(Matrixpb,intcurposx,intcurposy,int&eposx,int&eposy,intntype);27. 28. voidLCSLength(intm,intn,char*x,char*y,Matrixpc,Matrixpb);29. voidLCS(char*x,Matrixpc,Matrixpb,introw,intcol);/矩阵搜索回溯30. 31. 32. intmain()33. charx=,A,B,C,B,D,A,B;34. chary=,B,D,C,A,B,A;35. 36. Matrixb=GreateMatrix(M,N);37. Matrixc=GreateMatrix(M,N);38. 39. LCSLength(M,N,x,y,c,b);40. 41. cout序列X：endl;42. output(x,M);43. cout序列Y：endl;44. output(y,N);45. 46. cout序列X、Y最长公共子序列长度为：cMNendl;47. cout序列X、Y最长公共子序列为：endl;48. 49. LCS(x,c,b,M,N);50. 51. DeleteMatrix(b,M);52. DeleteMatrix(c,M);53. 54. return0;55. 56. 57. voidoutput(char*s,intn)58. 59. for(inti=1;i=n;i+)60. 61. coutsi;62. 63. coutendl;64. 65. 66. ElementCreateElement(intnlen,introw,intcol)67. 68. Elementele;69. ele.lcslen=nlen;70. ele.col=col;71. ele.row=row;72. returnele;73. 74. 75. MatrixGreateMatrix(introw,intcol)76. 77. Matrixp=newint*row+1;78. for(inti=0;i=row;i+)79. 80. pi=newintcol+1;81. 82. returnp;83. 84. 85. voidDeleteMatrix(Matrixp,introw)86. 87. for(inti=0;i=row;i+)88. 89. deletepi;90. 91. 92. deletep;93. 94. 95. voidPrintStack(Stack*s,char*str,intlen)96. 97. if(s=NULL|str=NULL)98. return;99. 100. StackNode*sn=s-GetStackNode();101. 102. while(sn!=NULL&sn-data.row=len)103. 104. coutdata.rownext;106. 107. 108. coutendl;109. 110. 111. voidSearchE(Matrixpb,intcurposx,intcurposy,int&eposx,int&eposy,intntype)112. 113. switch(pbcurposxcurposy)114. 115. case1:116. eposx=curposx;117. eposy=curposy;118. return;119. case2:120. SearchE(pb,curposx-1,curposy,eposx,eposy,ntype);121. break;122. case3:123. SearchE(pb,curposx,curposy-1,eposx,eposy,ntype);124. break;125. case4:126. if(ntype=0)127. /搜索e1点，如过碰到分叉点，向上继续搜索128. SearchE(pb,curposx-1,curposy,eposx,eposy,ntype);129. else130. /搜索e2点，如过碰到分叉点，向左继续搜索131. SearchE(pb,curposx,curposy-1,eposx,eposy,ntype);132. break;133. 134. 135. 136. voidLCSLength(intm,intn,char*x,char*y,Matrixpc,Matrixpb)137. 138. inti,j;139. 140. for(i=1;i=m;i+)141. pci0=0;142. for(i=1;i=n;i+)143. pc0i=0;144. 145. for(i=1;i=m;i+)146. 147. for(j=1;jpcij-1)155. 156. pcij=pci-1j;157. pbij=2;158. 159. elseif(pci-1jpcij-1)160. 161. pcij=pcij-1;162. pbij=3;163. 164. else165. 166. pcij=pcij-1;/由左节点或上节点转移而来167. pbij=4;/标记为4168. 169. 170. 171. 172. 173. voidLCS(char*x,Matrixpc,Matrixpb,introw,intcol)174. 175. if(x=NULL|pc=NULL|pb=NULL)176. return;177. 178. Stackstore,print;/构造两个栈store，print179. Elementstoretop;/store栈的栈顶节点180. Elementelement;/临时变量181. Elementvirtualnode;/虚拟节点182. intntoplen;/保存store栈顶节点的LCS长度183. intex1,ey1,ex2,ey2;/矩形搜索的两个节点的坐标184. inti,j;185. 186. virtualnode=CreateElement(pcrowcol+1,row+1,col+1);187. 188. store.Push(virtualnode);/压入虚拟节点到store189. 190. while(!store.IsEmpty()191. 192. store.Pop(&storetop);193. if(storetop.row=1|storetop.col=1)/如果是边界节点194. 195. print.Push(storetop);196. PrintStack(&print,x,row);/打印print栈里面除虚拟节点之外的所有节点197. store.Peek(&element);198. ntoplen=element.lcslen;/当前store的栈顶节点的LCS长度199. 200. /*弹出print栈中所有LCS长度小于等于ntoplen的节点*/201. while(print.Peek(&element)&element.lcslen=ntoplen)202. 203. print.Pop(&element);204. 205. 206. else207. 208. print.Push(storetop);209. SearchE(pb,storetop.row-1,storetop.col-1,ex1,ey1,0);210. SearchE(pb,storetop.row-1,storetop.col-1,ex2,ey2,1);/*alsoothervalueisok*/211. 212. if(ex1=ex2&ey1=ey2)213. 214. element=CreateElement(pcex1ey1,ex1,ey1);215. store.Push(element);/压入store栈，回到步骤2216. 217. else218. 219. for(i=ex1;i=ex2;i+)220. for(j=ey2;j=ey1;j+)221. 222. if(pbij=1)223. 224. element=CreateElement(pcij,i,j);225. store.Push(element);226. 227. 228. 229. 230. 231. 232. 矩形搜索LCS算法回溯路径如下：算法LCS先构造了一个虚拟节点virtualnode，指向节点(m,n)的右下角，即(m+1,n+1),这个节点的LCS的长度假设为最大公共子序列长度+1。将虚拟节点压入栈store，然后从虚拟节点出发，当状态bij=4时，节点开始分叉，根据设置类型向上(ntype=0)、向左(ntype=1)矩形搜索查找导致公共子序列长度发生变化的节点(跳跃点)，即bij=1对应的节点压入store栈中，然后s判断store弹出元素是否已到达边界，如果没有到达，则将节点压入print栈中，如果到达边界，则打印print栈，输出其中一个最长公共序列。运行结果如下：专心-专注-专业