算法设计与分析第6讲 动态规划.ppt

1、1,动态规划,Dynamic Programming,2,最长公共子序列问题,给定两个序列x(x1,.xm), y(y1,yn)，寻找一个最长的公共子序列，lcs（x,y）. 例 X: A B C B D A B Y: B D C A B A Lcs: BDAB, BCAB,BCBA 算法：穷举给出X的一个子串（2m个？），测试是不是Y的子串。次测试的时间是(n)，故总时间 (n2m),是个指数级别的。,3,算法思路,先算出LCS(x,y)的长度 再扩充之，得到LCS. 用|S|记录串S的长度， 策略：考虑x,y的前缀，变成一些会怎么样？ 定义Ci,j=|LCS(x(1,.i),y(1,j)|

2、 则Cm,n=LCS(x,y),4,递推式,定理： 证明：令Z(1,2,.k)LCS(x(1,2,.i),y(1,2,.j) 则|Z|=Ci, j=k. 1 xi=yj. 画出到x和y的一一对应，zk一定对应到xi或（和）yj？. 那么Z(1,2,.k-1)肯定对应在(x(1,2,.i-1),y(1,2,.j-1)上.另外，不会有更长的公共字串, 故Z(1,2,.k-1)LCS (x(1,2,.i-1),y(1,2,.j-1),即Ci-1,j-1=k-1=Ci,j-1. 2 else. 如果Zk不对应xi或者yj。如果不对应Xi,则Z(1,2,.k)=LCS(x(1,2,.i-1),y(1,2

3、,.j),如果不对应yi,则Z(1,2,.k)=LCS(x(1,2,.i),y(1,2,.j-1),故CI,j=max(Ci-1,j,CI,j-1),5,动态规划特征最优子结构,刚才的证明发现，Z(1,2,.k)LCS(x,y)则Z(1,2k-1)是x,y前缀的 LCS. 最优子结构： 一个问题的最优解的一部分，是子问题的最优解。 递归算法：LCS(x,y,i,j) If xi=yj then Ci,j=LCS(x,y,i-1,j-1)+1; Else Ci,j=max(LCS(x,y,i-1,j),LCS(x,y,i,j-1) Return Ci,j,6,递归算法复杂性,递归树 （最差情况，

4、xi!=yj 任何的i,j） 2叉树，树高（m+n）,故节点个数O(2m+n) 但是，可以观察到，很多子树是相同的，不必要递归再计算一次,7,3,7,5,6,6,7,4,6,5,6,5,5,6,7,6,6,4,6,4,5,5,5,5,6,4,5,5,4,6,7,动态规划特征2,重叠子结构：递归中，有独立子问题被计算多次。 实际上Ci,j中，不同的只有mn个问题 备忘录算法： LCS(x,y,i,j) if Ci,j != nil then if xi=yj then Ci,j=LCS(x,y,i-1,j-1)+1; Else Ci,j=max(LCS(x,y,i-1,j),LCS(x,y,i,j-1); return Ci,j T= (mn),8,动态规划算法,自底向上计算，不递归 A B C B D A B 0 0 0 0 0 0 0 B 0 0 1 1 1 1 1 1 D 0 0 1 1 1 2 2 2 C 0 0 1 2 2