算法 第六章 动态规划_第1页
算法 第六章 动态规划_第2页
算法 第六章 动态规划_第3页
算法 第六章 动态规划_第4页
算法 第六章 动态规划_第5页
已阅读5页,还剩69页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、6.1 一般方法 6.2 多段图 6.3 多对结点之间的最短路径 6.4 最优二分检索树 6.5 0/1背包问题 6.6 可靠性设计 6.7 货郎担问题 6.8 流水线调度问题,第六章 动态规划,6.1 动态规划的一般方法,概念引入: 有这样一类问题, 它们的活动过程可分为若干个阶段, 在任一阶段后的行为都依赖于i 阶段的过程状态,而与i 阶段之前的过程无关, 这样就构成了一个多阶段决策过程。 根据这类问题多阶段决策的特性, 提出了解决这类问题的“最优性原理”,从而创建了一种新的算法设计方法动态规划。 在多阶段决策过程的每一个阶段, 都有多种决策可供选择,但必须从中选取一种。一旦各种阶段的决策

2、选定之后,就构成了一个决策序列。决策序列不同会导致问题结果也不同。,最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质: 无论过程的初始状态和初始决策是什么, 其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列,如果对于所求解的问题最优性原理成立, 则说明用动态规划方法有可能解决该问题。而解决问题的关键在于获取各阶段间的递推关系式。,动态规划的目标: 在所有允许选择的决策序列中选取一个会获得问题最优解的决策序列,即最优决策序列。,例:多段图问题(multistage graph problem),图中的结点被划分成 k 2个不相交的集合Vi

3、 , 1ik,其中V1和Vk分别只有一个结点 s (源点) 和 t ( 汇点)。 图中所有的边均具有如下性质: 若uVi ,则v Vi+1 ,1ik,且每条边均附有成本c(u, v)。 从s到t的一条路径成本是这条路径上边的成本和。 多段图问题是求由s到t的最小成本路径。,多段图G(V, E)是一个有向图, 它具有如下特性:,假设s,v2,v3,vk-1,t是一条由s到t的最短路径 再假设从源点s开始,已作出了到结点V2的决策,因此V2就是初始决策所产生的状态 如果把V2看成是原问题的一个子问题的初始状态,解决这个子问题就是找出一条由V2到t的最短路径 这条最短路径显然是v2,v3,vk-1,

4、t 如果不是,设v2,q3,qk-1,t由V2到t的更短路径,则这条路径肯定比v2,v3,vk-1,t路径短,这与假设矛盾,因此最优性原理成立,最优性原理对多段图成立,0/1背包问题,背包问题中的xj限定只能取0或1值,用KNAP(l,j,X)来表示这个问题,效益值,背包容量,若对于有n个物品,容量为M的背包,则0/1背包问题就可表示为KNAP(1,n,M),0/1背包问题的最优性原理证明,设y1,y2,yn分别为x1,x2,xn的0/1值的最优序列。 若y1=0,则y2,y3,yn必须相对于KNAP(2,n,M)问题构成一个最优序列。如若不然,则y1,y2,yn就不是KNAP(1,n,M)的

5、最优序列。 若y1=1,则y2,y3,yn必须是KNAP(2,n,M-w1)的最优序列。如若不然,则必有另一个0/1序列z2,z3,zn使得wizi M- w1(2in)且pizi piyi(2in) 因此,序列y1,z2, z3,zn是一个对问题KNAP(1,n,M)具有更大效益值的序列。这与假设相矛盾,所以0/1背包问题的最优性原理成立。,最优化决策序列的表示,设S0是问题的初始状态, 假定要作n次决策xi, 1in X1=r1, 1, r1, 2, , r1, p1是x1的可能决策值的集合, 而 S1, 1是在选取决策值r1, j1以后所产生的状态, 1j1p1,如果已作了k-1次决策,

6、 1k-1n ,设x1,xk-1的最优决策值是r1,.,rk-1,它们所产生的状态为S1,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,向前处理法(forward approach) 最优决策序列的表示法启发我们从最后阶段开始,以逐步向前递推的方式, 列出求解前一阶段决策值的递推关系式, 即根据xi+1, xn的那些最优决策序列来列出求取x

