算法设计和分析6章-动态规范算法-PPT精品课件.ppt

1、算法设计与分析*河南工程学院算法设计与分析*河南工程学院 6.1 一般方法 6.2 多段图 6.3 每对节点之间的最短路径 6.4 最优二分检索树 6.5 0/1背包问题 6.6 可靠性设计 6.7 货郎担问题 6.8 流水线调度问题算法设计与分析*河南工程学院 学习要点学习要点:理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。算法设计与分析*河南工程学院 通过应用范例学习动态规

2、划算法设计策略。(1)多段图（2）每对节点间的最短路径（3）最优二分检索树；（4）0/1 背包问题 （5）可靠性设计；（6）货郎担问题（7）流水作业调度；算法设计与分析*河南工程学院6.1 一般方法 把已知问题分为许多阶段或许多子问题，然后按顺序求解各个子问题。在每种情况下，列出各种可能的局部解，然后根据某些条件，从局部中挑选中那些有可能产生最优结果的解 前一个子问题的解为后一个子问题的求解提供有用的信息，从而大大减少了计算量算法设计与分析*河南工程学院 最优性原理：不论初始状态和第一步决策是什么，余下的决策必须按照前一次决策所产生的新状态构成一个最优决策序列。不论前面的状态和策略如何，后面的

