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

《算法设计与分析第6讲 动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划DynamicProgramming1最长公共子序列问题给定两个序列x(x1,..xm),y(y1,…yn)，寻找一个最长的公共子序列，lcs（x,y）.例X:ABCBDABY:BDCABALcs:BDAB,BCAB,BCBA算法１：穷举－－给出X的一个子串（2m个？），测试是不是Y的子串。１次测试的时间是θ(n)，故总时间＝θ(n2m),是个指数级别的。2算法思路１　先算出LCS(x,y)的长度２　再扩充之，得到LCS.用

2、S

3、记录串S的长度，策略：考虑x,y的前缀，变成一些会怎么样？定义C[i,j]=

4、LCS(x(1,..i),y(1,,,j)

5、则C[m,n]=

6、LCS(x,y)3递推式定理：证明：令Z(1,2,..k)＝LCS(x(1,2,..i),y(1,2,..j))则

7、Z

8、=C[i,j]=k.1x[i]=y[j].画出Ｚ到x和y的一一对应，z[k]一定对应到x[i]或（和）y[j]？.那么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)),即C[i-1,j-1]=k-1=C[i,j]-1.2else.如果Z[k]不对应x[i]或者y[j]。如果不对应X[i],则Z(1,2

9、,..k)=LCS(x(1,2,..i-1),y(1,2,..j)),如果不对应y[i],则Z(1,2,..k)=LCS(x(1,2,..i),y(1,2,..j-1)),故C[I,j]=max(C[i-1,j],C[I,j-1])4动态规划特征１－最优子结构刚才的证明发现，Z(1,2,..k)＝LCS(x,y)则Z(1,2…k-1)是x,y前缀的LCS.最优子结构：一个问题的最优解的一部分，是子问题的最优解。递归算法：LCS(x,y,i,j)Ifx[i]=y[j]thenC[i,j]=LCS(x,y,i-1,j-1)+1;ElseC[i,j]=max(LCS(x,y,i-

10、1,j),LCS(x,y,i,j-1))ReturnC[i,j]5递归算法复杂性递归树（最差情况，x[i]!=y[j]任何的i,j）2叉树，树高（m+n）,故节点个数O(2m+n)但是，可以观察到，很多子树是相同的，不必要递归再计算一次7,37,56,67,46,56,55,67,66,46,45,55,56,45,54,66动态规划特征2重叠子结构：递归中，有独立子问题被计算多次。实际上C[i,j]中，不同的只有mn个问题备忘录算法：LCS(x,y,i,j)ifC[i,j]!=nilthenifx[i]=y[j]thenC[i,j]=LCS(x,y,i-1,j-1)+1;

11、ElseC[i,j]=max(LCS(x,y,i-1,j),LCS(x,y,i,j-1));returnC[i,j]T=θ(mn)7动态规划算法自底向上计算，不递归ABCBDAB0000000B00111111D00111222C00122222A01122233B01223334A01223344回溯－重建LCS8