第3讲动态规划.

第1页1广州大学华软软件学院算法分析与设计第3讲动态规划第2页2广州大学华软软件学院算法分析与设计学习要点理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。第3页3广州大学华软软件学院算法分析与设计通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）多边形游戏；（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。第4页4广州大学华软软件学院算法分析与设计主要内容•1、算法思想•2、例题•（1）矩阵连乘问题；•（2）最长公共子序列；•（3）最大子段和•（4）凸多边形最优三角剖分；•（5）多边形游戏；（6）图像压缩；（7）电路布线；（8）流水作业调度；（9）背包问题；（10）最优二叉搜索树。第5页5广州大学华软软件学院算法分析与设计•动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=1、算法总体思想第6页6广州大学华软软件学院算法分析与设计•但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。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)第7页7广州大学华软软件学院算法分析与设计•如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。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)第8页8广州大学华软软件学院算法分析与设计1.1最优子结构•组合优化问题，指的是问题有多个可行解，每一个可行解对应一个目标值，目的是要在可行解中求得目标值最优者（最大或最小）。•最优子结构特性指的是问题的最优解包含的子问题的解相对于子问题而言也是最优的。第9页9广州大学华软软件学院算法分析与设计1.2子问题重叠•问题的一个递归算法在每个递归步骤产生分支子问题时并不总是新的，而是对部分子问题解了又解。当一个递归算法一次又一次地访问同一个子问题时，我们说该最优化问题具有重叠子问题的特性。第10页10广州大学华软软件学院算法分析与设计1.3动态规划•针对具有上述两个特征的优化问题，动态规划算法通常需要做如下的3步工作：•（1）利用最优子结构定义一个关于解的目标值的递归方程。鉴于子问题的重叠性，如果自顶向下地用递归技术解每一个遇到的子问题，则可能陷入一个“时间黑洞”。•（2）因此，动态规划以自底向上地对每个新产生的子问题仅解一次且将其解保存在一个表格中，需要时可以在表中查找，且能在常数时间内完成查找。•（3）根据计算出的最优解的值构造对应的最优解。第11页11广州大学华软软件学院算法分析与设计动态规划基本步骤1.找出最优解的性质，并刻划其结构特征。2.递归地定义最优值。3.以自底向上的方式计算出最优值。4.根据计算最优值时得到的信息，构造最优解。第12页12广州大学华软软件学院算法分析与设计•2、例题第13页13广州大学华软软件学院算法分析与设计2.1矩阵链乘法•给定一个由n个矩阵构成矩阵序列（链）A1,A2,...,An，要将它们相乘（假定它们按此序列是乘法相容的：Ai是pi-1pi矩阵，而Ai+1是pipi+1矩阵），计算积：A1A2...An•只要对此序列加上括号，确定运算顺序，就可以算得它们的积。矩阵链的积称为是完全加括号的，若它或是单一的矩阵，或是两个完全加括号的矩阵子链之积，并用一对括号括起来。第14页14广州大学华软软件学院算法分析与设计（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即AABC)(BCADCBA,,,1050A4010B3040C530D)))(((DBCA)))(((DCAB)))(((DBCA)))(((CDBA)))(((CDAB16000,10500,36000,87500,34500完全加括号的矩阵连乘积可递归地定义为：设有四个矩阵，它们的维数分别是：总共有五中完全加括号的方式第15页15广州大学华软软件学院算法分析与设计矩阵连乘问题•给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积•由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。•若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。},...,,{21nAAAiA1iA1,...,2,1ninAAA...21第16页16广州大学华软软件学院算法分析与设计给定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第17页17广州大学华软软件学院算法分析与设计穷举法动态规划将矩阵连乘积简记为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]相乘的计算量第18页18广州大学华软软件学院算法分析与设计•特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。•矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。•问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。分析最优解的结构第19页19广州大学华软软件学院算法分析与设计建立递归关系•设计算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第20页20广州大学华软软件学院算法分析与设计计算最优值•对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有•由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。•用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法)(22nnn第21页21广州大学华软软件学院算法分析与设计子问题重叠性第22页22广州大学华软软件学院算法分析与设计4．算法的伪代码描述•MATRIX-CHAIN-ORDER(p)•1n←length[p]-1•2fori←1ton•3dom[i,i]←0•4forl←2tonl是矩阵链的长度•5dofori←1ton-l+1•6doj←i+l-1•7m[i,j]←∞•8fork←itoj-1•9doq←m[i,k]+m[k+1,j]+pi-1pkpj•10ifqm[i,j]•11thenm[i,j]←q•12s[i,j]←k•13returnmands第23页23广州大学华软软件学院算法分析与设计5．算法的运行时间•算法有三重循环，每个循环变量（l、i及k）最多取n-1个值，可得该算法的运行时间是Θ(n3)。第24页24广州大学华软软件学院算法分析与设计6．构造一个最优解•利用MATRIX-CHAIN-ORDER(p)返回的数表s，可以通过下列过程构造一个最优解。•PRINT-OPTIMAL-PARENS(s,i,j)•1ifi=j•2thenprintAi•3elseprint(•4PRINT-OPTIMAL-PARENS(s,i,s[i,j])•5PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)•6print)第25页25广州大学华软软件学院算法分析与设计用动态规划法求最优解voidMatrixChain(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;}}}}第26页26广州大学华软软件学院算法分析与设计用动态规划法求最优解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第27页27广州大学华软软件学院算法分析与设计用动态规划法求最优解voidMatrixChain(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)。第28页28广州大学华软软件学院算法分析与设计动态规划算法的基本要素一、最优子结构•矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构