3、最优策略只取决于由最初策略所决定的当前状态算法设计与分析*河南工程学院 动态规划的向前处理法：从最后阶段开始，以逐步向前递推的方式求出前一阶段决策值的递推关系式，即根据xi+1,xn的那些最优决策来求取xi决策值的关系式 列出关系式后，由最后阶段开始，回溯求解这些关系式得出最优决策序列算法设计与分析*河南工程学院6.2 多段图 多段图G=(V,E)是一个有向图。它具有如下的特性：图中的节点被划分成k=2个不相交的集合Vi,1=i=k，其中Vi和Vk分别只有一个节点s(源点）和t（汇聚点）。图中的所有的边均具有如下性质：若u Vi,则v Vi+1,1=ik-1,且没条边均附有成本c(u,v);从

4、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的路径。与假设相矛盾，故最优性原理成立。算法设计与分析*河南

5、工程学院123456781291110StV2V3V497324227111186543156425算法设计与分析*河南工程学院 设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是

6、这样的一个节点，属于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,1=i=n;当E(G)时，C(i,j)表示边的长度；ij算法设计与分析*河南工程学院6.4 最优二分检索树 检索一个二分检索树的算法：输入：二分检索树T和被查找元素X 输出：如果X不在T中，则置i=0，否则将i置成INDEXi=X算法设计与分析*河南工程学院 SEACH

7、(Elemtype T,Elemtype X)1 int it;2 while i0;3 do 4 if(xINDEXi 7 iRCHILDi)8 else xINDEXi;9 return i;10 算法设计与分析*河南工程学院查找成功与不成功的概率二查找树的期望耗费有 个节点的二叉树的个数为：穷举搜索法的时间复杂度为指数级110niniiiqpniiiTniiiTniiiTniiiTqdpkqdpkTE0101)(depth)(depth1)1)(depth()1)(depth()incost search(n)/4(2/3nn0d1d2d3d4d5d1k2k3k4k5k算法设计与分析*河

8、南工程学院2.80 Total0.40 0.10 3 0.20 0.05 3 0.20 0.05 3 0.20 0.05 3 0.30 0.10 2 0.15 0.05 2 0.60 0.20 2 0.20 0.10 1 0.15 0.05 2 0.10 0.10 0 0.30 0.15 1 oncontributiy probabilit depth node54321 054321ddddddkkkkk0d1d2d3d4d5d1k2k3k4k5k算法设计与分析*河南工程学院最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由最优二叉搜索树问题的最优子结构性质可建立计算pij

9、的递归式如下记wi,jpi,j为m(i,j)，则m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为注意到，可以得到O(n2)的算法min,1,11,1,jkjkkikijkijijijipwpwwpwniiimjijkmkimwjimjkiji1,0)1,(),1()1,(min),(,),1()1,(min),1()1,(min11jkmkimjkmkimjiskjisjki算法设计与分析*河南工程学院0/1背包问题(0/1 Knapsack)问题描述 有n种可选物品1,n，放入容量为c的背包内，使装入的物品具有最大效益 表示 n,c 分别为物品个数和背包容量

10、 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=10p=6,3,5,4,

11、6w=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

12、 种物品求解子问题.算法设计与分析*河南工程学院放进物品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,10p=20,18,15,算法设计与分析*河南工程学院 令f(i,y)表示容量为y,物品i,i+1,n 的优化效益值,按优化原理可列递归关系如下：初始背包问题的递归方程 f(1,c)=maxf(2,c),f(2,c-w1)

13、+p1 迭代 计算从f(n,*)开始(15-1)式)然后应用(15-2)式递归计算f(i,*)(i=n-1,n-2，,2)，最后得出 f(1,c)115(00),(nnnwywypynf)215(0),1(),1(),1(max),(iiiiwyyifwypwyifyifyif算法设计与分析*河南工程学院 初始化：10,15100,0),3(yyyf 利用递归式（15-2），可得：24,332414,181410,15100,0),2(yyyyyf 因此最优解f(1,116)=maxf(2,116)，f(2,116-w1)+p1 =maxf(2,116),f(2,16)+20 =max33,3

14、8=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算法设计与分

15、析*河南工程学院 如果设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.76.7货郎担问题货郎担问题 货郎担问题一般提法为：一个货郎从某城镇货郎担问题一般提法为：一个货郎从某城镇出发，经过若干个城镇一次，且仅经过一次，出发，经过若干个城镇一次，且仅经过一次，最后仍回到原出发的城镇，问应如何选择行最后仍回到原出发的城镇，问应如何选择行走

16、路线可使总行程最短，这是运筹学的一个走路线可使总行程最短，这是运筹学的一个著名的问题。著名的问题。实际中有很多问题可以归结为这类问题。实际中有很多问题可以归结为这类问题。算法设计与分析*河南工程学院哈密尔顿回路哈密尔顿回路：（环球旅行问题）（环球旅行问题）即从一个结点出发，即从一个结点出发，经过所有结点回到经过所有结点回到出发点（结点不能出发点（结点不能重复经过）。重复经过）。算法设计与分析*河南工程学院 设设v1，v2，.，vn是已知的是已知的n个城镇，个城镇，城镇城镇vi到城镇到城镇vj的距离为的距离为dij，现求从，现求从v1出发，出发，经各城镇一次且仅一次返回经各城镇一次且仅一次返回v

17、1的最短路程。的最短路程。问题描述：问题描述：解决方案：解决方案：1.穷举法？穷举法？2.动态规划？动态规划？算法设计与分析*河南工程学院 设设S表示从表示从v1到到vi中间所可能经过的城市集中间所可能经过的城市集合，合，S实际上是包含除实际上是包含除v1和和vi两个点之外的其余点两个点之外的其余点的集合，但的集合，但S中的点的个数要随阶段数改变。中的点的个数要随阶段数改变。阶段阶段：S中的点的个数中的点的个数建立动态规划模型：建立动态规划模型：算法设计与分析*河南工程学院状态变量（状态变量（i，S）表示：从表示：从v1点出发，经过点出发，经过S集合中所集合中所有点一次最后到达有点一次最后到达

18、vi。最优指标函数最优指标函数fk（i，S）为从为从v1出发，经过出发，经过S集合中所集合中所有点一次最后到达有点一次最后到达vi。决策变量决策变量Pk（i，S）表示：从表示：从v1经经k个中间城镇的个中间城镇的S集集合到合到vi城镇的最短路线上城镇的最短路线上邻接邻接vi的前一个城镇，则动态的前一个城镇，则动态规划的顺序递推关系为：规划的顺序递推关系为：建立动态规划模型：建立动态规划模型：算法设计与分析*河南工程学院 fk（i，S）=min fk-1（j，S、j+djij属于属于Sf0（i，空集），空集）=d1i （k=1，2，,n-1,i=2,3,n)算法设计与分析*河南工程学院 例例12

19、 已知已知4个城市间距离如下表，求从个城市间距离如下表，求从v1出出 发，经其余城市一次且仅一次最后返回发，经其余城市一次且仅一次最后返回v1的最短的最短路径和距离。路径和距离。Vj距离Vi 1 2 3 4 1 0 6 7 9 2 8 0 9 7 3 5 8 0 8 4 6 5 5 0算法设计与分析*河南工程学院解：解：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

20、,空空)+d 32=7+8=15f1(2,4)=f0(4,空空)+d 42=9+8=14f1(3,2)=f0(2,空空)+d 23=6+9=15f1(3,4)=f0(4,空空)+d 43=9+5=14f1(4,2)=f0(2,空空)+d 24=6+7=13f1(4,3)=f0(3,空空)+d 34=7+8=15 算法设计与分析*河南工程学院例12 已知4个城市间距离如下表，求从v1出发，经其余城市一次且仅一次最后返回v1的最短路径和距离。Vj距离Vi 1 2 3 4 1 0 6 7 9 2 8 0 9 7 3 5 8 0 8 4 6 5 5 0算法设计与分析*河南工程学院当当k=2时时,从城市