7、i决策值的关系式,向后处理法(backward approach) 从初始阶段开始, 以逐步向后递推的方式, 列出求解后一阶段决策值的递推关系式, 即根据x1, xi-1的那些最优决策序列来列出求取xi决策值的关系式,6.2 多段图,向前处理法: 从最后阶段开始, 逐步向前递推, 根据xi+1, xn的那些最优决策序列来列出求取xi 决策值的关系式,设P(i, j)是一条从Vi中的节点j 到汇点t 的最小成本路径, COST(i, j)表示这条路径的成本, 根据向前处理方法有公式4.5 : COST(i, j)= min c(j, l )+ COST(i+1, l) 其中: lVi+1 , 边

8、E, c(j, l)表示该边的成本,对于k段图, 当i=k-1时, 有COST(k-1, j)= c(j, t), 所以可以通过公式4.5,对所有jVk-2, 计算COST(k-2, j), 再对所有的jVk-3, 计算COST(k-3, j), 依次向前求解, 最后计算出COST(1, s),多段图向前处理的算法,多段图向前处理算法的计算过程,COST(4, 9)=c(9,12)=4 COST(4,10)=c(10,12)=2 COST(4,11)=c(11,12)=5,COST(3,6)=minc(6,9)+COST(4,9) , c(6,10)+COST(4,10) =min6+4, 5

9、+2=7 COST(3,7)=minc(7,9)+COST(4,9) , c(7,10)+COST(4,10) =min4+4, 3+2=5 COST(3,8)=minc(8,10)+COST(4,10) , c(8,11)+COST(4,11) =min5+2, 6+5=7,COST(i, j)=min c(j, l)+ COST(i+1, l) l Vi+1 , c(j, l)表示该边的成本,COST(2,2) =minc(2,6)+COST(3,6), c(2,7)+COST(3,7), c(2,8)+COST(3,8) =min4+7, 2+5, 1+7=7,COST(3,6)=7 C

10、OST(3,7)=5 COST(3,8)=7,COST(2,3)=min2+7,7+5=9 COST(2,4)=min11+7=18 COST(2,5)=min11+5,8+7=15,COST(1,1) =minc(1,2)+COST(2,2), c(1,3)+COST(2,3), c(1,4)+COST(2,4), c(1,5)+COST(2,5) =min9+7,7+9,3+18,2+15=16,在计算每个COST(i, j)的同时, 记下每个状态(结点j)所做出的决策(即l 的取值),令D(i, j)= l, 则容易求出这条最小成本的路径,COST(2,2)=minc(2,6)+COST

11、(3,6), c(2,7)+COST(3,7), c(2,8)+COST(3,8) =7,COST(1,1)=minc(1,2)+COST(2,2), c(1,3)+COST(2,3), c(1,4)+COST(2,4), c(1,5)+COST(2,5)=16,D(1, 1)=2,D(2, 2)=7 D(2, 3)=6 D(2, 4)=8 D(2, 5)=8,D(3, 6)=10 D(3, 7)=10 D(3, 8)=10,COST(3,6)=minc(6,9)+COST(4,9) , c(6,10)+COST(4,10)=7,12,7,10,12,最小成本的路径为:,多段图的向前处理算法

12、procedure FGRAPH(E,k,n,P) real COST(n); int D(n-1), P(k), r, j, k, n; COSTn=0; for j=n-1 downto 1 do 寻找结点r, 满足E且使c(j,r)+COST(r)值最小 COSTj=c(j,r)+COSTr; Dj=r ; P1=1; Pk=n; for j=2 to k-1 do Pj=DPj-1 ; end FGRAPH,为了算法描述的简单, 对结点进行编号, 从V1开始 s 编为1号, 然后V2中的结点依次编为2,3,4,5号, 按此规则编下去, 最后V5的结点t 编为12号, 有了编号可以将CO

13、ST, D中表示段数的第一个下标省略,通过计算找到一条最小成本的路径,数组p用来保存最小成本路径上结点,编程实现算法时要先将多段图用邻接表表示,邻接表: 邻接表是图的一种链式存储结构, 对图中的每个顶点建立一个单链表, 链表中的结点有3个域, 分别存储顶点, 边的成本和下一个结点的指针.,k=5; n=12; COST12=0; for j=11 downto 1 do COSTj=minc(j,r)+COSTr; Dj=r ; P1=1; Pk=12; for j=2 to 4 do Pj=DPj-1 ;,COST,D,P,COST(11)=5 COST(10)=2 COST(9)=4,5,

