首页计算机计算机基础计算机算法设计与分析 11 第五章作业.pptx

11 第五章作业.pptx

页数:18页文件大小:113.6 KB来源: 计算机算法设计与分析ppt课件

本课件讲解第五章贪心方法的课后习题,包括按不同输入次序求解背包问题最优解、用反例否定贪心策略命题、求解带期限作业排序问题所生成的作业集合,以及证明作业处理时间不同时定理5.3仍成立与可行解的判定规则。

第五章习题封面,标示本次习题选取贪心方法一章的2、3、8、9题
习题P121-2题目页,给出七件物品的效益与质量并要求求背包问题的最优解
解答页之一,按单位效益非增序输入得到贪心解并给出各分量的取值
查看本课件的文字版(共 18 页,供检索与复制)

第1页:第五章习题封面

第五章2, 3, 8, 9

第2页:习题P121-2题目

P121-2

  • 求以下情况背包问题的最优解,n=7,m=15,(p1,…, p7)=(10,5,15,7,6,18,3)和(w1,…,w7)=(2,3,5,7,1,4,1)。
  • 将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解,FO(I)是一个最优解。问FO(I)/ FG(I)是多少?
  • 当物品按wi的非降次序输入时,重复②的讨论。

第3页:P121-2:按效益质量比输入

P121-2

  • ①按照pi/wi的非增序可得(p5/w5,p1/w1,p6/w6,p3/w3,p7/w7,p2/w2,p4/w4)=(6,5,9/2,3,3,5/3,1)所以最优解为:(1,2/3,1,0,1,1,1),并且FO(I)=166/3
  • ②按照pi的非增次序输入时,得到(p6,p3,p1,p4,p5,p2,p7)=(18,15,10,7,6,5,3),对应的(w6,w3,w1,w4,w5,w2,w7)=(4,5,2,7,1,3,1),则FG(I)的解为(0,1,0,1,1,0,4/7),并且FG(I)=47,所以,FO(I)/FG(I)=166/141.

第4页:P121-2:按质量非增序输入

P121-2

  • ③按照wi的非增次序输入时,得到(w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7),(p5,p7,p1,p2,p6,p3,p4)=(6,3,10,5,18,15,7),FW(I)的解为(1,1,4/5,0,1,1,1),FW(I)=54,所以FO(I)/FW(I)=83/81.

第5页:习题P122-3题目

P122-3

第6页:P122-3的反例

否定一个命题,直接举反例即可设n=3,M=6,(p1,p2,p3)=(3,4,8),(w1,w2,w3)=(1,2,5)按照pi/wi的非增序得到(p1/w1,p2/w2,p3/w3)=(3,2,1.6),则其解为(1,1,0),而事实上最优解是(1,0,1)。

第7页:习题P123-8题目

P123-8

  • ①当n=7,(p1,…, p7)=(3,5,20,18,1,6,30)和(d1,…,d7)=(1,3,4,3,2,1,2)时,算法5.4所生成的解是什么?(P123)
  • ②证明即使作业有不同的处理时间定理5.3亦真。这里,假定作业i的效益pi>0,要用的处理时间ti>0,限期di≥ti.

第8页:P123-8的解

P123-8

  • 解:①按照pi的非增排序对作业重新排序,得到
  • (p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1),对应的期限为( 2, 4, 3, 1,3,1,2),
  • 按照算法5.4生成的解为:1.J(1)=7,2.J(1)=7, J(2)=3;3.J(1)=7, J(2)=4, J(3)=3;4.J(1)=6, J(2)=7, J(3)=4, J(4)=3;

第9页:定理5.3在作业处理时间不同时仍成立

P123-8

  • ②证明即使作业有不同的处理时间定理5.3亦真。这里,假定作业i的效益pi>0,要用的处理时间ti>0,限期di≥ti.
  • 定理5.3:设J是k个作业的集合,σ=i1i2…ik是J中作业的一种排序,它使得di1≤di2≤…≤dik. J是一个可行解,当且仅当J中的作业可以按照σ的次序又不违反任何一个期限的情况下来处理.

第10页:可行性排列的证明

