计算机算法设计与分析【王晓东-电子工业出版社-2版】-第3章

上海金融学院信息管理系1第3章动态规划上海金融学院信息管理系2学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。上海金融学院信息管理系3通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏；（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。上海金融学院信息管理系4动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=上海金融学院信息管理系5但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。算法总体思想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)上海金融学院信息管理系6如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。算法总体思想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)上海金融学院信息管理系7动态规划基本步骤找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。上海金融学院信息管理系8（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即AABC)(BCADCBA,,,1050A4010B3040C530D)))(((DBCA)))(((DCAB)))(((DBCA)))(((CDBA)))(((CDAB16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵，它们的维数分别是：总共有五中完全加括号的方式完全加括号的矩阵连乘积上海金融学院信息管理系93.1矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积},...,,{21nAAAiA1iA1,...,2,1ninAAA...21上海金融学院信息管理系10矩阵连乘问题给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk上海金融学院信息管理系11矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤jjiiAAA...1考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤kj，则其相应完全加括号方式为)...)(...(211jkkkiiAAAAAA计算量：A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量上海金融学院信息管理系12特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。分析最优解的结构上海金融学院信息管理系13建立递归关系设计算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]为：jkipppjkmkimjim1],1[],[],[这里的维数为iAiipp1jipppjkmkimjijimjki}],1[],[{min0],[1jki的位置只有种可能kij上海金融学院信息管理系14计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法)(22nnn上海金融学院信息管理系15voidMatrixChain(int*p，intn，int**m，int**s){for(inti=1;i=n;i++)m[i][i]=0;for(intr=2;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];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;}}}}算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。上海金融学院信息管理系16用动态规划法求最优解A1A2A3A4A5A630353515155510102020251137520103504375]5][5[]4][2[71252053510002625]5][4[]3][2[1300020153525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm上海金融学院信息管理系17#includestdafx.h#includeiostream.hvoidMatrixChain(int*p,intn,intm[][7],ints[][7]);voidTraceback(inti,intj,ints[][7]);intmain(intargc,char*argv[]){intn=6;intm[6][6];ints[6][6];intp[7];for(inti=0;i=n;i++){cout\n请输入正整数p(i);cinp[i];}MatrixChain(p,n,m,s);Traceback(1,n,s);return0;}上海金融学院信息管理系18voidMatrixChain(int*p,intn,intm[][6],ints[][6]){for(inti=1;i=n;i++)m[i][i]=0;for(intr=2;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];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;}}}}上海金融学院信息管理系19voidTraceback(inti,intj,ints[][6]){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);coutMultiplyAi,s[i][j];coutandAs[i][j]+1,jendl;}上海金融学院信息管理系20#includestdafx.h#includeiostream.hvoidMatrixChain(int*p,intn,intm[][6],ints[][6]);voidTraceback(inti,intj,ints[][6]);intmain(intargc,char*argv[]){intn=6;intm[6][6];ints[6][6];intp[7];for(inti=0;i=n;i++){cout\n请输入正整数p(i);cinp[i];}for(intii=0;ii=n;ii++)coutp[ii];coutendlendlendl;MatrixChain(p,n,m,s);//coutnendl;Traceback(1,6,s);return0;}voidMatrixChain(int*p,intn,intm[][6],ints[][6]){for(inti=1;i=n;i++){m[i][i]=0;s[i][i]=0;}for(intr=2;r=n;r++)for(inti=1;i=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];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;}}}for(intii=1;ii=n;ii++){for(intjj=ii;jj=n;jj++){cout.width(10);coutm[ii][jj];}coutendl;}coutendlendl;for(intiii=1;iii=n;iii++){for(intjjj=iii;jjj=n;jjj++){cout.width(10);couts[iii][jjj];}coutendl;}coutendlendl;}voidTraceback(inti,intj,ints[][6]){if(i==j)return;Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);coutMultiplyAi,s[i][j];coutandAs[i][j]+1,jendl;}上海金融学院信息管理系213.2动态规划算法的基本要素一、最优子结构•矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。•在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，