算法分析与设计第六章1(动态规划)

2008-09-01,版权所有：杨波，武汉科技大学理学院,第六章动态规划,2008-09-01,版权所有：杨波，武汉科技大学理学院,6.1一般方法,多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这决策过程称为多阶段决策过程(multistepdecisionprocess)。最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列最优决策序列。,多阶段决策问题,2008-09-01,版权所有：杨波，武汉科技大学理学院,1）枚举法穷举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法动态规划。动态规划(dynamicprogramming)是运筹学的一个分支，是求解决策过程(decisionprocess)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。,多阶段决策过程的求解策略,2008-09-01,版权所有：杨波，武汉科技大学理学院,过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。,最优性原理,说明：动态规划所遵循的原理就是最优化原理。动态规划的设计方法对于不同问题有不同的表达方式。不存在一种万能的动态规划算法。必须具体问题具体分析处理。以丰富想象力去建立模型，用创造性的技巧去求解。,相对的概念,广义的概念,2008-09-01,版权所有：杨波，武汉科技大学理学院,动态规划求解问题前提,证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键,2008-09-01,版权所有：杨波，武汉科技大学理学院,例6.1.1多段图问题多段图G=(V,E)是一个有向图，且具有特性:结点：结点集V被分成k2个不相交的集合Vi，1ik，其中V1和Vk分别只有一个结点：s(源结点)和t(汇点)。段：每一集合Vi定义图中的一段共k段。边：所有的边均具有如下性质：若E，则若uVi，则vVi1,即该边将是从某段i指向i+1段，1ik1。成本：每条边均附有成本c(u,v)。s到t的路径：是一条从第1段的源点s出发，依次经过第2段的某结点v2,i，经第3段的某结点v3,j、最后在第k段的汇点t结束的路径。该路径的成本是这条路径上边的成本和。多段图问题：求由s到t的最小成本路径。,2008-09-01,版权所有：杨波，武汉科技大学理学院,2008-09-01,版权所有：杨波，武汉科技大学理学院,多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1ik-2)中的哪个结点在从s到t的最短路径上。最优性原理对多段图问题成立假设s,v2,v3,vk-1,t是一条由s到t的最短路径。初始状态：s初始决策：(s,v2)，v2V2初始决策产生的状态：v2则，其余的决策：v3,.,vk-1相对于v2将构成一个最优决策序列最优性原理成立。反证：若不然，设v2,q3,qk-1,t是一条由v2到t的更短的路径，则s,v2,q3,qk-1,t将是比s,v2,v3,vk-1,t更短的从s到t的路径。与假设矛盾。故，最优性原理成立,即，是v2v3,.,vk-1t构成从v2至t的最短路径,过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例6.1.20/1背包问题KNAP(1,j,X)目标函数：约束条件：0/1背包问题：KNAP(1,n,M),2008-09-01,版权所有：杨波，武汉科技大学理学院,最优性原理对0/1背包问题成立：设y1,y2,yn是x1,x2,xn的0/1值最优序列。初始状态：KNAP(1,n,M)初始决策：决定y1等于1还是等于0若y10,KNAP(2,n,M)是初始决策产生的状态。则y2,yn相对于KNAP(2,n,M)将构成一个最优序列。否则，y1,y2,yn将不是KNAP(1,n,M)的最优解若y11,KNAP(2,n,M-w1)是初始决策产生的状态。则y2,yn相对于KNAP(2,n,Mw1)将构成一个最优序列。如若不然，设存在另一0/1序列z2,z3,zn,使得且则序列y1,z2,zn将是一个对于KNAP(1,n,M)具有更大效益值得序列。与假设矛盾。故，最优性原理成立,2008-09-01,版权所有：杨波，武汉科技大学理学院,设S0：问题的初始状态n次决策：问题需要做n次决策xi：i阶段的决策值，1in。设X1=r1,1,r1,2,r1,p1是x1可选决策值的集合，S1,j1是在选择决策值r1,j1之后所产生的状态“初始决策”所产生的状态。设1,j1是相应于状态S1,j1的最优决策序列。则，相应于S0的最优决策序列就是r1,j11,j1|1j1p1中最优的序列，记为,就一个特定的r1,j1而言,最优决策序列的表示,2008-09-01,版权所有：杨波，武汉科技大学理学院,x1,2008-09-01,版权所有：杨波，武汉科技大学理学院,若已经做了k-1次决策，1k-1n，设x1,x2,xk-1的最优决策值是r1,r2,rk-1，所产生的状态依次为S1,S2,Sk-1。设Xk=rk,1,rk,2,rk,pk是xk可能的决策值的集合，Sk,jk是在选择决策值rk,jk之后所产生的状态,1jkpk。k,jk是相应于状态Sk,jk的最优决策序列。则，相应于Sk-1的最优决策序列是相应于S0的最优决策序列为r1rk-1rkk,就一个特定的rk,jk而言,2008-09-01,版权所有：杨波，武汉科技大学理学院,sk-1,rk,1,rk,2,.,rk,pk,Sn+1,k,jk,k,1,k,2,k,pk,rk,jk,s0,s1,s2,x1,x2,xk,r1,r2,Xk-1,rk-1,2008-09-01,版权所有：杨波，武汉科技大学理学院,递推策略向前处理法,列出根据xi+1,xn的最优决策序列求取xi决策值的关系式。按关系式，从最后阶段开始，回溯求解这些关系式得出最优决策序列x1,x2,xn，即为问题的最优解。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例6.1.3利用向前处理法求解k段图问题设V2，1j2p2,|V2|=p2;是由到t的最短路径，则s到t的最短路径是s|V2,1j2p2中最短的那条路径。若s,v2,v3,vi,vk-1,t是s到t的一条最短路径，vi是其中的一个中间点，则s,v2,v3,vi和vi,vk-1,t分别是由s到vi和vi到t的最短路径,2008-09-01,版权所有：杨波，武汉科技大学理学院,2008-09-01,版权所有：杨波，武汉科技大学理学院,例6.1.4利用向前处理法求解0/1背包问题设gi(x)是KNAP(i+1,n,X)的最优解。g0(M)：KNAP(1,n,M)的最优解。由于x1的取值等于1或0,可得：g0(M)=maxg1(M),g1(M-w1)+p1对于某个xi，xi等于1或0，则有：gi(X)=maxgi+1(X),gi+1(X-wi+1)+pi+1初始值：0X0gn(X)=-X0,最优解是g0(M),2008-09-01,版权所有：杨波，武汉科技大学理学院,列出根据x1,xi-1的最优决策序列求取xi决策值的关系式。从第一个阶段，逐步向后递推求出各阶段的决策值。,递推策略向后处理法,2008-09-01,版权所有：杨波，武汉科技大学理学院,例6.1.5k段图问题（向后处理策略）设Vk-1，1jk-1pk-1，|Vk-1|=pk-1;是由s到的最短路径，则s到t的最短路径是t|Vk-1,1jk-1pk-1中最短的那条路径。若s,v2,v3,vi,vk-1,t是s到t的一条最短路径，vi是其中的一个中间点，则s,v2,v3,vi和vi,vk-1,t分别是由s到vi和vi到t的最短路径,2008-09-01,版权所有：杨波，武汉科技大学理学院,2008-09-01,版权所有：杨波，武汉科技大学理学院,例6.60/1背包问题（向后处理策略）设fi(x)是KNAP(1,i,X)的最优解。则，fn(M)=KNAP(1,n,M)由于xn的取值等于1或0,可得：fn(M)=maxfn-1(M),fn-1(M-wn)+pn对于某个xi，xi等于1或0，则有：向后递推关系式：fi(X)=maxfi-1(X),fi-1(X-wi)+pi初始值：0X0f0(X)=-X0,2008-09-01,版权所有：杨波，武汉科技大学理学院,采用枚举法：若问题的决策序列由n次决策构成，而每次决策有p种选择，则可能的决策序列将有pn个。利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列动态规划：可能有多项式的计算复杂度。,动态规划求解策略的进一步说明,2008-09-01,版权所有：杨波，武汉科技大学理学院,6.2多段图,问题的描述在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果。第i次决策决定Vi+1中的哪个结点在这条路径上，这里1ik-2；最优性原理对多段图问题成立,2008-09-01,版权所有：杨波，武汉科技大学理学院,设P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径，COST(i,j)是这条路径的成本。1)向前递推式2)递推过程第k-1段c(j,t)ECOST(k-1,j)=,Vi+1中的结点l到汇点t的最小成本,向前处理策略求解,Vi中的结点j到汇点t的最小成本,Vi中的结点j到Vi+1中的结点l成本,2008-09-01,版权所有：杨波，武汉科技大学理学院,第四段COST(4,9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=5,第三段COST(3,6)=min6+COST(4,9),5+COST(4,10)=7COST(3,7)=min4+COST(4,9),3+COST(4,10)=5COST(3,8)=min5+COST(4,10),6+COST(4,11)=7,第二段COST(2,2)=min4+COST(3,6),2+COST(3,7),1+COST(3,8)=7COST(2,3)=9COST(2,4)=18COST(2,5)=15,第一段COST(1,1)=min9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)=16,S到t的最小成本路径的成本：16,S到t的最小成本路径的成本：路径是什么呢？,2008-09-01,版权所有：杨波，武汉科技大学理学院,最小成本路径的求取,记D(i,j)为每一COST(i,j)的决策即，使c(j,l)+COST(i+1,l)取得最小值的l值。,Vi中的结点j到汇点t的最小成本路径上的下一个节点,2008-09-01,版权所有：杨波，武汉科技大学理学院,第四段COST(4,9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=5,第三段COST(3,6)=min6+COST(4,9),5+COST(4,10)=7COST(3,7)=min4+COST(4,9),3+COST(4,10)=5COST(3,8)=min5+COST(4,10),6+COST(4,11)=7,第二段COST(2,2)=min4+COST(3,6),2+COST(3,7),1+COST(3,8)=7COST(2,3)=9COST(2,4)=18COST(2,5)=15,第一段COST(1,1)=min9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)=16,S到t的最小成本路径的成本：16,第四段COST(4,9)=4D(4,9)=12COST(4,10)=2D(4.10)=12COST(4,11)=5D(4.11)=12,第三段COST(3,6)=7D(3,6)=10COST(3,7)=5D(3,7)=10COST(3,8)=7D(3,7)=10,第二段COST(2,2)=7D(2,2)=7COST(2,3)=9D(2,3)=6COST(2,4)=18D(2,4)=8COST(2,5)=15D(2,5)=8,第一段COST(1,1)=16D(1,1)=2,2008-09-01,版权所有：杨波，武汉科技大学理学院,1,2,3,4,5,6,7,8,9,10,11,12,9,7,3,2,4,2,2,7,11,11,8,1,4,5,6,3,5,6,4,2,5,V1,V2,V3,V4,V5,第四段COST(4,9)=4D(4,9)=12COST(4,10)=2D(4.10)=12COST(4,11)=5D(4.11)=12,第三段COST(3,6)=7D(3,6)=10COST(3,7)=5D(3,7)=10COST(3,8)=7D(3,7)=10,第二段COST(2,2)=7D(2,2)=7COST(2,3)=9D(2,3)=6COST(2,4)=18D(2,4)=8COST(2,5)=15D(2,5)=8,第一段COST(1,1)=16D(1,1)=2,2008-09-01,版权所有：杨波，武汉科技大学理学院,结点的编号规则源点s编号为1,然后依次对V2、V3Vk-1中的结点编号，汇点t编号为n。目的：使对COST和D的计算仅按n-1,n-2,1的次序计算即可，无需考虑标示结点所在段的第一个下标。,算法描述,2008-09-01,版权所有：杨波，武汉科技大学理学院,publicstaticvoidFgraph(E,intk,intn,intP)/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，/cij是边的成本。P1:k是最小成本路径。doubleCOSTn;intDn-1,r,j;COSTn=0;for(j=n-1;jE且使c(j,r)+COSTr取最小值COSTj=cjr+COSTr;Dj=r;P1=1;Pk=n;for(j=2;j=1;j-)/计算COSTj/设r是一个这样的结点，属于E且cjr+COSTr取最小值i=j+1;while(cji=10000)/不存在边i+;temp=cji+COSTi;r=i;,多段图向前处理算法详细描述,寻找第j个结点到终点的最短路径,2008-09-01,版权所有：杨波，武汉科技大学理学院,for(i=i+1;i=n;i+)if(cji!=10000),第j个结点到汇点的最短路径上的下一个节点,2008-09-01,版权所有：杨波，武汉科技大学理学院,设BP(i,j)是一条从源点s到Vi中的结点j的最小成本路径，BCOST(i,j)是这条路径的成本。1)向后递推式2)递推过程第2段c(1,j)ECOST(2,j)=,向后处理策略求解,源点s到Vi-1中的结点l的最小成本,源点s到Vi中的结点j的最小成本,Vi-1中的结点l到Vi+1中的结点j的成本,2008-09-01,版权所有：杨波，武汉科技大学理学院,第一段BCOST(2,2)=COST(1,2)=9BCOST(2,3)=COST(1,3)=7BCOST(2,4)=COST(1,4=3BCOST(2,5)=COST(1,5=2,第二段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,2)+1,BCOST(2,4)+11,BCOST(2,5)+8=10,第三段BCOST(4,9)=minBCOST(3,6)+6,BCOST(3,7)+4=15BCOST(4,10)=14BCOST(4,11)=16,第四段BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5=16,S到t的最小成本路径的成本：16,S到t的最小成本路径的成本：路径是什么呢？,2008-09-01,版权所有：杨波，武汉科技大学理学院,最小成本路径的求取,记D(i,j)为每一COST(i,j)的决策即，使COST(i-1,l)+c(l,j)取得最小值的l值。,源点s到Vi中的结点j的最小成本路径上的前一个节点,2008-09-01,版权所有：杨波，武汉科技大学理学院,第一段BCOST(2,2)=COST(1,2)=9BCOST(2,3)=COST(1,3)=7BCOST(2,4)=COST(1,4=3BCOST(2,5)=COST(1,5=2,第二段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,2)+1,BCOST(2,4)+11,BCOST(2,5)+8=10,第三段BCOST(4,9)=minBCOST(3,6)+6,BCOST(3,7)+4=15BCOST(4,10)=14BCOST(4,11)=16,第四段BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5=16,S到t的最小成本路径的成本：16,第一段BCOST(2,2)=9D(2,2)=1BCOST(2,3)=7D(2,3)=1BCOST(2,4)=3D(2,4)=1BCOST(2,5)=2D(2,5)=1,第二段BCOST(3,6)=9D(3,6)=3BCOST(3,7)=11D(3,7)=2BCOST(3,8)=10D(3,8)=2,第三段BCOST(4,9)=15D(4,9)=6BCOST(4,10)=14D(4,10)=7BCOST(4,11)=16D(4,11)=8,第四段BCOST(5,12)=16D(5,12)=10,2008-09-01,版权所有：杨波，武汉科技大学理学院,1,2,3,4,5,6,7,8,9,10,11,12,9,7,3,2,4,2,2,7,11,11,8,1,4,5,6,3,5,6,4,2,5,V1,V2,V3,V4,V5,第一段BCOST(2,2)=9D(2,2)=1BCOST(2,3)=7D(2,3)=1BCOST(2,4)=3D(2,4)=1BCOST(2,5)=2D(2,5)=1,第二段BCOST(3,6)=9D(3,6)=3BCOST(3,7)=11D(3,7)=2BCOST(3,8)=10D(3,8)=2,第三段BCOST(4,9)=15D(4,9)=6BCOST(4,10)=14D(4,10)=7BCOST(4,11)=16D(4,11)=8,第四段BCOST(5,12)=16D(5,12)=10,2008-09-01,版权所有：杨波，武汉科技大学理学院,voidBgraph(E,intk,intn,intP)/和Fgraph功能相同doubleBCOSTn;intDn-1,r,j;BCOST1=0;for(j=2;jE且使BCOSTr+crj取最小值BCOSTj=BCOSTr+crj;Dj=r;/找一条最小成本路径P1=1;Pk=n;for(j=k-1;j=2;j-)Pj=DPj+1;,多段图的向后处理算法,2008-09-01,版权所有：杨波，武汉科技大学理学院,资源的分配问题将n个资源分配给r个项目的问题：如果把j个资源，0jn，分配给项目i，可以获得N(i,j)的净利。问题：如何将这n个资源分配给r个项目才能使各项目获得的净利之和达到最大。（假设分配顺序为项目1,2,3,4并且一次就分配完，一个资源只能分配给一个项目）转换成一个多段图问题求解。,多段图问题的应用,2008-09-01,版权所有：杨波，武汉科技大学理学院,4个资源分给3个项目的4段图构造,S=V(1,0),起点开始分配0个资源给项目0（没有资源分配）,将0个资源分配给了项目1，没有进行资源分配,将1个资源分配给了项目1,将2个资源分配给了项目1,将4个资源分配给了项目1,N(1,0),将0个资源分配给了项目1的收益,N(1,1),将1个资源分配给了项目1的收益,N(1,2),将2个资源分配给了项目1的收益,N(1,3),将3个资源分配给了项目1的收益,N(1,4),将4个资源分配给了项目1的收益,将3个资源分配给了项目1,2008-09-01,版权所有：杨波，武汉科技大学理学院,4个资源分给3个项目的4段图构造,S=V(1,0),N(1,0),N(1,1),N(1,2),N(1,3),N(1,4),将0个资源分配给了项目1，2,V(3,1),V(3,2),V(3,3),V(3,4),V(3,0),N(2,0),将0个资源分配给了项目2的收益,将1个资源分配给了项目1，2,N(2,1),将1个资源分