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

最长公共子序列?定义:一个给定序列的子序列是在该序列中删去若干元素后得到的序列。找出{A, B, C, D} 的所有子序列思考:有 n个元素的序列至多有多少个子序列? ?2 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,它们的最长公共子序列唯一吗?举例说明。?不一定。如{A, B} 与{B, A} ?本节的问题是只找出一个最长公共子序列。最长公共子序列的结构设序列 X ={x 1, x 2, …, x m}, Y ={y 1, y 2, …, y n}, Z ={z 1, z 2, …, z k},则(1) 若x m = y n, 则Z k - 1是X m– 1和Y n– 1的最长公共子序列; 如: X = { …, C} , Y = { …, C} , 则 Z = {…, C} 最长公共子序列的结构(续) (2) 若x m≠y n, 且z k≠x m,则 Z是X m– 1和 Y的最长公共子序列; 如: X = { … , C} , Y = { …, B} ,z k≠C, 则在计算最长公共子序列时,可不考虑 X的最后一个元素 C 最长公共子序列的结构(续) (3) 若x m≠y n, 且z k≠y n,则 Z是X和Y n– 1的最长公共子序列如: X = { … , C} , Y = { …, B} , z k≠B, 则在计算最长公共子序列时,可不考虑 Y的最后一个元素 B 最长公共子序列的结构(续) ?两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,因此,最长公共子序列问题具有最优子结构性质。讨论可否根据序列的第 1个元素来重述本问题?这样做有什么优缺点? 可以。这样做不利于描述,如前面 X m–1 可以方便地表示 X前 m – 1 个元素,改后就比较麻烦。从递归的角度来看, 一般也是从后面增减元素。?当x m=y n时,有一个子问题,即:找出 X m–1 和Y n– 1的最长公共子序列?当x m?y n时,有两个子问题,即(1) 找出 X m– 1和Y的最长公共子序列, (2) 找出 X和Y n– 1的最长公共子序列。而这两个子问题都包含了同一个子问题(X m– 1, Y n–1 ) 。因此,本问题满足子问题重叠性质。问题分析令c[i ][j]记录 X i和Y j的最长公共子序列的长度, 则有 0 i = 0, j = 0 c[i ][j ] = c[i - 1][ j - 1] + 1 x i = y j max{ c[i ][j - 1] , c[i - 1][ j] } x i≠y j问题分析(续)