P123-8

  • 证明:显然即使作业的处理时间各不相同(ti>0,di≥ti),如果J中的作业可以按照σ的次序排列而又不超出任何一个期限的限定,即对σ次序中的任一个作业k,满足dk≥,则J就是一个可行解。
  • 下面证明如果J是可行解,σ=i1i2…ik使得J中的作业可以按照di1≤di2≤…≤din排列而又不超出任何一个作业的期限。

第11页:按期限排序的交换论证

  • 若J是可行解,则必存在一种排列σ’=r1r2…rn,使得对任意的rk,都有.
  • 设σ是按照di1≤di2≤…≤din排列的作业序列。若σ’=σ,则σ中每个作业都不会超出其期限。命题得证.
  • 假设σ’≠σ,那么令a是使ra≠ia的最小下标,设rb=ia,显然b>a.在σ’中将ra与rb相交换,因为drb≤dra,显然交换后ra和rb可以在各自的期限前完成作业。

第12页:交换后中间作业的可行性

  • 下面证明ra和rb之间的作业也能按期完成。因为drb≤dra,而显然二者之间的所有作业rt,都有drb≤drt,又由于σ’是可行解,所以,ra和rb交换后ra和rb之间的作业也能按期完成。
  • 作业ra和rb交换后,所有作业可依新产生的排列σ’’=s1s2…sn的次序处理而不违反任何一个期限,连续使用这种方法,σ’就可转换成σ且不违反任何一个期限,定理得证。

第13页:习题P123-9题目

P123-9

  • ①对于5.3节的作业排序问题证明:当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解;如果J中的作业i还没分配处理时间,则将它分配在时间片[α-1,α]处理,其中α是使得1≤r≤di的最大整数r,且时间片[α-1,α]是空的。
  • ②仿照例5.4的格式,在习题8①所提供的数据集上执行算法5.5。

第14页:可行解规则的充分性

  • 如果J中的作业能按上述规则处理,则每一个作业都可在它的期限之前获得一个空的时间片,所以J是可行解。
  • 如果J是可行解,存在一种排列σ’=i1i2…ik,作业都可在其期限前完成。
  • J中作业按效益值非递增的顺序排列为s1s2…sk,采用数学归纳法
  • 考虑作业s1,根据命题中的规则,它放在期限允许的最大位置ds1,若其在σ’中也处于该位置,则考虑下一个作业s2;否则,s1在σ’中的位置必然小于ds1,可将σ’中处于ds1位置的作业与s1交换,不影响其可行性。
  • 假设s1s2…sa都已经按照命题中规则安排好,并且与σ’中相应的作业处于相同的位置。现在考虑sa+1,按照规则它应该放在dsa+1或其前面的一个最大的空位置上,设其位置为α,若其在σ’中的位置不是α,设其为β(β<α),在σ’中将iα和iβ互换,且交换后仍可行,iα一定不是s1s2…sa中的任何一个。这样一直进行下去一直到sk,则σ’中的作业按照命题中

第15页:可行解规则的必要性

  • n=7(p1,…,p7)=(3,5,20,18,1,6,30)(d1,…,d7)=(1,3, 4, 3, 2,1, 2)
  • (p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1),对应的期限为(2, 4, 3,1,3,1,2)
  • b = min{ n,max{d(i)} }= min{7,4 }=4

第16页:P123-9的实例数据

F(4)F(3)F(2)F(1)F(0)43210-10-11-12-13-14F(4)F(3)F(2)F(1)F(0)43110-10-2112-13-14空{7}F(4)F(3)F(2)F(1)F(0)33110{7,3}-10-2112-2334(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)对应的期限为(2,4,3,1,3,1,2)J考虑作业无73

第17页:时间片分配过程之一

(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)对应的期限为(2,4,3,1,3,1,2)F(4)F(3)F(2)F(1)F(0)31110{7,3,4}-10-41121334F(4)F(3)F(2)F(1)F(0)31100{7,3,4,6}10-51121334J考虑作业64

第18页:时间片分配过程之二

(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)对应的期限为(2,4,3,1,3,1,2)F(4)F(3)F(2)F(1)F(0)31100F(4)F(3)F(2)F(1)F(0)31100{7,3,4,6}J考虑作业2(舍弃)10-511213341(舍弃){7,3,4,6}同上F(4)F(3)F(2)F(1)F(0)31100{7,3,4,6}5(舍弃)同上作业的处理顺序为(6,7,4, 3),效益值为74.

顶部目录