计算机算法基础45

《计算机算法基础45》由会员分享，可在线阅读，更多相关《计算机算法基础45（123页珍藏版）》请在金锄头文库上搜索。

1、第四章 动态规划4.1 一般方法 1. 多阶段决策问题多阶段决策过程：问题的活动过程分为若干相互联系的阶段 ，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过 程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这决策 过程称为多阶段决策过程(multistep decision process) 。最优化问题：问题的每一阶段可能有多种可供选择的决策，必 须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同 ，所导致的问题的结果可能不同。 多阶段决策的最优化问题就是：求能够获得问题最优解的决策 序列最优决策序列。Date12. 多阶段决策过程的求解策略1）枚举法穷

2、举可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段 决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类 过程优化问题的新方法动态规划。动态规划(dynamic programming)是运筹学的一个分支，是求 解决策过程(decision process)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工 程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管 理、资源分配、设备更新、排序、装载等

3、问题，用动态规划方法比用 其它方法求解更为方便。Date23. 最优性原理(Principle of Optimality)过程的最优决策序列具有如下性质：无论过程的初 始状态和初始决策是什么，其余的决策都必须相对于初始决 策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提1) 证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用 动态规划方法有可能解决该问题2) 获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。Date3例4.1 多段图问题多段图G=(V,E)是一个有向图，且具有 特性:结点：结点集V被分成k2个不相交的集合Vi，1ik，其中V1和

4、Vk分别只有一个结点：s(源结点)和t(汇点 )。段： 每一集合Vi定义图中的一段共k段。边： 所有的边(u,v)均具有如下性质： 若E，则若uVi，则uVi1,即该边将是从某段i指向i+1段 ，1ik1。成本：每条边(u,v)均附有成本c(u,v)。s到t的路径：是一条从第1段的源点s出发，依次经过第2段 的某结点v2,i，经第3段的某结点v3,j、最后在 第k段的汇点t结束的路径。该路径的成本是这条路径上边的成本和。多段图问题：求由s到t的最小成本路径。Date41234567891011129732422 7111181456356425V1V2V3V4V55段图Date5多段图问题的多

5、阶段决策过程：生成从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的路径 。与假设矛盾。故，

6、最优性原理成立即，是v2 v3,.,vk-1t构成 从v2至t的最短路径Date6n例4.20/1背包问题 KNAP(1,j,X)目标函数：约束条件：0/1背包问题：KNAP(1,n,M)Date7 最优性原理对0/1背包问题成立：设y1,y2,yn是x1,x2,xn的0/1值最优序列。初始状态： KNAP(1,n,M)初始决策：决定y1等于1还是等于0 若y10, KNAP(2,n-1,M)是初始决策产生的状态。则 y2,yn相对于KNAP(2,n-1,M)将构成一个最优序列。否则，y1,y2,yn将 不是KNAP(1,n,M)的最优解若y11, KNAP(2,n-1,M-w1)是初始决策产

7、生的状态。则 y2,yn相对于KNAP(2,n-1,Mw1)将构成一个最优序列。如若不然，设存在另一0/1序列z2,z3,zn,使得 且则序列y1,z2,zn将是一个对于KNAP(1,n,M)具有更大效益值 得序列。与假设矛盾。故，最优性原理成立 Date84. 最优决策序列的表示设 S0：问题的初始状态 n次决策：问题需要做n次决策 xi：i阶段的决策值，1in。设X1=r1,1,r1,2,r1,p1是x1可选决策值的集合，S1,j1是在 选择决策值r1,j1之后所产生的状态“初始决策”所产生的状态 。设1,j1是相应于状态S1,j1的最优决策序列。则，相应于S0的最优决策序列就是r1,j1

8、1,j1|1j1p1中最 优的序列，记为就一个特定的 r1,j1而言Date9s0r1,1r1,2. . .r1,p1sn1,j1Date10若已经做了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的最优决策序列为r1,rk-1，rk, k就一个特定的rk,jk而言Date115. 递推策略 1

9、）向前处理法列出根据xi+1,xn的最优决策序列求取xi决策值的关系 式。从最后一个阶段，逐步向前递推求出各阶段的决策值 。决策序列x1,x2,xn就是问题的最优解。xn-1,1xn-1,pn-1xn向前递推Date12例4.3 利用向前处理法求解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初始值：0 X0 gn(X) = - X0最优解是

10、g0(M)Date13例4.4 利用向前处理法求解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的最短路径（最优性原理）从Vi中的结点ji到t的最短路径将是：min | E, Vi+1,1ji+1pi+1Date142） 向后处理法列出根据x1,xi-1的最优决策序列求取xi决策值的关系式。从第一个阶段，逐步向后递推求出各阶段的决策值。Date15例4.5

11、 0/1背包问题（向后处理策略）设fi(x)是KNAP(1,i,X)的最优解。则，fn(M) = KNAP(1,n,M)向后递推关系式：fi(X)=maxfi-1(X),fi-1(X-wi)+pi初始值：0 X0 f0(X) = - X0Date16例4.6 k段图问题（向后处理策略）设 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到

12、t的最短路径（最优性原理）从s到Vi中的结点ji的最短路径将是：min | E, Vi+1,1ji+1pi+1 Date17关于动态规划求解策略的进一步说明采用枚举法：若问题的决策序列由n次决策构成，而每 次决策有p种选择，则可能的决策序列将有pn个。利用动态规划策略的求解过程中保存了所有子问题的最 优解，而舍去了所有不能导致问题最优解的次优决策序列动态规划：可能有多项式的计算复杂度。Date184.2 多段图问题1. 问题的描述 在多段图中求从s到t的一条最小成本的路径，可以 看作是在k-2个段作出某种决策的结果。 第i次决策决定Vi+1中的哪个结点在这条路径上，这 里1ik-2； 最优性原

13、理对多段图问题成立Date192. 向前处理策略求解设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。1) 向前递推式2) 递推过程 第k-1段c(j,t) ECOST(k-1,j) = Date20l1l2. . .lpi+1t jViVi+1Date211234567891011129732422 7111181456356425V1V2V3V4V55段图Date22各递推结果第4段 COST(4,9) = c(9,12) = 4COST(4,10) = c(10,12) = 2COST(4,11) = c(11,12) = 5 第3段 C

14、OST(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 第2段 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 第1段 COST(1,1) = min9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)

15、= 16S到t的最小成本路径的成本 16Date23 最小成本路径的求取记 D(i,j)每一COST(i,j)的决策即，使c(j,l)+COST(i+1,l)取得最小值的l值。例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8D(1,1) = 2根据D(1,1)的决策值向后递推求取最小成本路径： v2=D(1,1)=2 v3 = D(2,D(1,1) = 7 v4 = D(3,D(2,D(1,1) = D(3,7) = 10 故由s到t的最小成本路径是：1271012 Date243) 算法描述 结点的编号规则源点s编号为1,然后依次对V2、V3Vk-1中的结点编 号，汇点t编号为n。目的：使对COST和D的计算仅按n-1,n-2,1的次 序计算即可，无需考