算法设计与分析40学时课件ch4new

第四章 动态规划技术,骆吉洲 计算机科学与工程系,4.1 动态规划原理 4.2 最长公共子序列 4.3 矩阵链惩罚 4.4 0/1背包问题 4.5 最优二叉搜索树,提要,参考资料,Introduction to Algorithms 第15章: 15.2, 15.3, 15.4, 15.5 计算机算法设计与分析 第3章: 3.1, 3.3, 3.5, 3.10, 3.11 网站资料 第四章,4.1 动态规划技术的基本要素,为什么引入动态规划? 什么是动态规划? 如何进行动态规划?,分治技术的问题 子问题是相互独立的 如果子问题不是相互独立的，分治方法将重复计算公共子问题，效率很低 例如，计算斐波那契数列的第n项 F(0)=F(1)=1 F(n)=F(n-1)+F(n-2),Why?,分治技术的问题 子问题是相互独立的 如果子问题不是相互独立的，分治方法将重复计算公共子问题，效率很低 分治算法 算法F(n) 输入:非负整数n 输出:斐波那契数列第n项 1. If n=0 或1 Then 输出1,算法结束 2. f1F(n-1); 3. f2F(n-2); 4. 输出f1+f2;,Why?,时间复杂性 T(1)=T(0)=1 T(n)=T(n-1)+T(n-2) T(n)不是多项式有界的,提高效率的方法 从规模最小的子问题开始计算 用恰当数据结构存储子问题的解，供以后查询 确保每个子问题只求解一次 算法 算法F(n) 输入:非负整数n 输出:斐波那契数列第n项 1. A0 1; A1 1; 2. For i=2 To n 3. Ai Ai-1+Ai-2； 4. 输出An;,Why?,时间复杂性 T(n)=(n) 存在(log n)的分治算法,©DB-LAB(2003),分治技术的问题 子问题是相互独立的 如果子问题不是相互独立的，分治方法将重复计算公共子问题，效率很低 优化问题 给定一组约束条件和一个代价函数，在解空间中搜索具有最小或最大代价的优化解 很多优化问题可分为多个子问题，子问题相互关联，子问题的解被重复使用,Why?,©DB-LAB(2003),动态规划算法特点 把原始问题划分成一系列子问题 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间 自底向上地计算 适用范围 一类优化问题：可分为多个相关子问题，子问题的解被重复使用,What?,使用Dynamic Programming的条件 Optimal substructure（优化子结构） 当一个问题的优化解包含了子问题的优化解时，我们说这个问题具有优化子结构。 缩小子问题集合，只需那些优化问题中包含的子问题，减低实现复杂性 优化子结构使得我们能自下而上地完成求解过程 Subteties（重叠子问题） 在问题的求解过程中，很多子问题的解将被多次使用,How?,动态规划算法的设计步骤 分析优化解的结构 递归地定义最优解的代价 自底向上地计算优化解的代价保存之， 并获取构造最优解的信息 根据构造最优解的信息构造优化解,4.2 最长公共子序列,问题的定义 最长公共子序列 (LCS) 结构分析 建立求解LCS长度的递归方程 自底向上LCS长度的计算 构造优化解,子序列 X=(A, B, C, B, D, B) Z=(B, C, D, B)是X的子序例 W=(B, D, A)不是X的子序例 公共子序列 Z是序列X与Y的公共子序列如果Z是X的子序也是Y的子序列。,问题的定义,最长公共子序列（LCS）问题 输入：X = (x1,x2,.,xn)，Y = (y1,y2,.ym) 输出：Z = X与Y的最长公共子序列,蛮力法 枚举X的每个子序列Z 检查Z是否为Y的子序列 T(n)=O(m2n),最长公共子序列结构分析,第i前缀 设X=(x1, x2, ., xn)是一个序列，X的第i前缀Xi是一个序列，定义为Xi=(x1, ., xi ) 例. X=(A, B, D, C, A), X1=(A), X2=(A, B), X3=(A, B, D),优化子结构 定理1（优化子结构）设X=(x1, ., xm)、Y=(y1, ., yn) 是两个序列，Z=(z1, ., zk)是X与Y的LCS，我们有： 如果xm=yn, 则zk=xm=yn, Zk-1是Xm-1和Yn-1的LCS， 即，LCSXY = LCSXm-1Yn-1+ . 如果xmyn，且zkxm，则Z是Xm-1和Y的LCS，即 LCSXY= LCSXm-1Y 如果xmyn,且zkyn,则Z是X与Yn-1的LCS，即 LCSXY= LCSXYn-1,证明: . X=, Y=，则 LCSXY = LCSXm-1Yn-1+ . 设zkxm，则可加xm=yn到Z，得到一个长为k+1的X与Y 的公共序列，与Z是X和Y的LCS矛盾。于是zk=xm=yn。 现在证明Zk-1是Xm-1与Yn-1的LCS。显然Zk-1是Xm-1与Yn-1 的公共序列。我们需要证明Zk-1是LCS。 设不然，则存在Xm-1与Yn-1的公共子序列W，W的长大 于k-1。增加xm=yn到W，我们得到一个长大于k的X与Y的 公共序列，与Z是LCS矛盾。于是，Zk-1是Xm-1与Yn-1的 LCS., X=, Y=， xmyn，zkxm，则 LCSXY= LCSXm-1Y 由于zkxm，Z是Xm-1与Y的公共子序列。我们来 证Z是Xm-1与Y的LCS。设Xm-1与Y有一个公共子序列 W，W的长大于k, 则W也是X与Y 的公共子序列，与 Z是LCS矛盾。 同可证。,X和Y的LCS的优化解结构为 LCSXY=LCSXm-1Yn-1+ if xm=yn LCSXY=LCSXm-1Y if xmyn, zkxm LCSXY=LCSXYn-1 if xmyn, zkyn,算法SimpleLCS(X,Y) 输入： X = (x1,x2,.,xn)，Y = (y1,y2,.ym) 输出： X,Y的最长公共子序列 1. If m=0 或 n=0 Then 输出空串,算法结束; 2. If xn=ym Then 3. 输出SimpleLCS(X,Y)+; 4. Else 5. Z1SimpleLCS(Xn-1,Y)； 6. Z2SimpleLCS(X,Ym-1)； 7. 输出Z1,Z2中较长者；,分治算法,子问题重叠性,LCSXY,LCSXm-1Yn-1,LCSXm-1Y,LCSXYn-1,LCSXm-2Yn-2,LCSXm-2Yn-1,LCSXm-1Yn-2,LCS问题具有子问题重叠性,建立LCS长度的递归方程,Ci, j = Xi与Yj 的LCS的长度 LCS长度的递归方程 Ci, j = 0 if i=0 或 j=0 Ci, j = Ci-1, j-1 + 1 if i, j0 and xi = yj Ci, j = Max(Ci, j-1, Ci-1, j) if i, j0 and xi yj,基本思想,自底向上计算LCS的长度,计算过程,C0,0,C0,1,C0,3,C0,2,C0,4,C1,0,C2,0,C3,0,C1,1,C2,1,C3,1,C1,2,C1,3,C1,4,C2,2,C2,3,C2,4,C3,2,C3,3,C3,4,计算LCS长度的算法 数据结构 C0:m,0:n: Ci,j是Xi与Yj的LCS的长度 B1:m,1:n: Bi,j是指针，指向计算Ci,j 时所选择的子问题的优化解 所对应的C表的表项,©DB-LAB(2003),LCS-length(X, Y) mlength(X)；nlength(Y)； For i1 To m Do Ci,00; For j1 To n Do C0,j0; For i1 To m Do For j1 To n Do If xi = yj Then Ci,jCi-1,j-1+1；Bi,j“”; Else If Ci-1,jCi,j-1 Then Ci,jCi-1,j; Bi,j“”; Else Ci,jCi,j-1; Bi,j“”; Return C and B.,基本思想 从Bm, n开始按指针搜索 若Bi, j=“”，则xi=yj是LCS的一个元素 如此找到的“LCS”是X与Y的LCS的Inverse,构造优化解,©DB-LAB(2003),Print-LCS(B, X, i, j) IF i=0 or j=0 THEN Return; IF Bi, j=“” THEN Print-LCS(B, X, i-1, j-1); Print xi; ELSE If Bi, j=“” THEN Print-LCS(B, X, i-1, j); ELSE Print-LCS(B, X, i, j-1). Print-LCS(B, X, length(X), length(Y) 可打印出X与Y的LCS。,4.3 矩阵链乘法,输入：, Ai是矩阵 输出：计算A1A2.An的最小代价方法,问题的定义,矩阵乘法的代价/复杂性: 乘法的次数 若A是pq矩阵，B是qr矩阵，则AB 的代价是O(pqr),©DB-LAB(2003),矩阵链乘法的实现 矩阵乘法满足结合率。 计算一个矩阵链的乘法可有多种方法: 例如, （A1A2A3A4） =（A1(A2(A3A4) =（(A1A2)(A3A4) = (（A1A2）A3)A4),Motivation,矩阵链乘法的代价与计算顺序的关系 设A1=10100矩阵, A2=1005矩阵, A3=550矩阵 T(A1A2)A3)=101005+10550=7500 T(A1(A2A3)=100550+1010050=750000,结论: 不同计算顺序有不同的代价,p(n)= 1 if n=1 p(n)= if n1 p(n)=C(n-1)=Catalan数= = (4n/n3/2),矩阵链乘法优化问题的解空间 设p(n)=计算n个矩阵乘积的方法数 p(n)的递归方程,（A1 Ak)(Ak+1An),如此之大的解空间是无法用枚举方法求出最优解的！,©DB-LAB(2003),下边开始设计求解矩阵链乘法问题的动态规划算法,分析优化解的结构 递归地定义最优解的代价 自底向上地计算优化解的代价保存之， 并获取构造最优解的信息 根据构造最优解的信息构造优化解,两个记号 Ai-j=AiAi+1Aj cost(Ai-j )=计算Ai-j的代价 优化解的结构 若计算A1n的优化顺序在k处断开矩阵链, 即A1n=A1kAk+1n，则在A1n的优化顺序中，对应于子问题A1k的解必须是A1-k的优化解，对应于子问题Ak+1n的解必须是Ak+1n的优化解,分析优化解的结构,具有优化子结构： 问题的优化解包括子问题优化解,子问题重叠性,A1A2A3A4,(A1)(A2A3A4),(A1A2)(A3A4 ),(A1A2 A3)(A4 ),具有子问题重叠性,(A3A4),(A3A4),(A1A2 ),(A1A2),©DB-LAB(2003),假设 mi,