动态规划中地最长公共子序列.pptVIP

3.3 最长公共子序列 定义：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 找出{A, B, C, D}的所有子序列 思考：有n个元素的序列至多有多少个子序列？ 公共子序列 定义：如果序列Z既是序列X的子序列又是序列Y的子序列，则称Z是X和Y的公共子序列。 找出X = (A, B, C, D, A, B), Y = (B, D, C, A, B, A)的所有公共子序列。 最长公共子序列 找出X和Y的最长公共子序列。 对于任意给定的X和Y，它们的最长公共子序列唯一吗？举例说明。 最长公共子序列的结构 设序列X={x1, x2, …, xm}, Y={y1, y2, …, yn}, Z={z1, z2, …, zk},则 (1) 若xm = yn, 则Zk - 1 是Xm – 1和Yn – 1的最长公共子序列； 如：X = {…, C}, Y = {…, C}, 则Z = {…, C} 最长公共子序列的结构(续) (2)若xm ≠ yn, 且zk ≠ xm，则Z是Xm – 1和Y的最长公共子序列； 如：X = {… , C}, Y = {…, B}, zk ≠C, 则在计算最长公共子序列时，可不考虑X的最后一个元素C 最长公共子序列的结构(续) (3)若xm ≠ yn, 且zk ≠ yn，则Z是X和Yn– 1的最长公共子序列 如：X = {… , C}, Y = {…, B}, zk ≠B, 则在计算最长公共子序列时，可不考虑Y的最后一个元素B 最长公共子序列的结构(续) 两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，因此，最长公共子序列问题具有最优子结构性质。 讨论 可否根据序列的第1个元素来重述本问题？这样做有什么优缺点？ 问题分析 当xm = yn时，有一个子问题，即 ：找出Xm –1和Yn – 1的最长公共子序列 当xm ? yn时，有两个子问题，即 (1)找出Xm – 1和Y的最长公共子序列， (2)找出X和Yn – 1的最长公共子序列。而这两个子问题都包含了同一个子问题(Xm– 1, Yn–1) 。 因此，本问题满足子问题重叠性质。 问题分析(续) 令c[i][j]记录Xi和Yj的最长公共子序列的长度，则有 0 i = 0, j = 0 c[i][j] = c[i - 1][j - 1] + 1 xi = yj max{c[i][j - 1] , c[i - 1][j] } xi ≠ yj 问题分析(续) 显然不应以递归方式（自顶向下，即先考虑最后一个字符）设计算法，而应设计动态规划算法，即从第一个字符开始考虑。 计算最优值程序跟踪 补充习题 补充习题(答案) 讨论 结构化与面向对象程序设计的联系与区别？ * * 2n（包括空） 说“至多”是因为子序列可能相等（但具有不同下标序列） 不一定。如{A, B}与{B, A} 本节的问题是只找出一个最长公共子序列。 可以。这样做不利于描述，如前面Xm–1可以方便地表示X前m – 1 个元素，改后就比较麻烦。从递归的角度来看，一般也是从后面增减元素。 X = {A C B D} Y = {A B D A} c b 3 3 2 1 0 2 2 2 1 0 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 3 1 2 2 0 3 3 1 2 0 2 2 2 2 0 1 3 3 1 0 0 0 0 0 0 Y N 2 Y N 1 2 Y 4 N 3 N 2 Y 1 1 c[i-1][j]=c[i][j-1] x[i]=y[j] j i 1. X={B, C, A, D} Y={C, A, B, D},求X与Y的最长公共子序列，并画出数组c与b. c b 3 2 2 1 0 2 2 2 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 1 2 2 2 0 3 3 1 2 0 2 2 3 1 0 3 1 2 2 0 0 0 0 0 0 i: j: 1. X={B, C, A, D} Y={C, A, B, D},求X与Y的最长公共子序列，并画出数组c与b. c b 3 2 2