第3章_动态规划-2016-all.

1第3章动态规划动态规划算法的基本要素举例1矩阵连乘问题举例2凸多边形最优三角剖分举例3最长公共子序列举例4多段图的最短路径问题举例50-1背包问题举例6资源分配问题多阶段决策问题多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程(multistepdecisionprocess)。最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。多阶段决策的最优化问题：求能够获得问题最优解的决策序列——最优决策序列。22019/12/2031）枚举法穷举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法——动态规划。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。多阶段决策过程的求解策略2019/12/204多阶段决策问题多阶段决策过程多阶段决策过程是活动过程可按时间或空间顺序分解成若干相互独立、相互联系的阶段，在每个阶段的状态下做出决策，整个过程的决策构成一个决策序列，则称多阶段决策过程为序贯决策过程。称问题为多阶段决策问题。12345状态1状态2状态3状态4状态5决策2决策3决策4决策1多阶段决策问题的特点过程可分为若干个相互联系的阶段；每一阶段都对应着一组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。2019/12/205第1阶段第2阶段第3阶段第4阶段状态1状态2状态4状态5状态3决策1决策2决策4决策3动态规划把多阶段过程的问题转化为一系列单阶段的问题，逐个阶段求解的最优化数学方法。6动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题。nn/4n/4n/4n/4区别：经分解得到的子问题往往不是互相独立的。问题：用分治法求解，有些子问题被重复计算多次。7保存已解决的子问题的答案，在需要时找出已求得的答案，以避免大量的重复计算，从而得到多项式时间算法。这就是动态规划算法。在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。解决方法算法设计与分析8动态规划的基本要素最优子结构：问题的最优解是由其子问题的最优解所构成的。重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。9找出最优解的性质，并描述其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。步骤1~3是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。动态规划算法的基本步骤算法设计与分析10动态规划的备忘录方法动态规划中采用自底向上的方式。但是在递归定义中往往是自上而下的描述。备忘录方法就采用与递归定义一致的自上而下的方式。备忘录方法同样用表格来保存已解子问题的信息。每个子问题初始化时都标记为尚未求解。在递归求解过程中，对每个待解子问题，先查看它是否已求解。若未求解，则计算其解并填表保存。若已求解，则查表取出相应的结果。备忘录方法同样避免了子问题的重复计算，因而和动态规划算法具有同样效率。11动态规划算法举例1：矩阵连乘问题1050A4010B3040C530D)))(((DBCA)))(((DCAB)))(((DBCA)))(((CDBA)))(((CDAB给定n个矩阵{A1,A2,...,An}，其中Ai与Ai+1是可乘的。由于乘法满足结合律，故计算矩阵的连乘可以有不同的计算次序。其计算次序可以用加括号的方式确定。假设有4个矩阵：A,B,C,D乘法：16000乘法：10500乘法：36000乘法：87500乘法：34500算法设计与分析12不同计算顺序的差别设矩阵A1,A2和A3分别为10×100,100×5和5×50的矩阵，现要计算A1A2A3。若按((A1A2)A3)来计算，则需要的数乘次数为10×100×5+10×5×50=7500若按(A1(A2A3))来计算，则需要的数乘次数为100×5×50+10×100×50=75000后一种计算顺序的计算量竟是前者的10倍！所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。13矩阵连乘问题给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积所需要的乘法次数最少。14矩阵连乘方法1：枚举法列举出所有可能的计算次序，并计算出每一种计算次序所需要的乘法次数，从中找出一种乘法次数最少的计算次序。时间复杂度分析：对于n个矩阵的连乘，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：结论：P(n)随n的增长呈指数增长，不是高效算法。()()()nknPnPkPnkn1111115消除重复的计算要消除重复计算，可在在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免重复计算。计算方式可依据递归式自底向上地进行。注意到在此问题中，不同的有序对(i,j)就对应不同的子问题，因此不同的子问题个数个数最多只有Cn2+n=(n2)个。这样便可以得到多项式时间的算法。16自底向上的计算例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下：m[1][1]m[2][2]m[3][3]m[4][4]m[1][2]m[2][3]m[3][4]m[1][3]m[2][4]m[2][4]其中m[i][i]=0m[i][i+1]=pi–1pipi+1m[i][j]=mini≤k＜j{m[i][k]+m[k+1][j]+pi–1pkpj}例如：m[1][3]=minm[1][1]+m[2][3]+p0p1p3m[1][2]+m[3][3]+p0p2p317矩阵连乘方法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]相乘的计算量。18（1）分析最优解的结构关键特征：计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求最优解的显著特征。19（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]为：jipppjkmkimjijimjki}],1[],[{min0],[1jki20（3）计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应不同的子问题，因此不同子问题的个数最多只有：可以看出，在递归计算时，有许多子问题被重复计算。)(22nnn21intrecurMatrixChain(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;}22出现重复计算是该问题用动态规划算法求解的又一个显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，在后面需要时只要简单查找一下，从而可以避免大量地重复计算，最终得到多项式时间的算法。23计算最优解的动态规划算法假设Ai的维数为pi-1×pi，则输入序列为{p0,p1,p2,...,pn}p[n+1]记录每个矩阵的维数;m[i,j]记录AiAi+1...Aj相乘的代价（乘法次数）;s[i,j]记录取得最优代价所断开的点k。24具有自底向上的计算特征：如果计算m[i,j]，仅需要计算小于j-i+1个的矩阵乘积。即计算长度为L的矩阵相乘代价仅依赖于小于L长度的矩阵相乘代价。算法思路：按照长度递增(1,2,...n)计算m[i,j]代价。25算法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].261234567812345671234561234512341231211234567812345678m长度（个数）m[3,6]:m[3,3]+m[4,6]m[3,4]+m[5,6]m[3,5]+m[6,6]r27计算最优解的动态规划算法伪语言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)}}28算法voidmatrixChain(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