算法设计与分析-3-15

第3章动态规划学习要点:理解动态规划算法的概念，动态规划vs递归分治掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）(多边形游戏)（6）图像压缩；（7）背包问题；（8）最优二叉搜索树（9）(流水作业调度)（10）(电路布线)与分治法类似，其基本思想也是将待求解问题分解成若干个子问题;先求子问题解，然后合成原问题解算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=大问题自上而下分解为子问题时，可以有多种分解方法。e.g.归并排序，矩阵连乘如果不同分解方法对应的子问题及其解不同，并导致合并后的原问题解不同，则需要考虑各种可能的分解方法。此时，无法直接采用分治法求解：e.g.矩阵连乘1.分解得到的子问题往往不是互相独立的，用分治法求解，需要计算的子问题数目太多，时间复杂性指数级别2.不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。E.g.Fibonacci数列计算，见后与分治法区别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)解决方法：保存已解决的子问题的答案，在需要时再找出已求得的答案，避免大量重复计算，得到多项式时间算法。利用表来记录子问题的答案，表的大小为多项式量级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)示例：分治法vs动态规划算法1——基于递归分治F(n)1.if(n=1return1;2.elsereturnF(n-1)+F(n-2);问题：复杂性O(2n)原因：自上而下的递归计算过程中，一些子问题被多次重复计算10()11(1)(2)1nFnnFnFnnFibonacci数F(6)F(4)F(3)F(2)F(1)F(0)F(2)F(1)F(0)F(1)F(5)F(4)F(3)F(2)F(1)F(0)F(1)F(3)F(2)F(2)F(1)F(0)F(1)F(1)F(0)子问题F(3)重复计算3次子问题F(2)重复计算5次算法2：非递归的分治算法保存子问题计算结果，只计算1次，以后碰到同样子问题时，直接调用已有结果F1(n)0.初始化数组v[i]←-1,0≤i≤n1.ifv[n]0then2.v[n]←F1(n-1)+F1(n-2)3.returnv[n]数组v[n]:存储子问题结果的数组，v[i]：表示子问题F[i]的解，v[i]=-1：表示子问题F[i]还没有被计算问题：自上而下的计算过程中，避免了多次计算同一子问题，但又多次函数调用。每次调用需要花费较多时间用于参数传递和动态链接算法3——自下而上的迭代算法：动态规划算法F2(n)1.F(0)←1;2.F(1)←1;3.fori←2tondo4.F[i]←F1(i-1)+F1(i-2)/*问题-子问题间的递归公式5.returnF[n]特点：1）时间复杂性O(n)2)自下而上，迭代计算3)利用数组，保存中间（子问题）计算结果。每个子问题只计算一次动态规划基本步骤1.找出最优解的性质，刻划其结构特征-最优子结构特征2.递归地定义最优值：刻画原问题解与子问题解间的（数值）关系:表达式中存在寻优变量、最优目标值3.以自底向上的方式计算出各个子问题、原问题的最优值，并避免子问题的重复计算（记录已计算的子问题解）4.根据计算最优值时得到的信息，构造最优解12（1）矩阵连乘问题；——乘法次数最少（2）最长公共子序列；——公共子序列的长度最长（3）最大子段和——子段中的数字之和最大（4）凸多边形最优三角剖分；——三角形上权之和为最小（6）图像压缩；（9）背包问题；（10）最优二叉搜索树。（7）电路布线；（8）流水作业调度；——作业运行时间最短（5）多边形游戏；动态规划适宜解最优化问题给定n个可连乘的矩阵{A1,A2,…,An},连乘积A1A2,…,An。根据矩阵乘法结合律，可有多种不同计算次序，每种次序有不同的计算代价)—数乘次数（取决于各矩阵的行、列数和计算次序）给定2个矩阵A[pi,pj],B[pj,pk],A×B为[pi,pk]矩阵，数乘次数pi×pj×pk多个矩阵的连乘计算次序可用完全加括号来确定——见下页完全加括号的矩阵连乘积1050A4010B3040C530D)))(((DBCA)))(((DCAB)))(((DBCA)))(((CDBA)))(((CDAB这5种计算次序对应的计算代价分别为：16000,10500,36000,87500,34500设有四个矩阵A,B,C,D,它们的维数分别是：总共有五种完全加括号的方式举例(40*30*5)+10*40*5+50*10*5CD[40,5]B(CD)[10,5]A(B(CD))[50,5]完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即AABC)(BCA矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积},...,,{21nAAAiA1iA1,...,2,1ninAAA...21给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。方法1：穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序下的组合方式（即完全加括号的组合方式）为P(n)。每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)，关于P(n)的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk穷举法方法2：动态规划将矩阵连乘积简记为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]相乘的计算量特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。即：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。分析最优解的结构—是否可用动态规划？建立递归关系设计算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时，断开位置k可以递归地定义m[i,j]为：jkipppjkmkimjim1],1[],[],[这里的维数为iAiipp1jipppjkmkimjijimjki}],1[],[{min0],[1jki的位置只有种可能kij计算最优值对于1≤i≤j≤n，不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算：1）在计算过程中，保存已解决的子问题答案。每个子问题只计算一次2）而在后面需要时只要简单查一下，从而避免大量的重复计算最终得到多项式时间的算法)(22nnn子问题A[i,i],1≤i≤nvoidMatrixChain(int*p，intn，int**m，int**s){for(inti=1;i=n;i++)m[i][i]=0;/*规模为1的子问题的最优解for(intr=2;r=n;r++)/*自下而上，从规模为r=2的子问题开始，依次计算规模为2、3、…、n的子问题for(inti=1;i=n-r+1;i++){/*考察规模为r的共n-r+1个子问题m[i,j],j-i=r-1,intj=i+r-1;/*子问题左端点i，右端点j,规模rm[i][j]=0+m[i+1][j]+p[i-1]*p[i]*p[j];/*设置子问题m[i,j]的初始最优值s[i][j]=i;/*记录子问题最优值的初始断点位置for(intk=i+1;kj;k++){/*依次考察不同断点，计算m[i,j]最优值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;}}}}输入参数最优值断开位置子问题m[i,j]的递推比较矩阵维度1(...)iijAAA1n子问题规模r：2nr左端点i：1(=n-1)n-r+1右端点j：2j=i+r-1ni子问题m[i,j]的断点k：i+1jk规模为r的子问题m[i,j],共n-r+1个m[i,j]子问题：AiAi+1…Ak…Ajr断点右端点左端点子问题规模/长度共有j-i个断点示例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[541531521pppmmpppmmpppmmmA2A3A4A5[1,1],…,[6,6][1,2],…,[5,6][1,3],…,[4,6][1,4],…,[3,6][1,5],…,[2,6][1,6]算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。27总结——矩阵连乘问题求解要素1.原问题/子问题形式化表述2.（定量）最优化目标3.原问题/子问题最优解递归表达式1[,]...,1iijAijAAAijnmin[,],1mijijnjipppjkmkimjijimjki}],1[],[{min0],[1jki)...)(...(211jkkkiiAAAAAA28问题归结：原问题子问题(问题规模更小)原问题:A(i,j),最优解:m(i,j)A(i,k),m(i,k)A(k,j),m(k,j))...)(...(211jkkkiiAAAAAA动态规划算法基本要素一、最优子结构•矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质