14、12,COST(8)=7 COST(7)=5 COST(6)=7,D(8)=10 D(7)=10 D(6)=10,7,10,COST(5)=15 COST(4)=18 COST(3)=9 COST(2)=7,D(11)=12 D(10)=12 D(9)=12,D(5)=8 D(4)=8 D(3)=6 D(2)=7,15,8,D(1)=2,COST(1)=16,16,2,2,7,10,算法的执行过程,多段图向后处理的算法,对于k段图, 当i=2时, 有BCOST(2, j)= c(1, j), 所以可以通过公式4.6,对所有jV3, 计算BCOST(3, j), 依次向后求解, 最后计算出BCO

15、ST(k, t); 同样的, 在计算每个BCOST(i, j)的同时, 记下每个状态所做出的决策(即l 的取值),令D(i, j)= l 由于我们已经按规则对结点进行了编号, 所以这里可以省略BCOST和D中的第一个下标,设BP(i, j)是一条从源点s到 Vi中的结点j的最小成本路径, BCOST(i, j)表示这条路径的成本, 根据向后处理方法有公式4.6 : BCOST(i, j)= minBCOST(i-1, l)+ c( l , j ) 其中: lVi-1 , 边E, c(l, j)表示该边的成本,多段图向后处理算法的计算过程,BCOST(j)=minBCOST(l)+ c( l ,

16、 j),BCOST(2)=c(1,2)=9 BCOST(3)=c(1,3)=7 BCOST(4)=c(1,4)=3 BCOST(5)=c(1,5)=2,BCOST(6)=minBCOST(2)+c(2,6), BCOST(3)+c(3,6) = min9+4,7+2=9 BCOST(7)=11 BCOST(8)=10,D(2)=1 D(3)=1 D(4)=1 D(5)=1,D(6)=3 D(7)=2 D(8)=2,D(9)=6 D(10)=6 D(11)=8,BCOST(9)=15 BCOST(10)=14 BCOST(11)=16,BCOST(12)=16 D(12)=10,1,3,6,10

17、12,最小成本的路径为:,procedure BGRAPH(E,k,n,P) real BCOST(n); int D(n-1), P(k), r, j, k, n; BCOST1=0; for j=2 to n do 寻找结点r, 满足E且使BCOST(r)+c(r, j)值最小 BCOSTj= BCOSTr+c(r, j); Dj=r ; P1=1; Pk=n; for j=k-1 downto 2 do Pj=DPj+1 ; end BGRAPH,多段图的向后处理算法,对于向后处理算法多段图用反邻接表来存储,资源分配问题例子 N(i,j)把j个资源分配给项目i获得的利润 V(i,j)前i

18、-1个项目已经分配了j个资源,问题: 同时求任意结点间的最短路径 允许负成本 思路: 以中间点最大不超过的编号为契机,开始递归过程 相当于每次迭代中考虑一个新增结点对所有最短路径的影响,6.3 每对结点间的最短路径,一种简便算法!,例子,例子,6.4 最优二分检索树,二分检索树: T是一个二叉树,它或者为空, 或者其每个结点含有一个可比较大小的数据元素, 并且: T的左子树的所有元素比根结点T中的元素小 T的右子树的所有元素比根结点T中的元素大 T的左、右子树也是二分检索树 注意: 二分检索树中的所有结点的元素是互异的,为确定X是否在二分检索树中出现, 先将X与根比较: 若X比根中的元素小则检

19、索左子树 若X等于根中的元素则检索成功终止 若X比根中的元素大则检索右子树,检索二分检索树的算法: procedure SEARCH(T, X, i) i =T; while i0 do if XIDENT(i) then i=RCHILD(i); end SEARCH,二分检索树的每个结点有3个信息段, LCHILD, RCHILD, IDENT; 若X不在T中, 则i=0,例: 已知标识符集(a1,a2,a3,a4,a5)=(for,if,loop,repeat,while) 有以下2种不同的二分检索树,图a所示的树在最坏情况下检索一个标识符需要进行4次比较,而图b所示的树只需要3次比较

