动态规划算法.ppt
动态规划算法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望What is dynamic programmingn与分治法类似与分治法类似,动态规划也是通过组合子问题动态规划也是通过组合子问题的解来求解问题的解来求解问题.n分治算法将问题划分成独立子问题分治算法将问题划分成独立子问题,递归地解决递归地解决这些子问题这些子问题,然后组合这些子问题的解来求解原然后组合这些子问题的解来求解原始问题始问题.nIf these subproblems are not independent,what will happen?11/1/20222算法总体思想算法总体思想n动态规划算法与分治法类似动态规划算法与分治法类似,其基本思想也是其基本思想也是将待求解问题分解成若干个子问题将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n/2)T(n)=11/1/20223n但是经分解得到的子问题往往不是互相独立的但是经分解得到的子问题往往不是互相独立的.不同不同子问题的数目常常只有多项式量级子问题的数目常常只有多项式量级.在用分治法求解在用分治法求解时时,有些子问题被重复计算了许多次有些子问题被重复计算了许多次.算法总体思想算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)11/1/20224算法总体思想算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Those who cannot remember the past Those who cannot remember the past are doomed to repeat it.are doomed to repeat it.(无法记取教训者必重蹈覆辙无法记取教训者必重蹈覆辙无法记取教训者必重蹈覆辙无法记取教训者必重蹈覆辙)-George Santayana,-George Santayana,The life of ReasonThe life of Reason,Book I:Introduction and Book I:Introduction and Reason in Common Reason in Common Sense(1905)Sense(1905)n如果能够保存已解决的子问题的答案如果能够保存已解决的子问题的答案,而在需要时再而在需要时再找出已求得的答案找出已求得的答案,就可以避免大量重复计算就可以避免大量重复计算,从而从而得到多项式时间算法得到多项式时间算法.11/1/20225Fibonacci sequence(序列序列)nFibonacci序列定义如下：序列定义如下：q1.procedure f(n)q2.if n=1 or n=2 then return 1q3.else return f(n-1)+f(n-2)n这种递归形式有简洁、容易书写和容易查错等这种递归形式有简洁、容易书写和容易查错等优点优点,最主要是它的抽象性最主要是它的抽象性.n但是它远不是有效的算法但是它远不是有效的算法.q算法复杂性算法复杂性:(n)qWhy?11/1/20226Fibonacci sequence分析分析nf(n)=f(n-1)+f(n-2)n =2f(n-2)+f(n-3)n =3f(n-3)+2f(n-4)n =5f(n-4)+3f(n-5)11/1/20227二项式系数的计算二项式系数的计算有效计算上式的方法是按行构造帕斯卡三角形有效计算上式的方法是按行构造帕斯卡三角形11/1/20228What is dynamic programming什么是动态规划？什么是动态规划？n当子问题发生当子问题发生重叠重叠时时,分治法做了很多不必要的分治法做了很多不必要的工作工作重复对重叠的子问题进行求解重复对重叠的子问题进行求解.n动态规划算法对每个子问题求解一次动态规划算法对每个子问题求解一次,然后将结然后将结果保存在一张表里面果保存在一张表里面,这样可以避免每个已求解这样可以避免每个已求解子问题的重复计算子问题的重复计算.n对于对于Fibonacci序列序列,一个明显的方法是从一个明显的方法是从f(1)开开始自底向上地计算到始自底向上地计算到f(n),只需要只需要(n)时间和时间和(1)空间空间.n和前面的方法相比和前面的方法相比,可以很大程度降低时间复杂可以很大程度降低时间复杂度度.11/1/20229The longest common subsequence problem最长公共子序列问题最长公共子序列问题n在字母表在字母表 上上,分别给出两个长度为分别给出两个长度为n和和m的字符的字符串串A和和B,确定在确定在A和和B中最长公共子序列的长度中最长公共子序列的长度.q这里这里A=a1a2.an的子序列的一个形式为的子序列的一个形式为ai1ai2.aik的的字符串字符串,其中每个其中每个ij在在1到到n之间之间,并且并且1 i1i2.ik nn蛮力法蛮力法:列举列举A所以的所以的2n个子序列个子序列,对于每一子对于每一子序列在序列在(m)时间内来确定它是否也是时间内来确定它是否也是B的子序列的子序列.q很明显很明显,此算法的时间复杂的为此算法的时间复杂的为(m*2n).11/1/202210递推公式递推公式n为了使用动态规划技术为了使用动态规划技术,首先推导一个求最长首先推导一个求最长公共子序列长度的递推公式公共子序列长度的递推公式.q令令A=a1a2.an和和B=b1b2.bmq令令Li,j表示表示a1a2.ai和和b1b2.bj的最长公共的最长公共子序列的长度子序列的长度(i,j可能是可能是0,此时此时a1a2.ai和和b1b2.bj中至少一个为空中至少一个为空).可得如下结论：可得如下结论：11/1/202211递推公式递推公式n观察结论观察结论7.1 如果如果i和和j都大于都大于0,那么那么 q若若ai=bj,Li,j=Li-1,j-1+1q若若ai bj,Li,j=maxLi,j-1,+Li-1,jn可得如下公式：可得如下公式：11/1/202212n现在可以直接用动态规划技术来求解最长现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对公共子序列问题。对每一对i和和j的值，的值，0 i n，0 j m，我们用一个，我们用一个(n+1)(m+1)表来计算表来计算Li,j的值，只需要用上面的公式的值，只需要用上面的公式逐行地填表逐行地填表L0n,0m。算法如下：。算法如下：11/1/202213Algorithm 7.1 LCSInput: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 11/1/202214 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,m11/1/202215n定理定理7.1 最长公共子序列问题的最长公共子序列问题的最优解能够在最优解能够在(nm)时间和时间和(minm,n)空间内得到空间内得到.n？11/1/202216A=“xyxxzxyzxy”B=“zxzyyzxxyxxz”01z2x3z4y5y6z7x8x9y10 x11x12z000000000000001x00111111111112y00112222222223x00112223333334x00112223444445z01122233444456x01222234445557y01223334455558z01233344455569x012333455566610y0123444556666图图7.1 最长公共子序列问题的一个例子最长公共子序列问题的一个例子11/1/202217Algorithm 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”11/1/202218 10.else 11.if Li-1,j Li,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,m11/1/202219print-LCS(b,A,i,j)1.if i=0 or j=0 then return2.if bi,j=”then3.print-LCS(b,A,i-1,j-1)4.print ai5.else6.if bi,j=”then print-LCS(b,A,i-1,j)7.else print-LCS(b,A,i,j-1)8.end if11/1/20222011/1/202221算法的改进算法的改进n在算法在算法lcs和和print-LCS中中,可进一步将数组可进一步将数组b省省去去.事实上事实上,数组元素数组元素Lij的值仅由的值仅由Li-1j-1,Li-1j和和Lij-1这这3个数组元素的值所确个数组元素的值所确定定.对于给定的数组元素对于给定的数组元素Lij,可以不借助于可以不借助于数组数组b而仅借助于而仅借助于L本身确定本身确定Lij的值是由的值是由Li-1j-1,Li-1j和和Lij-1中哪一个值所确中哪一个值所确定的定的.11/1/202222算法的改进算法的改进n如果只需要计算最长公共子序列的长度如果只需要计算最长公共子序列的长度,则算则算法的空间需求可大大减少法的空间需求可大大减少.事实上事实上,在计算在计算Lij时时,只用到数组只用到数组L的第的第i行和第行和第i-1行行.因此因此,用用2行的数组空间就可以计算出最长公共子序行的数组空间就可以计算出最长公共子序列的长度列的长度.进一步的分析还可将空间需求减至进一步的分析还可将空间需求减至O(min(m,n).11/1/202223Matrix chain multiplication矩阵链相乘矩阵链相乘n设有设有4个矩阵个矩阵A,B,C,D,它们的维数分别是它们的维数分别是A:50 10 B:10 40 C:40 30 D:30 5,共有共有5种加种加括号的方式：括号的方式：n(A(BC)D)q乘法次数乘法次数:16000n(A(B(CD)q乘法次数乘法次数:10500n(AB)(CD)q乘法次数乘法次数:36000n(AB)C)D)q乘法次数乘法次数:87500n(A(BC)D)q乘法次数乘法次数:3450011/1/202224Matrix chain multiplication矩阵链相乘矩阵链相乘n一般情况下一般情况下,n个矩阵链个矩阵链M1M2.Mn相乘的耗费相乘的耗费,取决于取决于n-1个乘法执行的顺序个乘法执行的顺序(结合方式结合方式).n蛮力算法蛮力算法:计算出每一种可能顺序的数量乘法次计算出每一种可能顺序的数量乘法次数数.n时间复杂度是：时间复杂度是：算法复杂度分析：算法复杂度分析：对于对于n个矩阵的连乘积个矩阵的连乘积,设其不同的计算次序为设其不同的计算次序为P(n).由于每种加括号方式都可以分解为两个子矩阵的加括号问题：由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于可以得到关于P(n)的递推式如下：的递推式如下：11/1/202225n假设我们有假设我们有n+1维数维数r1,r2,.,rn+1,这里这里ri和和ri+1分别是矩阵分别是矩阵Mi的行数和列数的行数和列数,1 i n.n我们将用我们将用Mi,j记记MiMi+1.Mj的乘积的乘积,我们还假我们还假设链设链Mi,j的乘法的最小耗费用数量乘法的次数的乘法的最小耗费用数量乘法的次数来度量来度量,记为记为Ci,j.n对于给定的一对索引对于给定的一对索引i和和j,1 i 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 0时时,有如下结论有如下结论:n观察结论观察结论7.2 Vi,j是下面两个量的最大值是下面两个量的最大值qVi-1,j:仅用最优的方法取自仅用最优的方法取自u1.ui-1的物的物品去装体积为品去装体积为j的背包所得到的最大价值的背包所得到的最大价值.qVi-1,j-si+vi:用最优的方法取自用最优的方法取自u1.ui-1的的物品去装体积为物品去装体积为j-si的背包所得到的最大价值加的背包所得到的最大价值加上物品上物品ui的价值的价值.11/1/202243背包问题的递推公式背包问题的递推公式n递推公式如下：递推公式如下：11/1/202244Algorithm 7.4 KNAPSACKInput:A set of items U=u1.un with sizes s1,.,sn and values v1,.,vn and a knapsack capacity COutput: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 si j then Vi,jmaxVi,j,Vi-1,j-si+vi 11.end for 12.end for 13.return Vn,C11/1/202245分析分析nTime:(nC)nSpace:(C)nBut it is a pseudopolynomial time algorithm!n当背包容量当背包容量c很大时很大时,算法需要的计算时间较多算法需要的计算时间较多.例如例如,当当c2n时时,算法需要算法需要(n2n)计算时间计算时间.11/1/202246C=9 s1=2 s2=3 s3=4 s4=5 v1=3 v2=4 v3=5 v4=701234567890000000000010033333333200344777773003457899124003457810 11 12图图7.5 背包问题算法的一个例子背包问题算法的一个例子11/1/202247Homework7.57.77.117.22 11/1/202248