21、从城市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,f

22、2(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 n较小的情况较小的情况.算法设计与分析*河南工程学院在很多货郎担问题中，经常会看到在很多货郎担问题中，经常会看到dij不等于不等于dji的情的情况。况。

23、Vj距离Vi 1 2 3 4 1 0 6 7 9 2 8 0 9 7 3 5 8 0 8 4 6 5 5 0 这是因为：这是因为：1，各城市之间可能是复线，各城市之间可能是复线2，两地之，两地之间可能会使用不同的交通工具从而费用不同。间可能会使用不同的交通工具从而费用不同。算法设计与分析*河南工程学院实际中很多问题都可以归结为货郎担这类问题实际中很多问题都可以归结为货郎担这类问题.如如:1,物资运输路线中物资运输路线中,汽车应该走怎样的路线使路汽车应该走怎样的路线使路程最短程最短;2,工厂里在钢板上要挖一些小圆孔工厂里在钢板上要挖一些小圆孔,自动焊接机自动焊接机的割咀应走怎样的路线使路程最短的

24、割咀应走怎样的路线使路程最短;3,城市里有一些地方铺设管道时城市里有一些地方铺设管道时,管子应走怎样管子应走怎样的路线才能使管子耗费最少的路线才能使管子耗费最少,等等等等算法设计与分析*河南工程学院n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。分析：分析：直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况

25、下，机器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

26、的等待时间为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)。这就证明了流水作业调度问题具有最优子结构的性质。由流水作业调度问题的最优子结构性质可知，),(min)0,(1iinibiNTaNT)0,max,(min),(iiiSiatbiSTatST算法设计与分析*河南工程学院对递归式的深入分析表明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i,(2)=j。则由动态规划递归式可得:T(S,t)=ai

27、+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，,max0,max,0,maxmax0,0,maxmaxiijiijijijijijijijijjiijijabaataabbbaatabbbaatabbaatbbt如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足JohnsonJohnson不等式不等式。算法设计与分析*河南工程学院交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji)其中，当作业i和j满足Johnson不等式时，有由此可见当作业i和作业j不满足Johns

28、on不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意i2n时，算法需要(n2n)计算时间。算法设计与分析*河南工程学院由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1in)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。对每一个确定的i(1in)，用一个表pi存储函数m(i，j)的全部跳跃点。表pi可依计算m(i，j)的递归式递归地由

29、表pi+1计算，初始时pn+1=(0，0)。算法设计与分析*河南工程学院n=3，c=6，w=4，3，2，v=5，2，1。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)算法设计与分析*河南工程学院函数m(i,j)是由函

30、数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+1q

31、i+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,

32、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)，(9，10)，(10，11)q2=p2(2，6)=(2，6)，(4，9)，(6，12)，(8，15)p1=(0，0)，(2，6)，(4，9)，(6，12)，(8，15)p1的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。算法设计与分析*河南工程学院上述算法的主要计算量在于计算跳跃点集pi(1in)。由于qi+1=pi

33、+1(wi，vi)，故计算qi+1需要O(|pi+1|)计算时间。合并pi+1和qi+1并清除受控跳跃点也需要O(|pi+1|)计算时间。从跳跃点集pi的定义可以看出，pi中的跳跃点相应于xi,xn的0/1赋值。因此，pi中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集pi所花费的计算时间为从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1in)是整数时，|pi|c+1，(1in)。在这种情况下，改进后算法的计算时间复杂性为O(minnc,2n)。nniinniOOipO22|1|22算法设计与分析*河南工程学院 二叉搜索树（1）若它的左子树不空，则左子树上所有节

34、点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3 它的左、右子树也分别为二叉排序树45125333724100619078在随机的情况下，二叉查找树的平均查找长度和 是等数量级的nlog算法设计与分析*河南工程学院动态规划小结:一般步骤 确定决策序列(Decision sequences)明确问题状态(Problem states)验证优化原理(Principle of optimal)构造、求解优化值递归方程(Recurrence equation)回溯(traceback)构造优化解(Optimal solution)算法复杂性 动态规划递归方程往往不能直接用递归实现,会引发大量重复计算,算法的计算量将非常可观。最好是用迭代法求解动态规划法列出的递归方程 迭代实现需要存贮所有子问题的优化解的值，因此动态规划法设计的算法往往需要较大的存储空间 算法的复杂性来自子问题的数目,通常子问题的数目往往很大