20、假设检索每个标识符具有相同的概率1/5, 并设都能成功检索, 则在平均情况下, 图a的树需要12/5次比较, 图b的树需要11/5次比较,一般情况下, 要检索的那些标识符具有不同的概率, 而且存在不成功检索的情况, 用圆结点(内结点)表示给出的n个标识符,方结点(外结点)表示不成功检索的情况, 有n+1个外结点,一次成功检索在一个内结点(l 级)处终止, 算法中的循环要执行l 次, 所以内结点ai的预期成本为P(i)*level(ai),一次不成功检索在一个外结点处(l 级)终止, 算法中循环要执行l-1次, 所以外结点Ei的预期成本为Q(i)*(level(Ei)-1),定义标识符集(a1,

21、 a2, an)的最优二分检索树是一棵使P(i)*level(ai)+Q(i)*(level(Ei)-1)取最小值的树,例:标识符集(a1, a2, a3)=(do, if, stop) 有5种可能的二分检索树,1.设内外结点具有相同的概率P(i)=Q(i)=1/7 2.设内外结点的概率不同 P(i)=(0.5, 0.1, 0.05), Q(i)=(0.15,0.1,0.05,0.05),cost(a)=P(1)*3+P(2)*2+P(3)*1 +Q(0)*3+Q(1)*3+Q(2)*2+Q(3)*1,cost(a-1)=3*1/7+2*1/7+1/7 +3*1/7+3*1/7+2*1/7+1

22、/7 =15/7 cost(a-2)=3*0.5+2*0.1+0.05 +3*0.15+3*0.1+2*0.05+0.05 =2.65,最优二分检索树,cost(b-1)=13/7 cost(b-2)=1.9,cost(c-1)=15/7 cost(c-2)=1.5,cost(d-1)=15/7 cost(d-2)=2.15,cost(e-1)=15/7 cost(e-2)=1.6,cost(a-1)=15/7 cost(a-2)=2.65,对于第1种情况内、外结点概率相同, 图b所示的树最优 对于第2种情况内、外结点概率不同, 图c所示的树最优,将动态规划应用于最优二分检索树,选择a2作为根

23、结点(即k=2) 内结点a1和外结点E0,E1在左子树上, 内结点a3,a4,a5和外结点E2,E3,E4,E5在右子树上,对于ai, 1in, 决策出哪一个作为T的根结点, 如果选择ak作为根结点, 那么内结点a1,a2,ak-1和外结点E0,E1,Ek-1都将位于这个根的左子树上, 而内结点ak+1,an和外结点Ek,En将位于这个根的右子树上,注意: 上2式中级数的测定是把各子树的根作为第一级, 所以在计算整棵树的成本时还要加上一部分成本,树T的预期成本:P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n),例: 选a2为根结点 , k=2, 设P(i)=Q(i)=1

24、/7 COST(L)=P(1)*1+Q(0)*1+Q(1)*1=1*1/7+1*1/7+1*1/7=3/7 COST(R)=P(3)*1+Q(2)*1+Q(3)*1=1*1/7+1*1/7+1*1/7=3/7 W(0,k-1)=W(0,1)=Q(0)+Q(1)+P(1)=1/7+1/7+1/7=3/7 W(k,n)=W(2,3)=Q(2)+Q(3)+P(3)= 1/7+1/7+1/7=3/7 COST(T)=P(2)+COST(L)+COST(R)+W(0,1)+W(2,3) =1/7+3/7+3/7+3/7+3/7=13/7,二分检索树T的预期成本: P(k)+COST(L)+COST(R)

25、+W(0,k-1)+W(k,n),用c(i,j)表示包含ai+1, aj和Ei,Ej的二分检索树的成本,树T的预期成本: P(k)+C(0, k-1)+C(k, n)+W(0, k-1)+W(k, n),将上式一般化,对于任何c(i,j)有下式:,按上式逐步计算, 最后可求出C(0,n)。首先计算使j-i=1的C(i , j) (注意: C(i, i)=0, W(i, i)=Q(i), 0in), 然后依次计算使j-i=2的C(i , j), 使j-i=3的C(i , j)等等。在计算期间记下每棵树Tij的根R(i,j), 那么最优二分检索树就由这些R(i,j)构造出来。( R(i,j)是使C

26、(i,j)=minC(i, k-1)+C(k, j)+W(i, j)取最小值的k值 ),P(k)+Q(i)+Q(i+1)+P(i+1)+Q(k-1)+P(k-1) +Q(k)+Q(k+1)+P(k+1)+Q(j)+P(j)=W(i,j),例: n=4,(a1,a2,a3,a4)=(do, if, read, while) P(1:4)=(3,3,1,1); Q(0:4)=(2,3,1,1,1) (为计算方便P,Q的值都乘了16),W(0,1)=Q(0)+Q(1)+P(1)=2+3+3=8,R(0,1)=k=1,W(1,2)=Q(1)+Q(2)+P(2)=3+1+3=7,R(1,2)=k=2,W

