动态规划算法-课件

Chapter7动态规划DynamicProgramming12/23/20221Chapter7动态规划DynamicProgrammiWhatisdynamicprogramming与分治法类似,动态规划也是通过组合子问题的解来求解问题.分治算法将问题划分成独立子问题,递归地解决这些子问题,然后组合这些子问题的解来求解原始问题.Ifthesesubproblemsarenotindependent,whatwillhappen?12/23/20222Whatisdynamicprogramming与分治算法总体思想动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=12/23/20223算法总体思想动态规划算法与分治法类似,其基本思想也是将待求但是经分解得到的子问题往往不是互相独立的.不同子问题的数目常常只有多项式量级.在用分治法求解时,有些子问题被重复计算了许多次.算法总体思想nT(n)=n/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)n/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)12/23/20224但是经分解得到的子问题往往不是互相独立的.不同子问题的数目算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Thosewhocannotrememberthepastaredoomedtorepeatit.(无法记取教训者必重蹈覆辙

)-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法.12/23/20225算法总体思想n=n/2T(n/4)T(n/4)T(n/4)TFibonaccisequence(序列)Fibonacci序列定义如下：1.proceduref(n)2.ifn=1orn=2thenreturn13.elsereturnf(n-1)+f(n-2)这种递归形式有简洁、容易书写和容易查错等优点,最主要是它的抽象性.但是它远不是有效的算法.算法复杂性:(n)Why???12/23/20226Fibonaccisequence(序列)FibonaccFibonaccisequence分析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)12/23/20227Fibonaccisequence分析f(n)=f(n二项式系数的计算有效计算上式的方法是按行构造帕斯卡三角形12/23/20228二项式系数的计算有效计算上式的方法是按行构造帕斯卡三角形12Whatisdynamicprogramming

什么是动态规划？当子问题发生重叠时,分治法做了很多不必要的工作——重复对重叠的子问题进行求解.动态规划算法对每个子问题求解一次,然后将结果保存在一张表里面,这样可以避免每个已求解子问题的重复计算.对于Fibonacci序列,一个明显的方法是从f(1)开始自底向上地计算到f(n),只需要(n)时间和(1)空间.和前面的方法相比,可以很大程度降低时间复杂度.12/23/20229Whatisdynamicprogramming

什么Thelongestcommonsubsequenceproblem最长公共子序列问题在字母表上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度.这里A=a1a2...an的子序列的一个形式为ai1ai2...aik的字符串,其中每个ij在1到n之间,并且1i1<i2<...<ikn蛮力法:列举A所以的2n个子序列,对于每一子序列在(m)时间内来确定它是否也是B的子序列.很明显,此算法的时间复杂的为(m*2n).12/23/202210Thelongestcommonsubsequence递推公式为了使用动态规划技术,首先推导一个求最长公共子序列长度的递推公式.令A=a1a2...an和B=b1b2...bm令L[i,j]表示a1a2...ai和b1b2...bj的最长公共子序列的长度(i,j可能是0,此时a1a2...ai和b1b2...bj中至少一个为空).可得如下结论：12/23/202211递推公式为了使用动态规划技术,首先推导一个求最长公共子序列递推公式观察结论7.1如果i和j都大于0,那么若ai=bj,L[i,j]=L[i-1,j-1]+1若aibj,L[i,j]=max{L[i,j-1],+L[i-1,j]}可得如下公式：12/23/202212递推公式观察结论7.1如果i和j都大于0,那么12/1现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对i和j的值，0in，0jm，我们用一个(n+1)×(m+1)表来计算L[i,j]的值，只需要用上面的公式逐行地填表L[0…n,0…m]。算法如下：12/23/202213现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对Algorithm7.1LCSInput:TwostringsAandBoflengthnandm,respectively,overanalphabetOutput:ThelengthofthelongestcommonsubsequenceofAandB

1.fori0ton2.L[i,0]03.endfor4.forj0tom5.L[0,j]06.endfor

12/23/202214Algorithm7.1LCS12/17/2022147.fori1ton8.forj1tom9.ifai=bjthenL[i,j]L[i-1,j-1]+110.elseL[i,j]max{L[i,j-1],L[i-1,j]}11.endif12.endfor13.endfor14.returnL[n,m]12/23/2022157.fori1ton12/17/20221定理7.1最长公共子序列问题的最优解能够在(nm)时间和(min{m,n})空间内得到.？12/23/20221612/17/202216A=“xyxxzxyzxy”B=“zxzyyzxxyxxz”01z2x3z4y5y6z7x8x9y10x11x12z000000000000001x00111111111112y00112222222223x00112223333334x00112223444445z01122233444456x01222234445557y01223334455558z01233344455569x012333455566610y0123444556666图7.1最长公共子序列问题的一个例子12/23/202217A=“xyxxzxyzxy”B=“zxzyyzxxyxxAlgorithm7.1proLCS1.fori0ton2.L[i,0]03.endfor4.forj0tom5.L[0,j]06.endfor7.fori1ton8.forj1tom9.ifai=bjthenL[i,j]L[i-1,j-1]+1,b[i,j]”\”

12/23/202218Algorithm7.1proLCS12/17/202210.else11.ifL[i-1,j]L[i,j-1]then12.L[i,j]L[i-1,j],b[i,j]””13.else14.L[i,j]L[i,j-1],b[i,j]””15.endif16.endif17.endfor18.endfor19.returnL[n,m]andb[n,m]12/23/20221910.else12/17/202219print-LCS(b,A,i,j)1.ifi=0orj=0thenreturn2.ifb[i,j]=”\”then3.print-LCS(b,A,i-1,j-1)4.printai5.else6.ifb[i,j]=””thenprint-LCS(b,A,i-1,j)7.elseprint-LCS(b,A,i,j-1)8.endif12/23/202220print-LCS(b,A,i,j)12/17/20212/23/20222112/17/202221算法的改进在算法lcs和print-LCS中,可进一步将数组b省去.事实上,数组元素L[i][j]的值仅由L[i-1][j-1],L[i-1][j]和L[i][j-1]这3个数组元素的值所确定.对于给定的数组元素L[i][j],可以不借助于数组b而仅借助于L本身确定L[i][j]的值是由L[i-1][j-1],L[i-1][j]和L[i][j-1]中哪一个值所确定的.12/23/202222算法的改进在算法lcs和print-LCS中,可进一步将数算法的改进如果只需要计算最长公共子序列的长度,则算法的空间需求可大大减少.事实上,在计算L[i][j]时,只用到数组L的第i行和第i-1行.因此,用2行的数组空间就可以计算出最长公共子序列的长度.进一步的分析还可将空间需求减至O(min(m,n)).12/23/202223算法的改进如果只需要计算最长公共子序列的长度,则算法的空间Matrixchainmultiplication矩阵链相乘设有4个矩阵A,B,C,D,它们的维数分别是A:5010B:1040C:4030D:305,共有5种加括号的方式：(A((BC)D))乘法次数:16000(A(B(CD)))乘法次数:10500((AB)(CD))乘法次数:36000(((AB)C)D)乘法次数:87500((A(BC))D)乘法次数:3450012/23/202224Matrixchainmultiplication矩阵链Matrixchainmultiplication矩阵链相乘一般情况下,n个矩阵链M1M2...Mn相乘的耗费,取决于n-1个乘法执行的顺序(结合方式).蛮力算法:计算出每一种可能顺序的数量乘法次数.时间复杂度是：算法复杂度分析：对于n个矩阵的连乘积,设其不同的计算次序为P(n).由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：12/23/202225Matrixchainmultiplication矩阵链假设我们有n+1维数r1,r2,...,rn+1,这里ri和ri+1分别是矩阵Mi的行数和列数,1in.我们将用Mi,j记MiMi+1...Mj的乘积,我们还假设链Mi,j的乘法的最小耗费用数量乘法的次数来度量,记为C[i,j].对于给定的一对索引i和j,1i<jn,Mi,j可用如下方法计算:设k是i+1和j之间的一个索引,计算两个矩阵Mi,k-1=MiMi+1…Mk-1和Mk,j=MkMk+1…Mj,那么Mi,j=Mi,k-1Mk,j显然,用这种方法计算Mi,j的总耗费,是计算Mi,k-1的耗费加上计算Mk,j的耗费,再加上Mi,k-1乘以Mk,j的耗费(rirkrj+1),因此得到了如下的公式:12/23/202226假设我们有n+1维数r1,r2,...,rn+1,这Particularly,如果采用自顶向下的方式不能得到有效的算法,导致巨大的重复递归调用.12/23/20222712/17/202227Illustrationofmatrixchainmultiplication矩阵链乘图示12/23/202228IllustrationofmatrixchainmAlgorithm7.2MATCHAINInput:Anarrayr[1..n+1]ofpositiveintegerscorrespondingtothedimensionsofachainofnmatrices,wherer[1..n]arethenumberofrowsinthenmatricesandr[n+1]isthenumberofcolumnsinMnOutput:Theleastnumberofscalarmultiplicationsrequiredtomultiplythenmatrices1.fori1ton{Fillindiagonald0}2.C[i,i]03.endfor4.ford1ton-1{Fillindiagonalsd1todn-1}5.fori1ton-d{Fillinentriesindiagonaldi}6.ji+ment:ThenextthreelinescomputesC[i,j]8.C[i,j]9.forki+1toj10.C[i,j]min{C[i,j],C[i,k-1]+C[k,j]+r[i]r[k]r[j+1]}11.endfor12.endfor13.endfor14.returnC[1,n]12/23/202229Algorithm7.2MATCHAIN12/17/20分析算法matrixChain的主要计算量取决于算法中对r,i和k的3重循环.循环体内的计算量为O(1),而3重循环的总次数为定理7.2一个由n个矩阵组成的链相乘,它所需的数量乘法最少次数可以在(n3)时间和(n2)空间内找出.12/23/202230分析算法matrixChain的主要计算量取决于算法中对r,M1:510M2:104M3:46M2:610M5:102C[1,1]=0C[1,2]=200C[1,3]=320C[1,4]=620C[1,5]=348C[2,2]=0C[2,3]=240C[2,4]=640C[2,5]=248C[3,3]=0C[3,4]=240C[3,5]=168C[4,4]=0C[4,5]=120C[5,5]=0图7.3矩阵链乘算法的一个例子12/23/202231M1:510M2:104M3:46M2:61动态规划算法的基本要素一、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解.这种性质称为最优子结构性质.在分析问题的最优子结构性质时,所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾.12/23/202232动态规划算法的基本要素一、最优子结构12/17/202232动态规划算法的基本要素一、最优子结构利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解.最优子结构是问题能用动态规划算法求解的前提.注意：同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)12/23/202233动态规划算法的基本要素一、最优子结构12/17/202233二、重叠子问题递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次.这种性质称为子问题的重叠性质.动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果.通常不同的子问题个数随问题的大小呈多项式增长.因此用动态规划算法只需要多项式时间,从而获得较高的解题效率.12/23/202234二、重叠子问题递归算法求解问题时,每次产生的子问题并不总是三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解.m0privatestaticintlookupChain(inti,intj){

if(m[i][j]>0)returnm[i][j];

if(i==j)return0;intu=lookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;

for(intk=i+1;k<j;k++){intt=lookupChain(i,k)+lookupChain(k+1,j)+p[i-1]*p[k]*p[j];

if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;

returnu;}12/23/202235三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相TheDynamicProgrammingParadigm动态规划范式适用范围

多阶段决策的最优化问题最优解满足最优性原理子问题的重叠性基本思想

将原问题分解为子问题来求解,求出子问题的解并由此来构造出原问题的解(即自下而上来求解).在求解过程中不必回头看以前的情况.设计一个动态规划算法有四个步骤.12/23/202236TheDynamicProgrammingParadiBasicstepsofdynamicprogramming动态规划的基本步骤找出最优解的性质,并刻划其结构特征.递归地定义最优值.以自底向上的方式计算出最优值.根据计算最优值时得到的信息,构造最优解.12/23/202237BasicstepsofdynamicprogramTheall-pairsshortestpathproblems

所有点对的最短路径问题设G=(V,E)是一个有向图,其中的每条边(i,j)有一个非负的长度l[i,j],如果顶点i到顶点j没有边,则l[i,j]=.问题是要找出从每个顶点到其他所有顶点的距离.顶点x到顶点y的距离是指x到y的最短路径长度.12/23/202238Theall-pairsshortestpathprTheall-pairsshortestpathproblems假设V={1,2,...,n},设i和j是V中两个不同的顶点.定义dk[i,j]是从i到j不经过{k+1,k+2,...,k+n}中任何顶点的最短路径的长度.d[i,j]0=l[i,j],d[i,j]1表示i,j最多经过顶点1的最短路径…给出上述定义后,可以递归的计算：12/23/202239Theall-pairsshortestpathpr迭代公式12/23/202240迭代公式12/17/202240Algorithm7.3FLOYDInput:Annnmatrixl[1..n,1..n]isthelengthoftheedge(i,j)inadirectedgraphG=({1,2,...,n},E)Output:AmatrixDwithD[i,j]=thedistancefromitoj1.Dl{copytheinputmatrixlintoD}2.fork1ton3.fori1ton4.forj1ton5.D[i,j]=min{D[i,j],D[i,k]+D[k,j]}6.endfor7.endfor8.endforTime:(n3)Space:(n2)12/23/202241Algorithm7.3FLOYD12/17/20224Knapsackproblem背包问题设U={u1,...,un}是一个准备放入容量为C的背包中的n项物品的集合.对于1jn,令sj和vi分别表示第j项物品的体积和价值.要解决的问题是用U中的一些物品来装满背包,这些物品的总体积不超过C,然而要使它们的总价值最大.12/23/202242Knapsackproblem背包问题设U={u1,..背包问题的递推公式设V[i,j]用来表示从前i项{u1...ui}中取出来的装入体积为j的背包的物品的最大值.这样要寻求的是V[n,C].显然V[0,j]和V[i,0]都是等于0的.当i,j>0时,有如下结论:观察结论7.2V[i,j]是下面两个量的最大值V[i-1,j]:仅用最优的方法取自{u1...ui-1}的物品去装体积为j的背包所得到的最大价值.V[i-1,j-si]+vi:用最优的方法取自{u1...ui-1}的物品去装体积为j-si的背包所得到的最大价值加上物品ui的价值.12/23/202243背包问题的递推公式设V[i,j]用来表示从前i项{u1..背包问题的递推公式递推公式如下：12/23/202244背包问题的递推公式递推公式如下：12/17/202244Algorithm7.4KNAPSACKInput:AsetofitemsU={u1...un}withsizess1,...,snandvaluesv1,...,vnandaknapsackcapacityCOutput:Themaximumvalueoftheproblem1.fori0ton2.V[i,0]03.endfor4.forj0toC5.V[0,j]06.endfor7.fori1ton8.forj1toC9.V[i,j]V[i-1,j]10.ifsijthenV[i,j]max{V[i,j],V[i-1,j-si]+vi}11.endfor12.endfor13.returnV[n,C]12/23/202245Algorithm7.4KNAPSACK12/17/20分析Time:(nC)Space:(C)Butitisapseudopolynomialtimealgorithm!当背包容量c很大时,算法需要的计算时间较多.例如,当c>2n时,算法需要Ω(n2n)计算时间.12/23/202246分析Time:(nC)12/17/202246C=9s1=2s2=3s3=4s4=5

v1=3v2=4v3=5v4=7012345678900000000000100333333332003447777730034578991240034578101112图7.5背包问题算法的一个例子12/23/202247C=9s1=2s2=3s3=4sHomework17.22

12/23/202248Homework7.512/17/202248Chapter7动态规划DynamicProgramming12/23/202249Chapter7动态规划DynamicProgrammiWhatisdynamicprogramming与分治法类似,动态规划也是通过组合子问题的解来求解问题.分治算法将问题划分成独立子问题,递归地解决这些子问题,然后组合这些子问题的解来求解原始问题.Ifthesesubproblemsarenotindependent,whatwillhappen?12/23/202250Whatisdynamicprogramming与分治算法总体思想动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=12/23/202251算法总体思想动态规划算法与分治法类似,其基本思想也是将待求但是经分解得到的子问题往往不是互相独立的.不同子问题的数目常常只有多项式量级.在用分治法求解时,有些子问题被重复计算了许多次.算法总体思想nT(n)=n/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)n/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)12/23/202252但是经分解得到的子问题往往不是互相独立的.不同子问题的数目算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)Thosewhocannotrememberthepastaredoomedtorepeatit.(无法记取教训者必重蹈覆辙

)-----GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,就可以避免大量重复计算,从而得到多项式时间算法.12/23/202253算法总体思想n=n/2T(n/4)T(n/4)T(n/4)TFibonaccisequence(序列)Fibonacci序列定义如下：1.proceduref(n)2.ifn=1orn=2thenreturn13.elsereturnf(n-1)+f(n-2)这种递归形式有简洁、容易书写和容易查错等优点,最主要是它的抽象性.但是它远不是有效的算法.算法复杂性:(n)Why???12/23/202254Fibonaccisequence(序列)FibonaccFibonaccisequence分析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)12/23/202255Fibonaccisequence分析f(n)=f(n二项式系数的计算有效计算上式的方法是按行构造帕斯卡三角形12/23/202256二项式系数的计算有效计算上式的方法是按行构造帕斯卡三角形12Whatisdynamicprogramming

什么是动态规划？当子问题发生重叠时,分治法做了很多不必要的工作——重复对重叠的子问题进行求解.动态规划算法对每个子问题求解一次,然后将结果保存在一张表里面,这样可以避免每个已求解子问题的重复计算.对于Fibonacci序列,一个明显的方法是从f(1)开始自底向上地计算到f(n),只需要(n)时间和(1)空间.和前面的方法相比,可以很大程度降低时间复杂度.12/23/202257Whatisdynamicprogramming

什么Thelongestcommonsubsequenceproblem最长公共子序列问题在字母表上,分别给出两个长度为n和m的字符串A和B,确定在A和B中最长公共子序列的长度.这里A=a1a2...an的子序列的一个形式为ai1ai2...aik的字符串,其中每个ij在1到n之间,并且1i1<i2<...<ikn蛮力法:列举A所以的2n个子序列,对于每一子序列在(m)时间内来确定它是否也是B的子序列.很明显,此算法的时间复杂的为(m*2n).12/23/202258Thelongestcommonsubsequence递推公式为了使用动态规划技术,首先推导一个求最长公共子序列长度的递推公式.令A=a1a2...an和B=b1b2...bm令L[i,j]表示a1a2...ai和b1b2...bj的最长公共子序列的长度(i,j可能是0,此时a1a2...ai和b1b2...bj中至少一个为空).可得如下结论：12/23/202259递推公式为了使用动态规划技术,首先推导一个求最长公共子序列递推公式观察结论7.1如果i和j都大于0,那么若ai=bj,L[i,j]=L[i-1,j-1]+1若aibj,L[i,j]=max{L[i,j-1],+L[i-1,j]}可得如下公式：12/23/202260递推公式观察结论7.1如果i和j都大于0,那么12/1现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对i和j的值，0in，0jm，我们用一个(n+1)×(m+1)表来计算L[i,j]的值，只需要用上面的公式逐行地填表L[0…n,0…m]。算法如下：12/23/202261现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对Algorithm7.1LCSInput:TwostringsAandBoflengthnandm,respectively,overanalphabetOutput:ThelengthofthelongestcommonsubsequenceofAandB

1.fori0ton2.L[i,0]03.endfor4.forj0tom5.L[0,j]06.endfor

12/23/202262Algorithm7.1LCS12/17/2022147.fori1ton8.forj1tom9.ifai=bjthenL[i,j]L[i-1,j-1]+110.elseL[i,j]max{L[i,j-1],L[i-1,j]}11.endif12.endfor13.endfor14.returnL[n,m]12/23/2022637.fori1ton12/17/20221定理7.1最长公共子序列问题的最优解能够在(nm)时间和(min{m,n})空间内得到.？12/23/20226412/17/202216A=“xyxxzxyzxy”B=“zxzyyzxxyxxz”01z2x3z4y5y6z7x8x9y10x11x12z000000000000001x00111111111112y00112222222223x00112223333334x00112223444445z01122233444456x01222234445557y01223334455558z01233344455569x012333455566610y0123444556666图7.1最长公共子序列问题的一个例子12/23/202265A=“xyxxzxyzxy”B=“zxzyyzxxyxxAlgorithm7.1proLCS1.fori0ton2.L[i,0]03.endfor4.forj0tom5.L[0,j]06.endfor7.fori1ton8.forj1tom9.ifai=bjthenL[i,j]L[i-1,j-1]+1,b[i,j]”\”

12/23/202266Algorithm7.1proLCS12/17/202210.else11.ifL[i-1,j]L[i,j-1]then12.L[i,j]L[i-1,j],b[i,j]””13.else14.L[i,j]L[i,j-1],b[i,j]””15.endif16.endif17.endfor18.endfor19.returnL[n,m]andb[n,m]12/23/20226710.else12/17/202219print-LCS(b,A,i,j)1.ifi=0orj=0thenreturn2.ifb[i,j]=”\”then3.print-LCS(b,A,i-1,j-1)4.printai5.else6.ifb[i,j]=””thenprint-LCS(b,A,i-1,j)7.elseprint-LCS(b,A,i,j-1)8.endif12/23/202268print-LCS(b,A,i,j)12/17/20212/23/20226912/17/202221算法的改进在算法lcs和print-LCS中,可进一步将数组b省去.事实上,数组元素L[i][j]的值仅由L[i-1][j-1],L[i-1][j]和L[i][j-1]这3个数组元素的值所确定.对于给定的数组元素L[i][j],可以不借助于数组b而仅借助于L本身确定L[i][j]的值是由L[i-1][j-1],L[i-1][j]和L[i][j-1]中哪一个值所确定的.12/23/202270算法的改进在算法lcs和print-LCS中,可进一步将数算法的改进如果只需要计算最长公共子序列的长度,则算法的空间需求可大大减少.事实上,在计算L[i][j]时,只用到数组L的第i行和第i-1行.因此,用2行的数组空间就可以计算出最长公共子序列的长度.进一步的分析还可将空间需求减至O(min(m,n)).12/23/202271算法的改进如果只需要计算最长公共子序列的长度,则算法的空间Matrixchainmultiplication矩阵链相乘设有4个矩阵A,B,C,D,它们的维数分别是A:5010B:1040C:4030D:305,共有5种加括号的方式：(A((BC)D))乘法次数:16000(A(B(CD)))乘法次数:10500((AB)(CD))乘法次数:36000(((AB)C)D)乘法次数:87500((A(BC))D)乘法次数:3450012/23/202272Matrixchainmultiplication矩阵链Matrixchainmultiplication矩阵链相乘一般情况下,n个矩阵链M1M2...Mn相乘的耗费,取决于n-1个乘法执行的顺序(结合方式).蛮力算法:计算出每一种可能顺序的数量乘法次数.时间复杂度是：算法复杂度分析：对于n个矩阵的连乘积,设其不同的计算次序为P(n).由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：12/23/202273Matrixchainmultiplication矩阵链假设我们有n+1维数r1,r2,...,rn+1,这里ri和ri+1分别是矩阵Mi的行数和列数,1in.我们将用Mi,j记MiMi+1...Mj的乘积,我们还假设链Mi,j的乘法的最小耗费用数量乘法的次数来度量,记为C[i,j].对于给定的一对索引i和j,1i<jn,Mi,j可用如下方法计算:设k是i+1和j之间的一个索引,计算两个矩阵Mi,k-1=MiMi+1…Mk-1和Mk,j=MkMk+1…Mj,那么Mi,j=Mi,k-1Mk,j显然,用这种方法计算Mi,j的总耗费,是计算Mi,k-1的耗费加上计算Mk,j的耗费,再加上Mi,k-1乘以Mk,j的耗费(rirkrj+1),因此得到了如下的公式:12/23/202274假设我们有n+1维数r1,r2,...,rn+1,这Particularly,如果采用自顶向下的方式不能得到有效的算法,导致巨大的重复递归调用.12/23/20227512/17/202227Illustrationofmatrixchainmultiplication矩阵链乘图示12/23/202276IllustrationofmatrixchainmAlgorithm7.2MATCHAINInput:Anarrayr[1..n+1]ofpositiveintegerscorrespondingtothedimensionsofachainofnmatrices,wherer[1..n]arethenumberofrowsinthenmatricesandr[n+1]isthenumberofcolumnsinMnOutput:Theleastnumberofscalarmultiplicationsrequiredtomultiplythenmatrices1.fori1ton{Fillindiagonald0}2.C[i,i]03.endfor4.ford1ton-1{Fillindiagonalsd1todn-1}5.fori1ton-d{Fillinentriesindiagonaldi}6.ji+ment:ThenextthreelinescomputesC[i,j]8.C[i,j]9.forki+1toj10.C[i,j]min{C[i,j],C[i,k-1]+C[k,j]+r[i]r[k]r[j+1]}11.endfor12.endfor13.endfor14.returnC[1,n]12/23/202277Algorithm7.2MATCHAIN12/17/20分析算法matrixChain的主要计算量取决于算法中对r,i和k的3重循环.循环体内的计算量为O(1),而3重循环的总次数为定理7.2一个由n个矩阵组成的链相乘,它所需的数量乘法最少次数可以在(n3)时间和(n2)空间内找出.12/23/202278分析算法matrixChain的主要计算量取决于算法中对r,M1:510M2:104M3:46M2:610M5:102C[1,1]=0C[1,2]=200C[1,3]=320C[1,4]=620C[1,5]=348C[2,2]=0C[2,3]=240C[2,4]=640C[2,5]=248C[3,3]=0C[3,4]=240C[3,5]=168C[4,4]=0C[4,5]=120C[5,5]=0图7.3矩阵链乘算法的一个例子12/23/202279M1:510M2:104M3:46M2:61动态规划算法的基本要素一、最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解.这种性质称为最优子结构性质.在分析问题的最优子结构性质时,所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的,然后再设法说明在这个假设下可构造出比原问题最优解更好的解,从而导致矛盾.12/23/202280动态规划算法的基本要素一、最优子结构12/17/202232动态规划算法的基本要素一、最优子结构利用问题的最优子结构性质,以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解.最优子结构是问题能用动态规划算法求解的前提.注意：同一个问题可以有多种方式刻划它的最优子结构,有些表示方法的求解速度更快(空间占用小,问题的维度低)12/23/202281动态规划算法的基本要素一、最优子结构12/17/202233二、重叠子问题递归算法求解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次.这种性质称为子问题的重叠性质.动态规划算法,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此子问题时,只是简单地用常数时间查看一下结果.通常不同的子问题个数随问题的大小呈多项式增长.因此用动态规划算法只需要多项式时间,从而获得较高的解题效率.12/23/202282二、重叠子问题递归算法求解问题时,每次产生的子问题并不总是三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看,避免了相同子问题的重复求解.m0privatestaticintlookupChain(inti,intj){

if(m[i][j]>0)returnm[i][j];

if(i==j)return0;intu=lookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;

for(intk=i+1;k<j;k++){intt=lookupChain(i,k)+lookupChain(k+1,j)+p[i-1]*p[k]*p[j];

if(t<u){u=t;s[i][j]=k;}}m[i][j]=u;

returnu;}12/23/202283三、备忘录方法备忘录方法的控制结构与直接递归方法的控制结构相TheDynamicProgrammingParadigm动态规划范式适用范围

多阶段决策的最优化问题最优解满足最优性原理子问题的重叠性基本思想

将原问题分解为子问题来求解,求出子问题的解并由此来构造出原问题的解(即自下而上来求解).在求解过程中不必回头看以前的情况.设计一个动态规划算法有四个步骤.12/23/202284TheDynamicProgrammingParadiBasicstepsofdynamicprogramming动态规划的基本步骤找出最优解的性质,并刻划其结构特征.递归地定义最优值.以自底向上的方式计算出最优值.根据计算最优值时得到的信息,构造最优解.12/23/202285BasicstepsofdynamicprogramTheall-pairsshortestpathproblems

所有点对的最短路径问题设G=(V,E)是一个有向图,其中的每条边(i,j)有一个非负的长度l[i,j],如果顶点i到顶点j没有边,则l[i,j]=.问题是要找出从每个顶点到其他所有顶点的距离.顶点x到顶点y的距离是指x到y的最短路径长度.12/23/202286Theall-pairsshortestpathprTheall-pairsshortestpathproblems假设V=