算法设计与分析6章动态规范算法.ppt

第6章 动态规范算法,6.1 一般方法 6.2 多段图 6.3 每对节点之间的最短路径 6.4 最优二分检索树 6.5 0/1背包问题 6.6 可靠性设计 6.7 货郎担问题 6.8 流水线调度问题,学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。,通过应用范例学习动态规划算法设计策略。 (1) 多段图 （2） 每对节点间的最短路径 （3）最优二分检索树； （4）0/1 背包问题 （5）可靠性设计； （6）货郎担问题 （7）流水作业调度；,6.1 一般方法,把已知问题分为许多阶段或许多子问题，然后按顺序求解各个子问题。 在每种情况下，列出各种可能的局部解，然后根据某些条件，从局部中挑选中那些有可能产生最优结果的解 前一个子问题的解为后一个子问题的求解提供有用的信息，从而大大减少了计算量,最优性原理： 不论初始状态和第一步决策是什么，余下的决策必须按照前一次决策所产生的新状态构成一个最优决策序列。 不论前面的状态和策略如何，后面的最优策略只取决于由最初策略所决定的当前状态,动态规划的向前处理法： 从最后阶段开始，以逐步向前递推的方式求出前一阶段决策值的递推关系式，即根据xi+1,xn的那些最优决策来求取xi决策值的关系式 列出关系式后，由最后阶段开始，回溯求解这些关系式得出最优决策序列,6.2 多段图,多段图G=(V,E)是一个有向图。它具有如下的特性：图中的节点被划分成k=2个不相交的集合Vi, 1均具有如下性质： 若u Vi, 则v Vi+1,1=ik-1, 且没条边均附有成本c(u,v); 从s到t的一条路径成本是这条路径上边的成本和。多段图问题是求由s到t的最小成本路径,假设s, V2,V3,Vk-1, t是由s到t的最短路径，同时假定从源点s(初始状态）开始，已作出了到结点V2的决策（初始决策），因此V2就是初始决策所产生的状态。 如果把V2看成是原问题的一个子问题的初始状态，解这个子问题就是找出一条由v2到t的最短路径。这条最短路径是V2,V3,Vk-1, t 否则设V2,q3,qk-1, t是一条由V2到t的更短路径，则s, V2,q3,qk-1, t是一条比s, V2,V3,Vk-1, t更短的由s到t的路径。与假设相矛盾，故最优性原理成立。,1,2,3,4,5,6,7,8,12,9,11,10,S,t,V2,V3,V4,9,7,3,2,4,2,2,7,11,11,8,6,5,4,3,1,5,6,4,2,5,设P(i,j)是一条从Vi中的节点j到汇点t的最小成本路径，COST(i,j)是这条路径的成本。那么，由向前处理法可以得到 COST(i,j)=minc(j,1)+COST(j+1,1) 当E时， COST(k-1,j)=c(j,t), 如果 不属于E时， COST(k-1,j)=无穷大,FGRAPH(Elemtype E, int k, int n, Elemtype Pk) 1 COStn0 2 for jn-1 to 1 by -1 3 do 设r是这样的一个节点，属于E，且使cjr+COSTr取最小值 4 COSTjcjr+COSTr; 5 Djr; 6 P11; Pkn 8 for j2 to k-1 9 do PjDPj-1;,6.3 每对节点之间的最短路径,设G=（V,E）是一个有n个节点的有向图。又设C是G的成本邻接矩阵，其中C(i,j)=0, 1E (G)时，C(i,j)表示边的长度；ij,6.4 最优二分检索树,检索一个二分检索树的算法： 输入：二分检索树T和被查找元素X 输出：如果X不在T中，则置i=0，否则将i置成INDEXi=X,SEACH(Elemtype T, Elemtype X) 1 int it; 2 while i0; 3 do 4 if (xINDEXi 7 iRCHILDi) 8 else xINDEXi; 9 return i; 10 ,查找成功与不成功的概率 二查找树的期望耗费 有 个节点的二叉树的个数为： 穷举搜索法的时间复杂度为指数级,二叉查找树的期望耗费,二叉查找树的期望耗费示例,最优二叉搜索树,最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下 记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为 注意到， 可以得到O(n2)的算法,0/1背包问题(0/1 Knapsack),问题描述 有n种可选物品1,n ，放入容量为c的背包内，使装入的物品具有最大效益 表示 n, c 分别为物品个数和背包容量 p1,p2, , pn为个体物品效益值 w1,w2, ，wn为个体物品容量 问题解析 0/1背包问题的解指物品1,n的一种放法(x1, ,xn的0/1赋值), 使得效益值最大 假定背包容量不足以装入所有物品:面临选择 优化原理:无论优化解是否放物品1,优化解对物品2,n的放法,相对剩余背包容量,也是优化解,背包问题满足的优化原理,(1,1,0,0,1)为其优化解,即放物品1,2,5 物品1占背包容量2,剩下容量为8 考虑子问题:n=4,c=8,物品为2,3,4,5 (1,0,0,1),即放物品1和5,是子问题的优化解 因而背包问题满足优化原理,假设： n=5,c=10 p=6,3,5,4,6 w=2,2,6,5,4,对于0/1背包问题，可以通过作出变量x1,x2,xi的一个决策序列来得到它的解。 对xn作出决策之后，问题处于下列的两种状态之一： 1 背包的剩余容量是M，没有产生任何效益 2 剩余容量是M-w, 效益增长了p,优化值间的递归式,虽然不知道优化解是否放物品1,但从优化原理我们能建立优化值间的递归式 设f(i, y)为以背包容量y,放物品i,n,得到的优化效益值,以下递归关系成立: f(1,c)=maxf(2,c), f(2,c-w1)+p1 先求子问题的优化值(递归),再从2种可能性中求出最优的. 须对任意给定容量y, 任意i,n 种物品求解子问题.,放进物品1(x1 = 1),背包容量还剩r=16 x2,x3= 1,0 为子问题的优化解,值为18，总效益值为20+18=38 不放物品1(x1= 0)则对于剩下的两种物品而言,容量限制条件为116，1,1为子问题优化解,值为33 前者效益值为38, 后者为33; 所以优化解为1,1,0, 优化值为38,例题： n=3, c=116 w=100,14,10 p=20,18,15,令f(i,y) 表示容量为y,物品i,i+1,n 的优化效益值,按优化原理可列递归关系如下：,初始背包问题的递归方程 f(1,c)=maxf(2,c),f(2,c-w1)+p1 迭代 计算从f(n, *)开始(15-1)式) 然后应用(15-2)式递归计算f(i,*) ( i=n-1,n-2，,2 )， 最后得出 f(1,c),初始化：,利用递归式（15-2），可得：,因此最优解 f(1,116 )=maxf(2,116)，f(2,116-w1)+p1 =maxf(2,116),f(2,16)+20 =max33,38=38,例题 n=3, w=100,14,10, p=20,18,15, c=116,求解优化解：traceback方法计算x1,xn值: f(1,c) =f(2,c)=x1=0；否则x1=1,c=c-w1。 x2: f(2,c)=f(3,c)= x2=0否则x2=1,c=c-w2 Xi: f(i,c)=f(i+1,c)= xi=0否则xi=1,c=c-wi 该例中, f(2,116)=33f(1,116),所以x1=1. 剩余容量=116-100=16, f(2,16)=18,f(3,16)= 14f(2,16),因此x2=1 此时r=16-14=2,不足以放物品3,所以x3= 0,如果设fi(M)是KNAP(1,j,X)最优解得值，那么fn(M)可以表示为 fn(M)=max fn-1(M),fn-1(M-wn）+pn 对于任意fi(X),这里i0,则有 fi(X)=Max(fi-1(X),fi-1(X-wi)+pi,6.6 可靠性设计,6.7货郎担问题,货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅经过一次，最后仍回到原出发的城镇，问应如何选择行走路线可使总行程最短，这是运筹学的一个著名的问题。 实际中有很多问题可以归结为这类问题。,哈密尔顿回路：（环球旅行问题）即从一个结点出发，经过所有结点回到出发点（结点不能重复经过）。,设v1，v2，vn是已知的n个城镇，城镇vi到城镇vj的距离为dij，现求从v1出发，经各城镇一次且仅一次返回v1的最短路程。,问题描述：,解决方案： 1.穷举法？ 2.动态规划？,设S表示从v1到vi中间所可能经过的城市集合，S实际上是包含除v1和vi两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。 阶段： S中的点的个数,建立动态规划模型：,状态变量（i，S）表示：从v1点出发，经过S集合中所有点一次最后到达vi。 最优指标函数fk（i，S）为从v1出发，经过S集合中所有点一次最后到达vi。 决策变量Pk（i，S）表示：从v1经k个中间城镇的S集合到vi城镇的最短路线上邻接vi的前一个城镇，则动态规划的顺序递推关系为：,建立动态规划模型：,fk（i，S）= min fk-1（j，S、 j +dji j属于S f0（i，空集）=d1i （k=1，2，,n-1, i=2,3,n),例12 已知4个城市间距离如下表，求从v1出 发，经其余城市一次且仅一次最后返回v1的最短路径和距离。,解：K=0 由边界条件（7.21b)知: f0(2,空集)=d12=6 f0(3,空集)=d13=7 f0(4,空集)=d14=9,当k=1时: 从城市V1出发,经过1个城镇到达Vi的最短距离为: f1(2, 3 ) = f0 (3, 空)+d 32 =7+8=15 f1(2, 4 ) = f0 (4, 空)+d 42 =9+8=14 f1(3, 2 ) = f0 (2, 空)+d 23 =6+9=15 f1(3, 4 ) = f0 (4, 空)+d 43 =9+5=14 f1(4, 2 ) = f0 (2, 空)+d 24 =6+7=13 f1(4, 3 ) = f0 (3, 空)+d 34 =7+8=15,例12 已知4个城市间距离如下表，求从v1出发，经其余城市一次且仅一次最后返回v1的最短路径和距离。,当k=2时, 从城市V1出发,中间经过2个城镇到达Vi的最短距离. f2(2, 3,4 ) = min f1(3,4)+d 32, f1(4,3)+ d42 =min14+8,15+5=20 P2(2,3,4)=4,f2(3, 2,4 )= min14+9,13+5=18 P2(3,2,4)=4 f2(4, 2,3 )= min15+7,15+8=22 P2(4,2,3)=2,当k=3时: 从城市V1出发,中间经过3个城镇最终回到Vi的最短距离. f3(1, 2,3, 4 )= minf2(2, 3,4 ) + d 21, f2(3, 2,4 )+ d 31, f2(4, 2,3 ) + d 41 =min20+8,18+5,22+6=23 P3(1,2,3,4)=3,逆推回去,货郎的最短路线是12431, 最短距离为23.,货郎担问题当城市数目增加时,用动态规划方法求解,无论是计算量还是存储量都会大大增加,所以本方法只适用于n较小的情况.,在很多货郎担问题中，经常会看到dij不等于dji的情况。,这是因为：1，各城市之间可能是复线2，两地之间可能会使用不同的交通工具从而费用不同。,实际中很多问题都可以归结为货郎担这类问题. 如: 1,物资运输路线中,汽车应该走怎样的路线使路程最短; 2,工厂里在钢板上要挖一些小圆孔,自动焊接机的割咀应走怎样的路线使路程最短; 3,城市里有一些地方铺设管道时,管子应走怎样 的路线才能使管子耗费最少,等等,6.8流水作业调度,n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。,分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 设全部作业的集合为N=1，2，n。SN是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。,流水作业调度,设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器M2的等待时间为b(1)时，安排作业(2)，(n)所需的时间。 记S=N-(1)，则有T=T(S,b(1)。,证明：事实上，由T的定义知TT(S,b(1)。若TT(S,b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度。则(1)， (2)， (n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S,b(1)。这就证明了流水作业调度问题具有最优子结构的性质。,由流水作业调度问题的最优子结构性质可知，,Johnson不等式,对递归式的深入分析表明，算法可进一步得到简化。 设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i, (2)=j。则由动态规划递归式可得: T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij) 其中，,如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。,流水作业调度的Johnson法则,交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji) 其中， 当作业i和j满足Johnson不等式时，有 由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度 ，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意ij有 由此可知，所有满足Johnson法则的调度均为最优调度。,算法描述,流水作业调度问题的Johnson算法 (1)令 (2)将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序； (3)N1中作业接N2中作业构成满足Johnson法则的最优调度。,算法复杂度分析： 算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。,0-1背包问题,给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。,0-1背包问题,设所给0-1背包问题的子问题,的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。,算法复杂度分析： 从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。,算法改进,由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。,对每一个确定的i(1in)，用一个表pi存储函数m(i，j)的全部跳跃点。表pi可依计算m(i，j)的递归式递归地由表pi+1计算，初始时pn+1=(0，0)。,一个例子,n=3，c=6，w=4，3，2，v=5，2，1。,函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集pi+1与函数m(i+1，j-wi)+vi的跳跃点集qi+1的并集中。易知，(s,t)qi+1当且仅当wisc且(s-wi,t-vi)pi+1。因此，容易由pi+1确定跳跃点集qi+1如下qi+1=pi+1(wi,vi)=(j+wi,m(i,j)+vi)|(j,m(i,j)pi+1 另一方面，设(a，b)和(c，d)是pi+1qi+1中的2个跳跃点，则当ca且db时，(c，d)受控于(a，b)，从而(c，d)不是pi中的跳跃点。除受控跳跃点外，pi+1qi+1中的其它跳跃点均为pi中的跳跃点。 由此可见，在递归地由表pi+1计算表pi时，可先由pi+1计算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳跃点得到表pi。,算法改进,一个例子,n=5，c=10，w=2，2，6，5，4，v=6，3，5，4，6。,初始时p6=(0,0)，(w5,v5)=(4,6)。因此，q6=p6(w5,v5)=(4,6)。 p5=(0,0),(4,6)。 q5=p5(w4,v4)=(5,4),(9,10)。从跳跃点集p5与q5的并集p5q5=(0,0),(4,6),(5,4),(9,10)中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p4=(0,0),(4,6),(9,10) q4=p4(6，5)=(6，5)，(10，11) p3=(0，0)，(4，6)，(9，10)，(10，11) q3=p3(2，3)=(2，3)，(6，9) p2=(0，0)，(2，3)，(4，6)，(6，9)