【20140518版】第四讲_动态规划不可更改

——《算法分析与设计》1第4讲动态规划动态规划算法的基本要素举例1矩阵连乘问题举例2凸多边形最优三角剖分举例3最长公共子序列举例4多段图的最短路径问题举例50-1背包问题举例6资源分配问题——《算法分析与设计》2动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题。区别：经分解得到的子问题往往不是互相独立的。问题：用分治法求解，有些子问题被重复计算多次。——《算法分析与设计》3解决方法保存已解决的子问题的答案，在需要时找出已求得的答案，以避免大量的重复计算，从而得到多项式时间算法。这就是动态规划算法。动态规划的基本步骤：找出最优解的性质，并描述其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。——《算法分析与设计》4动态规划算法举例1：矩阵连乘问题给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的。由于乘法满足结合律，故计算矩阵的连乘可以有不同的计算次序。其计算次序可以用加括号的方式确定。假设有4个矩阵：A,B,C,DA=50×10B=10×40C=40×30D=30×5(A((BC)D))(((AB)C)D)((A(BC))D)乘法：16000乘法：87500乘法：34500(A(B(CD)))((AB)(CD))乘法：10500乘法：36000——《算法分析与设计》5矩阵连乘问题给定n个矩阵{A1,A2,…,An}，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积所需要的乘法次数最少。——《算法分析与设计》6矩阵连乘方法1：枚举法列举出所有可能的计算次序，并计算出每一种计算次序所需要的乘法次数，从中找出一种乘法次数最少的计算次序。时间复杂度分析：对于n个矩阵的连乘，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk结论：P(n)随n的增长呈指数增长，不是高效算法——《算法分析与设计》7矩阵连乘方法1：动态规划算法将矩阵连乘积AiAi+1...Aj简记为A[i:j]，i≤j。考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤kj，则其相应完全加括号方式为：(AiAi+1...Ak）(Ak+1Ak+2...Aj)计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量。——《算法分析与设计》8（1）分析最优解的结构关键特征：计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求最优解的显著特征。——《算法分析与设计》9（2）建立递归关系假设计算A[i:j]（1≤i≤j≤n）所需要的最少乘法次数为m[i,j]，则原问题的最优值为m[1,n]。当i=j时，A[i:j]=Ai，因此m[i,i]=0，i=1,2,…,n当ij时，m[i][j]=m[i][k]+m[k+1][j]+pi-1×pk×pjk∈{i,i+1,...,j-1}可以递归地定义m[i,j]为：——《算法分析与设计》10（3）计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应不同的子问题，因此不同子问题的个数最多只有：)(22nnn可以看出，在递归计算时，有许多子问题被重复计算。——《算法分析与设计》11intrecurMatrixChain(intp[],inti,intj){if(i==j)return0;intu=∞;for(intk=i;kj;k++){intt=recurMatrixChain(p,i,k)+recurMatrixChain(p,k+1,j)+p[i-1]*p[k]*p[j];if(tu){u=t;s[i][j]=k;}}returnu;}——《算法分析与设计》12出现重复计算是该问题用动态规划算法求解的又一个显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，在后面需要时只要简单查找一下，从而可以避免大量地重复计算，最终得到多项式时间的算法。——《算法分析与设计》13计算最优解的动态规划算法假设Ai的维数为pi-1×pi，则输入序列为{p0,p1,p2,...,pn}p[n+1]记录每个矩阵的维数;m[i,j]记录AiAi+1...Aj相乘的代价（乘法次数）;s[i,j]记录取得最优代价所断开的点k——《算法分析与设计》14具有自底向上的计算特征：如果计算m[i,j]，仅需要计算小于j-i+1个的矩阵乘积。即计算长度为L的矩阵相乘代价仅依赖于小于L长度的矩阵相乘代价。算法思路：按照长度递增(1,2,...n)计算m[i,j]代价。算法matrixChain，首先计算出m[i,i]=0,i=1,2,…,n。然后，根据递归式，按矩阵链长递增的方式依次计算：m[i,i+1],i=1,2,…,n-1,(矩阵链长度为2）；m[i,i+2],i=1,2,…,n-2,(矩阵链长度为3）…；在计算m[i,j]时，只用到已计算的m[i,k]和m[k+1,j];——《算法分析与设计》15——《算法分析与设计》16计算最优解的动态规划算法伪语言voidmatrixChain(intp[],intm[][NUM+1],ints[][NUM+1],intn){//n是当前矩阵个数，NUM是最大矩阵个数处理矩阵长度为1的代价（m[i,i]=0）；for(intr=2;r=n;r++)//长度从2~nfor(inti=1;i=n-r+1;i++){//m[i][i+r-1]intj=i+r-1;寻找min{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]}-m[i][j],k-s[i][j];(i≤kj)}}~~~~~~——《算法分析与设计》17voidmatrixChain(intp[],intm[][NUM+1],ints[][NUM+1]){//p数组包含n+1元素for(inti=1;i=n;i++)m[i][i]=0;//将长度为1的代价赋为0for(intr=2;r=n;r++)//长度从2~nfor(inti=1;i=n-r+1;i++){//从第1行开始~n-r+1行为止intj=i+r-1;m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];//k=i,m[i][i]=0可以省略s[i][j]=i;for(intk=i+1;kj;k++){intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}——《算法分析与设计》18举例：给定一个6个矩阵的矩阵链：k=3,所以s[2][5]=3.算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的三重循环。循环体内的计算量为O(1)，三重循环的总次数为O(n3)。因此算法计算时间上界为O(n3)。算法占用的空间为O(n2)。——《算法分析与设计》19打印矩阵的运算次序voidprintOptimalParens(ints[][NUM+1],inti,intj){if(i==j){coutAi;}else{cout(;printOptimalParens(s,i,s[i][j]);printOptimalParens(s,s[i][j]+1,j);cout)”;}}输出结果：((A1(A2A3))((A4A5)A6))——《算法分析与设计》20总结：动态规划算法的基本要素（1）最优子结构矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。（2）重叠子结构在利用递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质——《算法分析与设计》21用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。动态规划算法举例2：凸多边形最优三角剖分——《算法分析与设计》22多边形的三角剖分就是将多边形分割成互不相交的三角形的弦的集合T。在凸多边形P的三角剖分T中,各弦互不相交,且集合T已达到最大。在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦和n-2个三角形。——《算法分析与设计》23给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得三角剖分中各个三角形的权值之和最小。——《算法分析与设计》24语法树一个带括号的表达式可以用一棵二叉树表示其计算顺序，称为表达式的语法树。例如，((A1(A2A3))(A4(A5A6)))对应的语法树是——《算法分析与设计》25三角剖分的结构及其相关问题凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。除（v0,v6）外，其余边构成叶子结点，弦构成内部结点。——《算法分析与设计》26三角剖分的结构及其相关问题矩阵连乘积中的每个矩阵Ai对应凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应矩阵连乘积A[i+1:j]。——《算法分析与设计》27凸多边形最优三角剖分问题：给定凸边形p={v0,v1,...vn-1}，以及定义在由多边形的边和弦组成的三角形上的权函数w，要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权之和最小。w(vivjvk)=|vivj|+|vjvk|+|vkvi|——《算法分析与设计》28（1）最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。证明（反证法）：如果凸(n+1)边形P={v0,v1,…,vn}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：v0vkvn+{v0,v1,…,vk}+{vk,vk+1,…,vn}可以断言，由T确定的两个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。——《算法分析与设计》29（2）最优三角剖分的递归结构定义t[i][j]，1≤ij≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权