27、(2,3)=3 C(2,3)=3 R(2,3)=k=3,W(3,4)=3 C(3,4)=3 R(3,4)=k=4,ji=1时, 0i4,ji=2时, 0i3,W(0,2)=Q(0)+Q(1)+P(1)+Q(2)+P(2)=2+3+3+1+3=12,P(1:4)=(3,3,1,1); Q(0:4)=(2,3,1,1,1),=min0+7,8+0+12=19,R(0,2)=k=1,W(1,3)=Q(1)+Q(2)+P(2)+Q(3)+P(3)=3+1+3+1+1=9,=min0+3,7+0+9=11,R(1,3)=k=2,W(2,4)=5 C(2,4)=8 R(2,4)=k=3,ji=3时, 0i

28、2,W(0,3)=Q(0)+Q(1)+P(1)+Q(2)+P(2)+Q(3)+P(3)=2+3+3+1+3+1+1=14,P(1:4)=(3,3,1,1); Q(0:4)=(2,3,1,1,1),=min0+12,8+3,19+0+14=11+14=25,R(0,3)=k=2,W(1,4)=11 C(1,4)=19 R(1,4)=k=2,ji=4时, 0i1,W(0,4)=Q(0)+Q(1)+P(1)+Q(2)+P(2)+Q(3)+P(3)+Q(4)+P(4)=16,=min0+19,8+8,19+3,25+0+16=16+16=32,R(0,4)=k=2,从表中可看出C(0,4)是关于(a1

29、,a2,a3,a4)的二分检索树的最小成本。树T04的根是a2, 其左子树是T01, 右子树是T24,T01的根是a1, 其左右子树是T00,T11,T24的根是a3, 其左右子树是T22,T34,T34的根是a4, 其左右子树是T33,T44,6.5 0/1背包问题,0/1背包问题要求物品或者整件装入背包中, 或者根本不装入(即不能装入物品的一部分), 所以xi限定只能取0或1值, 可以用KNAP(1, n, M)表示这个问题,最优性原理对0/1背包问题成立,假设y1,y2,yn是最优解, 若y1=0,则y2,y3,yn 必须是KNAP(2, n, M)的一个最优序列,否则y1,y2,yn就

30、不是KNAP(1, n, M)的最优序列; 若y1=1, 则y2,y3,yn 必须是KNAP(2, n, M-w1)的一个最优序列, 否则将存在另一个序列 z2 ,z3 , zn ,使得,那么y1, z2 ,z3 , zn 将是原问题的最优解,这与假设y1,y2,yn是最优解相矛盾,因此最优性原理对0/1背包问题成立,可以用动态规划的方法求解0/1背包问题的最优解,用向后处理法求解0/1背包问题,假设决策x的次序为x1,x2,xn, 则在对x1作出决策后,问题处于下列两种状态: x1=0, 背包剩余容量为M,没有产生任何效益 x1=1, 背包剩余容量为M-w1,效益值增加了p1 显然对x2,

