5-动态规划

5-动态规划陆伟CollegeofSoftwareandMicroelectronics算法设计与分析IntroductiontotheDesignandAnalysisofAlgorithmsMay7,2020NorthwesternPolytechnicalUniversityLectureOverview1.动态规划基本思想2.动态规划算法的适用条件3.动态规划算法设计的基本步骤和要素4.动态规划算法求解问题案例5.总结与开放性讨论2动态规划基本思想动态规划是一种使多阶段决策过程最优的通用方法。动态规划算法与分治法类似，其思想把求解的问题分成许多阶段或多个子问题，然后按顺序求解各子问题。最后一个阶段或子问题的解就是初始问题的解。3动态规划基本思想动态规划中分解得到的子问题往往不是互相独立的。但不同子问题的数目常常只有多项式级。用分治法求解时，有些子问题被重复计算了许多次，从而导致分治法求解问题时间复杂度较高。4n=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)动态规划基本思想动态规划基本思想是保留已解决的子问题的解，在需要时再查找已求得的解，就可以避免大量重复计算，进而提升算法效率。5n=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)动态规划算法的适用条件动态规划问题的特征求解的问题是组合优化问题；求解过程需要多步判断，从小到大依次求解；子问题目标函数最优解之间存在依赖关系；6动态规划算法的适用条件多起点、多终点的最短路径7S1S4S2S3S5T1T4T2T3T5A1A2A3A4B1B2B3B4B1C1C2C3C464593744342153329341362425376471动态规划算法的适用条件多起点、多终点的最短路径8S1S4S2S3S5T1T4T2T3T5A1A2A3A4B1B2B3B4B1C1C2C3C464593744342153329341362425376471u,2d,3u,7u,1d,11u,5u,7d,5u,4d,9u,8d,6u,7d,15u,13d,10d,11u,10动态规划算法的适用条件求图中总长模10的最短路径。9动态规划算法设计的基本步骤和要素基本步骤（1）找出最优解的性质，并刻画其结构特征。（2）递推地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。要素最优子结构重叠子问题备忘录（表格）10动态规划算法求解问题案例矩阵连乘问题11问题：给定n个矩阵{A1,A2,…,An}，其中，Ai与Ai+1是可乘的，i=1,2,…,n-1。确定矩阵乘法顺序，使得元素相乘的次数最少。实例：3个矩阵{A1,A2,A3}连乘，设3个矩阵的维数分别为10×100,100×5,5×50。若按((A1A2)A3)计算，需要数乘次数为：10×100×5+10×5×50=7500；若按(A1(A2A3))计算，需要数乘次数为：100×5×50+10×100×50=75000。矩阵连乘次序对计算量有很大影响。动态规划算法求解问题案例矩阵连乘问题12蛮力法：搜索所有可能的计算次序，并计算出每种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。设不同计算次序为P(n)。复杂度分析该递归方程解为Catalan数（）P(n)=Ω(4n/n3/2)11)()(1)(11nnknPkPnPnknnnnC211)(动态规划算法求解问题案例矩阵连乘问题—问题理解13说明：将矩阵连乘积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]相乘的计算量。动态规划算法求解问题案例矩阵连乘问题—动态规划14（1）分析最优解结构：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解，满足最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。动态规划算法求解问题案例矩阵连乘问题—动态规划15（2）建立递推关系1.设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]。2.递推方程K的位置只有j-i种可能jipppjkmkimjijimjki}],1[],[{min0],[1jki动态规划算法求解问题案例矩阵连乘问题—动态规划16（3）计算最优值—递归求解intRecurMatrixChain(inti,intj,int*p,int**s){if(i==j)return0;intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];if(tu){u=t;s[i][j]=k;}}returnu;}S[i][j]表示矩阵链A[i:j]最少乘次的断开位置。T(n)≥2n-111))1()()(()1()(11nnOknTkTOnTnk111111)(2)()()()()(nknknkkTnOknTkTnOnT动态规划算法求解问题案例矩阵连乘问题—递归算法分析17对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题,不同子问题的个数最多只有:递归求解最优值复杂度较高的原因是：子问题重复度高)(22nnn动态规划算法求解问题案例矩阵连乘问题18voidMatrixChain(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;}}}}（3）计算最优值—迭代查表求解时间复杂度O(n3)空间复杂的O(n2)动态规划算法求解问题案例矩阵连乘问题—迭代查表19动态规划算法求解问题案例矩阵连乘问题—迭代查表20A1A2A3A4A5A63035351515551010202025（3）计算最优值—迭代查表求解—案例分析1137520103504375]5][5[]4][2[71252053510002625]5][4[]3][2[1300020153525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm动态规划算法求解问题案例矩阵连乘问题—备忘录21（3）计算最优值—备忘录求解intMemoizedMatrixChain(intn,int**m,int**s){for(inti=1;i=n;i++)for(intj=i;j=n;j++)m[i][j]=0;returnLookupChain(1,n);}intLookupChain(inti，intj){if(m[i][j]0)returnm[i][j];if(i==j)return0;intu=LookupChain(i，i)+LookupChain(i+1，j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;kj;k++){intt=LookupChain(i，k)+LookupChain(k+1，j)+p[i-1]*p[k]*p[j];if(tu){u=t;s[i][j]=k;}}m[i][j]=u;returnu;}动态规划算法求解问题案例矩阵连乘问题—构造最优解22（4）构造最优解voidTracback(inti,intj,int**s){if(i==j)return;Trackback(i,s[i][j],s);Trackback(s[i][j]+1,j,s);cout“Multiply”i“,”s[i][j];cout“andA”(s[i][j])+1“,”jendl;}动态规划算法求解问题案例矩阵连乘问题—实例计算23设输入P=30,35,15,5,10,20，n=5，相应矩阵链为：A1,A2,A3,A4,A5，其中，A1:3035,A2:3515,A3:155,A4:510,A5:1020动态规划算法求解问题案例凸多边形最优三角剖分24凸多边形的表示：多边形顶点的逆时针序列表示。例：P={v0，v1，v2，v3，v4，v5，v6}弦：两个不相邻顶点间的直线线段。弦将多边形分割为两个子多边形。动态规划算法求解问题案例凸多边形最优三角剖分25多边形的三角剖分指将多边形分割成互不相交的三角形的弦的集合T。n个顶点的凸多边形剖分必有n-3条弦和n-2个三角形。动态规划算法求解问题案例凸多边形最优三角剖分26问题：给定凸多边形P={v0，v1，…，vn-1}，以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分所对应的权，即三角剖分中诸三角形上权之和为最小。动态规划算法求解问题案例凸多边形最优三角剖分27（1）一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图(a)所示。（2）凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所示的语法树表示。（3）矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积A[i+1:j]。（4）矩阵连乘的最优计算次序问题是凸多边形最优三角剖分问题的特殊情形。动态规划算法求解问题案例三角剖分的结构及其相关问题—同构28动态规划算法求解问题案例凸多边形最优三角剖分29凸多边形的最优三角剖分问题有最优子结构性质。若凸(n+1)边形P={v0,v1,…,vn}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。动态规划算法求解问题案例凸多边形最优三角剖分—递归结构30定义t[i][j]，1≤ij≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。t[i][j]的值可以利用最优子结构性质递归地计算