《动态规划算法》PPT课件

Chapter 7,动态规划Dynamic Programming,2020/10/5,2,What is dynamic programming,与分治法类似, 动态规划也是通过组合子问题的解来求解问题. 分治算法将问题划分成独立子问题, 递归地解决这些子问题, 然后组合这些子问题的解来求解原始问题. If these subproblems are not independent, what will happen?,2020/10/5,3,算法总体思想,动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题,2020/10/5,4,但是经分解得到的子问题往往不是互相独立的. 不同子问题的数目常常只有多项式量级. 在用分治法求解时, 有些子问题被重复计算了许多次.,算法总体思想,2020/10/5,5,算法总体思想,T(n),Those who cannot remember the past are doomed to repeat it. (无法记取教训者必重蹈覆辙 ) -George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905),如果能够保存已解决的子问题的答案, 而在需要时再找出已求得的答案, 就可以避免大量重复计算, 从而得到多项式时间算法.,2020/10/5,6,Fibonacci sequence(序列),Fibonacci序列定义如下： 1. procedure f(n) 2. if n=1 or n=2 then return 1 3. else return f(n-1)+f(n-2) 这种递归形式有简洁、容易书写和容易查错等优点, 最主要是它的抽象性. 但是它远不是有效的算法. 算法复杂性: (n) Why?,2020/10/5,7,Fibonacci sequence分析,f(n)= f(n-1)+ f(n-2) =2f(n-2)+ f(n-3) =3f(n-3)+2f(n-4) =5f(n-4)+3f(n-5),2020/10/5,8,二项式系数的计算,有效计算上式的方法是按行构造帕斯卡三角形,2020/10/5,9,What is dynamic programming什么是动态规划？,当子问题发生重叠时, 分治法做了很多不必要的工作重复对重叠的子问题进行求解. 动态规划算法对每个子问题求解一次, 然后将结果保存在一张表里面, 这样可以避免每个已求解子问题的重复计算. 对于Fibonacci序列, 一个明显的方法是从f(1)开始自底向上地计算到f(n), 只需要(n)时间和(1)空间. 和前面的方法相比, 可以很大程度降低时间复杂度.,2020/10/5,10,The longest common subsequence problem最长公共子序列问题,在字母表上, 分别给出两个长度为n和m的字符串A和B, 确定在A和B中最长公共子序列的长度. 这里A=a1a2.an的子序列的一个形式为ai1ai2.aik的字符串, 其中每个ij在1到n之间, 并且1i1i2.ikn 蛮力法: 列举A所以的2n个子序列, 对于每一子序列在(m)时间内来确定它是否也是B的子序列. 很明显, 此算法的时间复杂的为(m*2n).,2020/10/5,11,递推公式,为了使用动态规划技术, 首先推导一个求最长公共子序列长度的递推公式. 令A=a1a2.an和B=b1b2.bm 令Li, j表示a1a2.ai和b1b2.bj的最长公共子序列的长度(i, j可能是0, 此时a1a2.ai和b1b2.bj中至少一个为空). 可得如下结论：,2020/10/5,12,递推公式,观察结论7.1 如果i和j都大于0, 那么 若ai=bj, Li, j=Li-1, j-1+1 若aibj, Li, j=maxLi, j-1, + Li-1, j 可得如下公式：,2020/10/5,13,现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对i和j的值，0 i n，0 j m，我们用一个(n+1)(m+1)表来计算Li, j的值，只需要用上面的公式逐行地填表L0n, 0m。算法如下：,2020/10/5,14,Algorithm 7.1 LCS Input: Two strings A and B of length n and m, respectively, over an alphabet Output: The length of the longest common subsequence of A and B 1. for i0 to n 2. Li, 00 3. end for 4. for j0 to m 5. L0, j0 6. end for,2020/10/5,15,7. for i1 to n 8. for j1 to m 9. if ai=bj then Li, jLi-1, j-1+1 10. else Li, jmaxLi, j-1, Li-1, j 11. end if 12. end for 13. end for 14. return Ln, m,2020/10/5,16,定理7.1 最长公共子序列问题的最优解能够在(nm)时间和(minm, n) 空间内得到. ？,2020/10/5,17,A=“xyxxzxyzxy” B=“zxzyyzxxyxxz”,图7.1 最长公共子序列问题的一个例子,2020/10/5,18,Algorithm 7.1pro LCS 1. for i0 to n 2. Li, 00 3. end for 4. for j0 to m 5. L0, j0 6. end for 7. for i1 to n 8. for j1 to m 9. if ai=bj then Li, jLi-1, j-1+1, bi, j”,2020/10/5,19,10. else 11. if Li-1, jLi, j-1 then 12. Li, jLi-1, j, bi, j” 13. else 14. Li, jLi, j-1, bi, j” 15. end if 16. end if 17. end for 18. end for 19. return Ln, m and bn, m,2020/10/5,20,print-LCS(b, A, i, j) 1. if i=0 or j=0 then return 2. if bi, j= ” then 3. print-LCS(b, A, i-1, j-1) 4. print ai 5. else 6. if bi, j= ” then print-LCS(b, A, i-1, j) 7. else print-LCS(b, A, i, j-1) 8. end if,2020/10/5,21,2020/10/5,22,算法的改进,在算法lcs和print-LCS中, 可进一步将数组b省去. 事实上, 数组元素Lij的值仅由Li-1j-1, Li-1j和Lij-1这3个数组元素的值所确定. 对于给定的数组元素Lij, 可以不借助于数组b而仅借助于L本身确定Lij的值是由Li-1j-1, Li-1j和Lij-1中哪一个值所确定的.,2020/10/5,23,算法的改进,如果只需要计算最长公共子序列的长度, 则算法的空间需求可大大减少. 事实上, 在计算Lij时, 只用到数组L的第i行和第i-1行. 因此, 用2行的数组空间就可以计算出最长公共子序列的长度. 进一步的分析还可将空间需求减至O(min(m, n).,2020/10/5,24,Matrix chain multiplication矩阵链相乘,设有4个矩阵A, B, C, D, 它们的维数分别是A:5010 B:1040 C:4030 D:305, 共有5种加括号的方式： (A(BC)D) 乘法次数: 16000 (A(B(CD) 乘法次数: 10500 (AB)(CD) 乘法次数: 36000 (AB)C)D) 乘法次数: 87500 (A(BC)D) 乘法次数: 34500,2020/10/5,25,Matrix chain multiplication矩阵链相乘,一般情况下, n个矩阵链M1M2.Mn相乘的耗费, 取决于n-1个乘法执行的顺序(结合方式). 蛮力算法: 计算出每一种可能顺序的数量乘法次数. 时间复杂度是：,算法复杂度分析： 对于n个矩阵的连乘积, 设其不同的计算次序为P(n). 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,2020/10/5,26,假设我们有n+1维数r1, r2, ., rn+1, 这里ri和ri+1分别是矩阵Mi的行数和列数, 1in. 我们将用Mi, j记MiMi+1.Mj的乘积, 我们还假设链Mi,j的乘法的最小耗费用数量乘法的次数来度量, 记为Ci, j. 对于给定的一对索引i和j, 1ijn, Mi,j可用如下方法计算: 设k是i+1和j之间的一个索引, 计算两个矩阵 Mi,k-1=MiMi+1Mk-1和Mk,j=MkMk+1Mj, 那么Mi,j=Mi,k-1Mk,j 显然, 用这种方法计算Mi,j的总耗费, 是计算Mi,k-1的耗费加上计算Mk,j的耗费, 再加上Mi,k-1乘以Mk,j的耗费(rirkrj+1), 因此得到了如下的公式:,2020/10/5,27,Particularly, 如果采用自顶向下的方式不能得到有效的算法, 导致巨大的重复递归调用.,2020/10/5,28,Illustration of matrix chain multiplication矩阵链乘图示,2020/10/5,29,Algorithm 7.2 MATCHAIN Input: An array r1.n+1 of positive integers corresponding to the dimensions of a chain of n matrices, where r1.n are the number of rows in the n matrices and rn+1 is the number of columns in Mn Output: The least number of scalar multiplications required to multiply the n matrices 1. for i1 to n Fill in diagonal d0 2. Ci, i0 3. end for 4. for d1 to n-1 Fill in diagonals d1 to dn-1 5. for i1 to n-d Fill in entries in diagonal di 6. ji+d 7. comment: The next three lines computes Ci, j 8. Ci, j 9. for ki+1 to j 10. Ci, jminCi, j, Ci, k-1+Ck, j+rirkrj+1 11. end for 12. end for 13. end for 14. return C1, n,2020/10/5,30,分析,算法matrixChain的主要计算量取决于算法中对r, i和k的3重循环. 循环体内的计算量为O(1), 而3重循环的总次数为 定理7.2 一个由n个矩阵组成的链相乘, 它所需的数量乘法最少次数可以在(n3)时间和(n2)空间内找出.,2020/10/5,31,M1:510 M2:104 M3:46 M2:610 M5:102,图7.3 矩阵链乘算法的一个例子,2020/10/5,32,动态规划算法的基本要素,一、最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解. 这种性质称为最优子结构性质. 在分析问题的最优子结构性质时, 所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的, 然后再设法说明在这个假设下可构造出比原问题最优解更好的解, 从而导致矛盾.,2020/10/5,33,动态规划算法的基本要素,一、最优子结构 利用问题的最优子结构性质, 以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解. 最优子结构是问题能用动态规划算法求解的前提. 注意：同一个问题可以有多种方式刻划它的最优子结构, 有些表示方法的求解速度更快(空间占用小, 问题的维度低),2020/10/5,34,二、重叠子问题,递归算法求解问题时, 每次产生的子问题并不总是新问题, 有些子问题被反复计算多次. 这种性质称为子问题的重叠性质. 动态规划算法, 对每一个子问题只解一次, 而后将其解保存在一个表格中, 当再次需要解此子问题时, 只是简单地用常数时间查看一下结果. 通常不同的子问题个数随问题的大小呈多项式增长. 因此用动态规划算法只需要多项式时间, 从而获得较高的解题效率.,2020/10/5,35,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同, 区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看, 避免了相同子问题的重复求解.,m0 private static int lookupChain(int i, int j) if (mij 0) return mij; if (i = j) return 0; int u = lookupChain(i+1, j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = lookupChain(i, k) + lookupChain(k+1, j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; ,2020/10/5,36,The Dynamic Programming Paradigm动态规划范式,适用范围 多阶段决策的最优化问题 最优解满足最优性原理 子问题的重叠性 基本思想 将原问题分解为子问题来求解, 求出子问题的解并由此来构造出原问题的解(即自下而上来求解). 在求解过程中不必回头看以前的情况. 设计一个动态规划算法有四个步骤.,2020/10/5,37,Basic steps of dynamic programming动态规划的基本步骤,找出最优解的性质, 并刻划其结构特征. 递归地定义最优值. 以自底向上的方式计算出最优值. 根据计算最优值时得到的信息, 构造最优解.,2020/10/5,38,The all-pairs shortest path problems所有点对的最短路径问题,设G=(V, E)是一个有向图, 其中的每条边(i, j)有一个非负的长度li, j, 如果顶点i到顶点j没有边, 则li, j=. 问题是要找出从每个顶点到其他所有顶点的距离. 顶点x到顶点y的距离是指x到y 的最短路径长度.,2020/10/5,39,The all-pairs shortest path problems,假设V=1, 2, ., n, 设i和j是V中两个不同的顶点. 定义dki, j是从i到j不经过k+1, k+2, ., k+n中任何顶点的最短路径的长度. di, j0=li, j, di, j1表示i, j最多经过顶点1的最短路径 给出上述定义后, 可以递归的计算：,2020/10/5,40,迭代公式,2020/10/5,41,Algorithm 7.3 FLOYD Input: An nn matrix l1.n, 1.n is the length of the edge (i, j) in a directed graph G=(1, 2, ., n, E) Output: A matrix D with Di, j=the distance from i to j 1. Dl copy the input matrix l into D 2. for k1 to n 3. for i1 to n 4. for j1 to n 5. Di, j=minDi, j, Di, k+Dk, j 6. end for 7. end for 8. end for Time: (n3) Space: (n2),2020/10/5,42,Knapsack problem背包问题,设U=u1, ., un是一个准备放入容量为C的背包中的n项物品的集合. 对于1jn, 令sj和vi分别表示第j项物品的体积和价值. 要解决的问题是用U中的一些物品来装满背包, 这些物品的总体积不超过C, 然而要使它们的总价值最大.,2020/10/5,43,背包问题的递推公式,设Vi, j用来表示从前i项u1.ui中取出来的装入体积为j的背包的物品的最大值. 这样要寻求的是Vn, C. 显然V0, j和Vi, 0都是等于0的. 当i, j0时, 有如下结论: 观察结论7.2 Vi, j是下面两个量的最大值 Vi-1, j: 仅用最优的方法取自u1.ui-1的物品去装体积为j的背包所得到的最大价值. Vi-1, j-si+vi:用最优的方法取自u1.ui-1的物品去装体积为j-si的背包所得到的最大价值加上物品ui的价值.,2020/10/5,44,背包问题的递推公式,递推公式如下：,2020/10/5,45,Algorithm 7.4 KNAPSACK Input: A set of items U=u1.un with sizes s1, ., sn and values v1, ., vn and a knapsack capacity C Output: The maximum value of the problem 1. for i0 to n 2. Vi, 00 3. end for 4. for j0 to C 5. V0, j0 6. end for 7. for i1 to n 8. for j1 to C 9. Vi, jVi-1, j 10. if sij then Vi, jmaxVi, j, Vi-1, j-si+vi 11. end for 12. end for 13. return Vn, C,2020/10/5,46,分析,Time: (nC) Space: (C) But it is a pseudopolynomial time algorithm! 当背包容量c很大时, 算法需要的计算时间较多. 例如, 当c2n时, 算法需要(n2n)计算时间.,2020/10/5,47,C=9 s1=2 s2=3 s3=4 s4=5 v1=3 v2=4 v3=5 v4=7,图7.5 背包问题算法的一个例子,2020/10/5,48,Homework,7.5 7.7 7.11 7.22,