31、xn的决策相对于决策了x1后所产生的问题状态应该是最优的, 否则 x1,x2,xn就不可能是最优的决策序列。,如果设fi(X)是KNAP(1,i,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 ,为了求解出fn(M), 必须从f0(X)开始, 根据递推关系式进行计算,递推求解过程如下: X0时, f0(X) = - ;X0时, f0(X)= 0 X0时, f1(X) = - 0X2时, f1(X)=maxf0(X

32、) , f0(X-2)+1=max0, - +1=0 X2时, f1(X)=maxf0(X) , f0(X-2)+1 =max0, 0+1=1,例: n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6,公式: fi(X) = max fi-1(X) , fi-1(X-wi)+pi ,X0 时, f2(X) =- 0X2时, f2(X)=maxf1(X) , f1(X-3)+2=max0 , -+2=0 2X3 时, f2(X)=maxf1(X) , f1(X-3)+2=max1 , -+2=1 3X5 时, f2(X)=maxf1(X) , f

33、1(X-3)+2=max1 , 0+2 =2 X 5 时, f2(X)=maxf1(X) , f1(X-3)+2=max1 , 1+2 =3,X0 时, f3(X) = - 0X2 时, f3(X)=maxf2(X), f2(X-4)+5=max0, - +5= 0 2X3 时, f3(X)=maxf2(X), f2(X-4)+5=max1, - +5= 1 3X4 时, f3(X)=maxf2(X), f2(X-4)+5=max2, - +5 = 2 4X5 时, f3(X)=maxf2(X), f2(X-4)+5=max2 , 0 + 5 = 5 5X6 时, f3(X)=maxf2(X)

34、, f2(X-4)+5=max3 , 0 + 5 = 5 6X7 时, f3(X)=maxf2(X), f2(X-4)+5=max3 , 1 + 5 = 6 7X9 时, f3(X)=maxf2(X), f2(X-4)+5=max3 , 2 + 5 = 7 X9 时, f3(X)=maxf2(X), f2(X-4)+5=max3 , 3 + 5 = 8,f3(X)=maxf2(X), f2(X-4)+5=max3, 1+5 = 6 f2(X)=maxf1(X), f1(X-3)+2=max1, -+2=1 f1(X)=maxf0(X), f0(X-2)+1=max0, 0+1=1,X3=1 X

35、2=0 X1=1,最优决策序列为: (x1,x2,x3)=(1,0,1),通过检测fi的取值情况可以确定最优决策序列,用图解法求解该问题 fi-1(X-wi)+pi的图像可由fi-1(X)在x轴上右移wi个单位,然后上移pi个单位得到 fi(X)的图像由fi-1(X)和fi-1(X-wi)+pi 的函数曲线按X相同时取最大值的规则归并而成,0/1背包问题实例图解法,maxfi-1(X),fi-1(X-wi)+pi,f0(X),f0(X-2)+1,f1(X),实例: n=3, (w1,w2,w3)=(2,3,4) , (p1,p2,p3)=(1,2,5) , M=6,i=2: f1(X-3)+2

36、,f2(X),i=3:f2(X-4)+5,f3(X),由图可以看出以下几点: 每一个fi 完全由一些序偶(Pj,Wj)组成的集合所说明, 其中Wj 是使fi 在其处产生一次阶跃的X值,Pj=fi(Wj) 第一对序偶(P0,W0)=(0,0); 如果有r 次阶跃, 就还有r 对序偶(Pj,Wj), 1jr ; 在r对序偶中, 假定WjWj+1, 则有PjPj+1 在0jr情况下, 对所有满足WjXWj+1的X, 有fi(X)=fi(Wj); 对所有满足XWr的X, 有fi(X)=fi(Wr),f2(X),345 , fi(4)=fi(3)=2,X5, 有fi(X)=fi(5)=3,有r =3次阶

37、跃, 有3对序偶:(P1,W1)=(1,2) (P2,W2)=(2,3),(P3,W3)=(3,5); f2是由序偶 (0,0),(1,2), (2,3), (3,5)组成的集合所说明,W,P,设Si-1表示fi-1的所有序偶的集合, Si1表示fi-1(X-wi)+pi 的所有序偶的集合, 将(pi,wi)加到Si-1的每一对序偶上就得到Si1, 然后在支配规则下将Si-1和Si1归并成Si,S0=(0, 0),S11=(1, 2),S1=(0, 0), (1, 2),S11=S0+(p1,w1)=(0,0)+(1,2)=(1,2),S1=(0, 0), (1, 2),S21=(2, 3),

38、 (3, 5),S2=(0, 0), (1, 2), (2, 3), (3, 5),S21=S1+(p2,w2)=(0,0), (1,2)+(2,3)=(1,2), (3,5),例: S2=(0,0),(1,2),(2,3),(3,5) S31=(5,4),(6,6),(7,7),(8,9),支配规则: 如果Si-1 和 Si1中一个有(Pj,Wj), 另一个有(Pk,Wk), 并且在WjWk的同时有PjPk, 那么, 序偶(Pj,Wj) 被放弃,S3=(0,0), (1,2), (2,3), (5,4), (6,6), (7,7), (8,9),根据支配规则, 54且35, 所以序偶(3,

39、5)被舍弃,注:实际运算中,按W的顺序加入,Si的推导过程,Si-1 S1i Si-1 , S1i Si WM的序偶清除 Sn不必计算,求出其最末序偶即可,例: n=3, (p1,p2,p3)=(1,2,5) ,(w1,w2,w3)=(2,3,4), M=6 S0=(0,0) 将(p1,w1)=(1,2)加到S0的序偶(0,0)上, 得S11=(1,2) S0 和S11归并, 得S1 =(0,0),(1,2) 将(p2,w2)=(2,3)加到S1的序偶(0,0)和(1,2)上, 得S21=(2,3),(3,5) S1 和S21归并, 得S2 =(0,0),(1,2),(2,3),(3,5) 将

40、(p3,w3)=(5,4)加到S2的4个序偶上, 得S31=(5,4),(6,6),(7,7),(8,9) S2 和S31归并, 根据支配规则删去(3,5), 并将WM的那些序偶除掉, 得S3 =(0,0),(1,2),(2,3),(5,4),(6,6),实例求解过程,再判断留在Sn-1的序偶(Pl,Wl)或(Pl-pn,Wl-wn)是否属于Sn-2以确定xn-1的取值。,例: S1 =(0,0),(1,2) S2 =(0,0),(1,2),(2,3),(3,5) S3 =(0,0),(1,2),(2,3),(5,4),(6,6) S3的最末序偶(Pl,Wl)=(6,6),如果已找到 Sn 的

41、最末序偶(Pl,Wl), 那么使pixi=Pl , wixi=Wl 的x1,xn的决策值可通过检索 Si 来确定,若(Pl,Wl)Sn-1,则xn=0;,若(Pl,Wl) Sn-1,且(Pl-pn,Wl-wn)Sn-1,则xn=1;,(6,6) S2, 并且(6-p3,6-w3)=(1,2) S2 , 所以x3=1,再判断留在S2的序偶(1,2), 因(1,2) S1 , 所以x2=0,(1,2) S0 , (1-p1,2-w1)=(0,0)S0,所以x1=1,最优解fn(M)的最优决策序列是(x1,x2,x3)=(1,0,1),0/1背包问题非形式化的DKP算法,procedure DKP(

42、p,w,n,M) S0 =(0,0); for i=1 to n-1 do Si1= (Pl,Wl)|(Pl-pi,Wl-wi) Si-1 and WlM Si = MERGE_PURGE(Si-1,Si1) (PX,WX) = Sn-1的最末序偶 (PY,WY) = (Pl+pn,Wl+wn) ; 其中Wl 是Sn-1中使得W+wnM的所有序偶中取最大值的Wl if PXPY then xn=0 /PX是Sn的最末序偶/ else xn=1 /PY是Sn的最末序偶/ 沿Sn-1, S1回溯确定xn-1,x1的值 end DKP,S1 =(0,0),(1,2) S2 =(0,0),(1,2),

43、(2,3),(3,5),(PX,WX)=(3,5),(P3,W3) =(5,4) , Wl =2 (PY,WY)=(1+5,2+4)=(6,6),(PX=3)(PY=6) 所以x3=1,0/1背包问题DKP算法的实现,可用两个一维数组P和W来存放所有的序偶(Pl ,Wl) 序偶集S0,S1,Sn-1互相邻接的存放 各个集合用指针Fi来指示, 0in, Fi指示S中的第一个元素所在的位置,S0 =(0,0) S1 =(0,0),(1,2) S2 =(0,0),(1,2),(2,3),(3,5),P W,在生成Si1的过程中, 同时将Si-1和Si1按支配规则进行归并而生成Si , 因此不需要附加空间存放Si1 在Si-1中序偶是按P和W的递增次序排列的, 因此Si的序偶也按这种次序生成,procedure DKNAP(p,w,n,M,m) F0=1; P1=W1=0; l=h=1; F1=next=2; for i=1 to n-1 do k=l ; u=r ; r是在lrh中,使得Wr+wiM最大 for j=l to u do (pp,ww)=(Pj+pi,Wj+wi) while ( kh and WkPnext-1 ) (Pnext,Wnext)=(pp,ww); next+; w

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论