动态规划法 -算法设计与分析.ppt

,7.1一般方法和基本要素7.2每对结点间的最短路径7.3矩阵连乘7.4最长公共子序列7.5最优二叉搜索树7.60/1背包7.7流水作业调度,第7章动态规划法,20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法动态规划。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。,动态规划法的实质也是将较大问题分解为较小的同类子问题，这一点上它与分治法和贪心法类似。但动态规划法有自己的特点。分治法的子问题相互独立，相同的子问题被重复计算，动态规划法解决这种子问题重叠现象。贪心法要求针对问题设计最优量度标准，但这在很多情况下并不容易。动态规划法利用最优子结构，自底向上从子问题的最优解逐步构造出整个问题的最优解，动态规划则可以处理不具备贪心准则的问题。,7.1一般方法和基本要素,7.1.1一般方法,最优性原理指出，一个最优策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，其余决策必定构成最优策略。这便是最优决策序列的最优子结构特性。,利用动态规划求解问题的前提：1)证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题2)获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。,设计一个动态规划算法，通常可以按以下几个步骤进行：（1）刻画最优解的结构特性；（2）递归定义最优解值；（3）以自底向上方式计算最优解值；（4）根据计算得到的信息构造一个最优解。其中，第（1）至（3）步是动态规划算法的基本步骤。最优解值是最优解的目标函数的值。,7.1.2基本要素,一个最优化多步决策问题适合用动态规划法求解有两个要素：最优子结构特性和重叠子问题。,7.1.3多段图问题,例71多段图G=(V,E)是一个带权有向图，它具有如下特性：图中的结点被划分成k2个互不相交的子集Vi，1ik。其中V1和Vk分别只有一个结点，V1包含源点（source）s，Vk包含汇点（sink）t。对所有边E，多段图要求若uVi，则vVi1，1i=0;j-)floatmin=INFTY;for(ENode*r=aj;r;r=r-nextArc)intv=r-adjVex;if(r-w+costvw+costv;q=v;costj=min;dj=q;p0=0;pk-1=n-1;for(j=1;j=k-2;j+)pj=dpj-1;deletecost;deleted;,算法的时间复杂度若G采用邻接表表示，总计算时间为：,3.向后处理策略求解设BP(i,j)是一条从源点s到Vi中的结点j的最小成本路径，BCOST(i,j)是这条路径的成本。1)向后递推式BCOST(k,t)=02)递推过程第2段c(1,j)ECOST(2,j)=,各递推结果第2段BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2第3段BCOST(3,6)=minBCOST(2,2)+4,BCOST(2,3)+2=9BCOST(3,7)=minBCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11=11BCOST(3,8)=minBCOST(2,4)+11,BCOST(2,5)+8=10第4段BCOST(4,9)=minBCOST(3,6)+6,BCOST(3,7)+4=15BCOST(4,10)=minBCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5=14BCOST(4,11)=minBCOST(3,8)+6=16第5段BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5=16S到t的最小成本路径的成本16,最小成本路径的求取记BD(i,j)每一COST(i,j)的决策即，使COST(i-1,p)+c(p,j)取得最小值的p值。例：BD(3,6)=3,BD(3,7)=2,BD(3,8)=5BD(4,9)=6,BD(4,10)=7,BD(4,11)=8BD(5,12)=10根据D(5,12)的决策值向前递推求取最小成本路径：v4=BD(5,12)=10v3=BD(4,BD(5,12)=7v2=BD(3,BD(4,BD(5,12)=BD(3,7)=2故由s到t的最小成本路径是：1271012,7.1.4资源分配问题,【例72】将n个资源分配给r个项目，已知如果把j个资源分配给第i个项目，可以收益N(i,j)，0jn，1ir。求总收益最大的资源分配方案。,用r1段图描述该问题：段：1到r之间的每个段i表示项目i。结点：i=1时，只有一个结点源点s=V(1,0)当2ir时，每段有n+1个结点，每个结点具有形式V(i,j)：表示到项目i之前为止，共把j个资源分配给了前i-1个项目，j=0,1,n。汇点t=V(r+1,n)边的一般形式：,jl,1ir成本：当jl且1ir时，边赋予成本N(i,l-j),表示给项目i分配l-j个资源所可能获得的净利。当jn且i=r时，此时的边为：,该边赋予成本：,指向汇点的边,注，并不是分给的资源越多，得到的净利就越大,问题的解：资源的最优分配方案由一条s到t的最大成本路径给出改变边成本的符号，从而将问题转换成为求取最小成本路径问题。,例求AOE网的关键路径,7.2.1问题描述,设G=(V,E)是一个有n个结点的带权有向图，w(i,j)是权函数，每对结点间的最短路径问题是指求图中任意一对结点i和j之间的最短路径。,7.2每对结点间的最短路径,分析：利用单源最短路径算法求解计算n个结点的单源最短路径。时间复杂度：(n3)利用动态规划策略求解将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。决策什么？最优性原理对于该问题是否成立？,7.2.2动态规划法求解,最优子结构设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j的最短路径长度，k是这条路径上的一个结点，(i,k)和(k,j)分别是从i到k和从k到j的最短路径长度，则必有(i,j)=(i,k)+(k,j)。因为若不然，则(i,j)代表的路径就不是最短路径。这表明每对结点之间的最短路径问题的最优解具有最优子结构特性。,最优解的递推关系,重叠子问题：为了计算dkij时，必须先计算dk1ij、dk1ik和dk1ik，dk1的元素被多个dk的元素的计算共享。,7.2.3弗洛伊德算法,弗洛伊德算法的基本思想是：令k=0,1,n-1，每次考察一个结点k。二维数组d用于保存各条最短路径的长度，其中，dij存放从结点i到结点j的最短路径的长度。在算法的第k步上应作出决策：从i到j的最短路径上是否包含结点k。,【程序72】弗洛伊德算法templatevoidMGraph:Floyd(T*,for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;弗洛伊德算法的时间复杂度为O(n3),7.2.4算法正确性,定理71弗洛伊德算法得到的dij，0i,jn-1是从i到j的最短路径。,7.3.1问题描述,给定n个矩阵A0,A1,An1，其中Ai，i=0,n-1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n个矩阵的连乘积A0A1An1，由于矩阵乘法满足结合律，所以计算矩阵的连乘可有许多不同的计算次序。矩阵连乘问题是确定计算矩阵连乘积的计算次序，使得按照这一次序计算矩阵连乘积，需要的“数乘”次数最少。,7.3矩阵连乘,完全加括号的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；矩阵连乘积A是完全加括号的，则A可表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。,例744个矩阵连乘积ABCD，设它们的维数分别为A:5010，B:1040,C:4030,D:305。,7.3.2动态规划法求解,最优子结构矩阵连乘AiAi+1Aj简记为Ai:j，ij。于是矩阵连乘A0A1An-1可记作A0:n-1。将这一计算次序在矩阵Ak和Ak+1，0kn-1之间断开，则其相应的完全加括号形式为（A0A1Ak）（Ak+1Ak+2An1）。可先分别计算A0:k和Ak+1:n-1，然后将两个连乘积再相乘得到A0:n-1。,矩阵连乘A0:n-1的最优计算次序的计算量等于A0:k和Ak+1:n-1两者的最优计算次序的计算量之和，再加上A0:k和Ak+1:n-1相乘的计算量。如果两个矩阵子序列的计算次序不是最优的，则原矩阵的计算次序也不可能是最优的。这就是说，矩阵连乘问题的最优解具有最优子结构特性。,最优解的递推关系先定义一个二维数组m，用来保存矩阵连乘时所需的最少计算量。,7.3.3矩阵连乘算法,【程序73】矩阵连乘算法classMatrixChainpublic:MatrixChain(intmSize,int*q);intMChain();intLookupChain();voidTraceback();,private:voidTraceback(inti,intj);intLookupChain(inti,intj);int*p,*m,*s,n;,intMatrixChain:MChain()/求A0:n-1的最优解值for(inti=0;in;i+)mii=0;,for(intr=2;r=n;r+)for(inti=0;i=n-r;i+)intj=i+r-1;mij=mi+1j+pi*pi+1*pj+1;sij=i;for(intk=i+1;kj;k+)intt=mik+mk+1j+pi*pk+1*pj+1;if(tmij)mij=t;sij=k;returnm0n-1;,voidMatrixChain:Traceback(inti,intj)if(i=j)coutAi;return;if(isij)cout(;Traceback(i,sij);if(isij)cout);if(sij+1j)cout(;Traceback(sij+1,j);if(sij+1j)cout);voidMatrixChain:Traceback()cout(;Traceback(0,n-1);cout);cout0)returnmij;if(i=j)return0;intu=LookupChain(i+1,j)+pi*pi+1*pj+1;sij=i;for(intk=i+1;kj;k+)intt=LookupChain(i,k)+LookupChain(k+1,j)+pi*pk+1*pj+1;if(tu)u=t;sij=k;mij=u;returnu;,intMatrixChain:LookupChain()returnLookupChain(0,n-1);,7.5最优二叉搜索树,7.5.1问题描述,设有元素集合a1,a2,an，其中，a1a2an，p(i)是在集合中成功查找ai的概率，1in，q(i)是待查元素x值满足aixai+1的概率,0in（假定a0=,an+1=+）。最优二叉搜索树问题是指设法构造一棵具有最小平均搜索时间的二叉搜索树。,7.5最优二叉搜索树,7.5.2动态规划法求解,设c(0,n)是由元素值集合a1,an所构造的最优二叉搜索树的代价，则,一般地，c(i,j),ij是元素值集合ai+1,aj所构造的最优二叉搜索树的代价，设r(i,j)=k为该树的根，要求结点k满足,例77设n4且（a1,a2,a3,a4）=(Mon,Thu,Tue,Wed)。又设p(1:4)=(3,3,1,1)和q(0:4)(2,3,1,1,1)。这里p和q都已乘了16。,7.5.3最优二叉搜索树算法,【程序77】构造最优二叉搜索树intFind(inti,intj,int*r,float*c)floatmin=INFTY;intk;for(intm=i+1;m=j;m+)if(cim-1+cmj)min)min=cim-1+cmj;k=m;returnk;,voidCreateOBST(float*p,float*q,float*c,int*r,float*w,intn)for(inti=0;i=n-1;i+)wii=qi;cii=0.0;rii=0;wii+1=qi+qi+1+pi+1;cii+1=qi+qi+1+pi+1;rii+1=i+1;wnn=qn;cnn=0.0;rnn=0;,for(intm=2;m0，0i0，pi0，1iP1)xn1=1;elsexn1=0;回溯确定xn2,xn-3,x0;,7.6.5性能分析,在最坏情况下，算法的空间复杂度是O(2n)。在最坏情况下，算法的时间复杂度是O(2n)。,7.7.1问题描述,假定处理一个作业需要执行若干项不同类型的任务，每一类任务只能在某一台设备上执行。设一条流水线上有n个作业J=J0,J1,Jn1和m台设备P=P1,P2,Pm。每个作业需依次执行m个任务，其中第j个任务只能在第j台设备上执行，1jm。设第i个作业的第j项任务Tji所需时间为tji，1jm，0i2则不然）。,定理73流水作业调度问题具有最优子结构的性质。,如果在调度方案的作业排列中，作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。可以设计下列作业排列方法。这样做能得到最优调度方案(1)如果mina0,a1,an1,b0,b1,bn1是ai，则ai应是最优排列的第一个作业；(2)如果mina0,a1,an-1,b0,b1,bn1是bj，则bj应是最优排列的最后一个作业；(3)继续（1）和（2）的做法，直到完成所有作业的排列。,例711设n4，（a0,a1,a2,a3）=(3,4,8,10)（b0,b1,b2,b3）=(6,2,9,15)。设=(0),(1),(2),(3)是最优作业排列。先将任务按处理时间的非减次序排列成：（b1,a0,a1,b0,a2,b2,a3,b3）=(2,3,4,6,8,9,10,15)先选b1，将其加在最优作业排列的最后，故(3)=1再选a0，应加在最