动态规划中的最长公共子序列_第1页
动态规划中的最长公共子序列_第2页
动态规划中的最长公共子序列_第3页
动态规划中的最长公共子序列_第4页
动态规划中的最长公共子序列_第5页
已阅读5页，还剩10页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

3.3最长公共子序列,定义：一个给定序列的是在该序列中删去若干元素后得到的序列。找出A,B,C,D的所有子序列思考：有n个元素的序列至多有多少个子序列？,2n（说“至多”是因为子序列可能相等（但具有不同下标序列）,公共子序列,定义：如果序列Z既是序列X的子序列又是序列Y的子序列，则称Z是X和Y的公共子序列。找出X=(A,B,C,D,A,B),Y=(B,D,C,A,B,A)的所有公共子序列。,最长公共子序列,找出X和Y的最长公共子序列。对于任意给定的X和Y，它们的最长公共子序列唯一吗？举例说明。,不一定。如A,B与B,A本节的问题是只找出一个最长公共子序列。,最长公共子序列的结构,设序列X=x1,x2,xm,Y=y1,y2,yn,Z=z1,z2,zk,则(1)若xm=yn,则Zk-1是Xm1和Yn1的最长公共子序列；如：X=,C,Y=,C,则Z=,C,最长公共子序列的结构(续),(2)若xmyn,且zkxm，则Z是Xm1和Y的最长公共子序列；如：X=,C,Y=,B,zkC,则在计算最长公共子序列时，可不考虑X的最后一个元素C,最长公共子序列的结构(续),(3)若xmyn,且zkyn，则Z是X和Yn1的最长公共子序列如：X=,C,Y=,B,zkB,则在计算最长公共子序列时，可不考虑Y的最后一个元素B,最长公共子序列的结构(续),两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，因此，最长公共子序列问题具有最优子结构性质。,讨论,可否根据序列的第1个元素来重述本问题？这样做有什么优缺点？,可以。这样做不利于描述，如前面Xm1可以方便地表示X前m1个元素，改后就比较麻烦。从递归的角度来看，一般也是从后面增减元素。,当xm=yn时，有一个子问题，即：找出Xm1和Yn1的最长公共子序列当xmyn时，有两个子问题，即(1)找出Xm1和Y的最长公共子序列，(2)找出X和Yn1的最长公共子序列。而这两个子问题都包含了同一个子问题(Xm1,Yn1)。因此，本问题满足子问题重叠性质。,问题分析,令cij记录Xi和Yj的最长公共子序列的长度，则有0i=0,j=0cij=ci-1j-1+1xi=yjmaxcij-1,ci-1jxiyj,问题分析(续),显然不应以递归方式（自顶向下，即先考虑最后一个字符）设计算法，而应设计动态规划算法，即从第一个字符开始考虑。,问题分析(续),计算最优值程序跟踪,X=ACBDY=ABDA,cb,补充习题,1.X=B,C,A,DY=C,A,B,D,求X与Y的最长公共子序列，并画出数组c与b.cb,i:j:,补充习题(答案),1.X=B,C,A,DY=C,A,B,D,求X与Y的最长公共子序列，并画出数组c与b.cb,i:123j:123412341234,讨论,结构化与面向对象程序设计的联系与区别？,面向对象的局部来看是结构化的。结构化的基本思想是“自顶向下，逐步求精”,面向对象的基本意图是提高软件模块的
人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论