算法分析作业--第5章_第1页
算法分析作业--第5章_第2页
算法分析作业--第5章_第3页
算法分析作业--第5章_第4页
算法分析作业--第5章_第5页
已阅读5页,还剩40页未读 继续免费阅读

下载本文档

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

文档简介

1、2021/8/21算法分析作业 第5章2021/8/22贪心法 最优化问题 约束条件 目标函数 最优量度标准(贪心规则、贪心选择性质) 试探、证明 贪心法不一定能求得最优值,大多数情况得到较优值;2021/8/23 2 、 3 、 6、 7 、8 、 9 、 11 、 122021/8/24P121-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)是一个最优解。

2、问FO(I)/ FG(I)是多少? 当物品按wi的非降次序输入时,重复的讨论。2021/8/25求背包问题的最优解 n=7,m=15 根据贪心(x5,x1,x6,x3,x7,x2,x4)=(1,1,1,1,1,2/3,0)即(x1,x2,x3,x4,x5,x6,x7)=(1,2/3,1,0,1,1,1 ) FO(I)=166/3。 i1234567p1051576183w2357141p/w 55/3 3169/2 3x12/3 11112021/8/26 按照Pi的非增次序:n=7,m=15 根据贪心(x6,x3,x1,x4,x5,x2,x7)=(1,1,1,4/7,0,0,0)即FG(I)

3、的解为(0,1,0,1,1,0,4/7),FG(I)=47 FO(I)/ FG(I)=166/141 i1234567p1051576183w2357141x117/412021/8/27 物品按wi的非降次序:n=7,m=15 根据贪心(x5,x7,x1,x2,x6,x3,x4)=(1,1,1,1,1,4/5,0)即FG(I)的解为(1,1,4/5,0,1,1,1),FG(I)=54 FO(I)/ FG(I)=166/162 = 83/81 i1234567p1051576183w2357141x114/51112021/8/28P122-3 (0/1背包问题)如果将5.3节讨论的背包问题修

4、改成 极大化 约束条件 xi=0或1 1in 这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是:按pi/wi的非增次序考虑这些物品,只要正被考虑的物品能装的进就将其装入背包。证明这种策略不一定能得到最优解。1niip x1 niiw xM2021/8/29P122-3 证明: 按照pi/wi的非增次序考虑物品放入背包,如果从大到小连续放入且能装满背包时,显然为最优解。 否则未必是最优解.2021/8/210P122-3 可举例如下:设n=3,M=6,(p1,p2,p3)=(3,4,8),(w1,w2,w3)=(1,2,5) 按照pi/wi 的

5、非增序得到(p1/w1,p2/w2,p3/w3)=(3,2,1.6),则其解为(1,1,0),而事实上最优解是(1,0,1) 。问题得证。2021/8/211P122- 6 假定要将长为l1,l2,ln的n个程序存入一盘磁带,程序i被检索的频率是fi。如果程序按i1,i2,in的次序存放,则期望检索时间(ERT)是:1()/jijikijkflf2021/8/212 证明按li的非降次序存放程序不一定得到最小的ERT。 证明按fi的非增次序存放程序不一定得到最小的ERT。 证明按fi/li的非增次序来存放程序时ERT取最小值。2021/8/213P122- 6 证明按li的非降次序存放程序不一

6、定得到最小的ERT。 I: (l1,l2)=(10,12) (f1,f2)=(0.4,0.6) ERT(I)=10*0.4+(10+12)*0.6=17.2 ERT(I)=12*0.6+(10+12)*0.4=162021/8/214P122 - 6 证明按fi的非增次序存放程序不一定得到最小的ERT。 I: (l1,l2)=(2,1) (f1,f2)=(0.6,0.4) ERT(I)=2*0.6+(2+1)*0.4=2.4 ERT(I)=1*0.4+(1+2)*0.6=2.22021/8/215P122 - 6 证明按fi/li的非增次序来存放程序时ERT取最小值。 假设i1,i2,in按照

7、fi/li的非增次序存放,即fi1/li1fi2/li2fin/lin,则得到 ERT=fi1li1+fi2(li1+li2)+fik(li1+li2+lik)+fin(li1+li2+lin)/(fi1+.+fin) 假设该问题的一个最优解是按照j1,j2,jn的顺序存放,并且其期望检索时间是ERT,我们只需证明ERTERT,即可证明按照fi/li的非增次序存放得到的是最优解。 从前向后考察最优解序列:j1,j2,jn,若与i1,i2,in相同,命题得证。2021/8/216 否则,不妨设程序jk是第一个与其相邻的程序jk+1存在关系fjk/ljk0,既有ERT ERT,显然ERT也是最优解

8、。2021/8/217 最优解中所有这样类似于反序对的程序互换位置,每次得到的解不比原来的最优解差,所以最终变换后得到的解也是最优解,而最终的解恰是程序按fi/li的非增次序来存放得到的顺序。 命题得证。2021/8/218P122-7 假定要将长为l1,l2,ln的n个程序分别写入两盘磁带T1和T2上,并且希望按照使最大检索时间取最小值的方式存放。即,如果存放在T1和T2上的程序集合分别是A和B,就希望所选择的A和B使得max , 取最小值。一种得到A和B的贪心方法如下:开始将A和B都初始化为空,然后一次考虑一个程序,如果 = min , , 则将当前正在考虑的那个程序分配给A,否则分配给B

9、。证明无论按l1 l2 ln 或是按l1 l2 ln 的次序来考虑程序,这种方法都不能不能产生最优解 。iiAliiBliiAliiAliiBl2021/8/219 证明:按照l1 l2 ln不一定产生最优解 证: 取l1 , l2 , l3 = 1,3,4 按l1 l2 l3次序得到A=1,4,B=3,最大值是5 若令A=1,3,B=4,最大值是4.这种方式更优。 故命题得证。2021/8/220 证明:按照l1 l2 ln不一定产生最优解 证: 取l1 , l2 , l3 , l4 , l5 = 10,9,8,6,5 按l1 l2 l3 l4 l5次序得到 A=10,6,5,B=9,8,最

10、大值是21. 若令A=10,9,B=8,6,5,最大值是19. 这种方式更优。 故命题得证。2021/8/221P123-8 当n=7,(p1 , p7)=(3,5,20,18,1,6,30) 和(d1,d7)=(1,3,4,3,2,1,2)时,算法5.4所生成的解是什么? 证明即使作业有不同的处理时间定理5.3亦真。这里,假定作业i的效益pi0,要用的处理时间ti0,限期diti.2021/8/222P123-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

11、生成的解为:kJD(J(r),r=1.k17227,32,437,4,32,3,446,7,4,31,2,3,42021/8/223P123-8 证明即使作业有不同的处理时间定理5.3亦真。这里,规定作业i的效益pi0,要用的处理时间ti0,限期diti.(P106) 定理5.3:设J是K个作业的集合, =i1i2ik是J中作业的一种排序,它使得di1di2dik .J是一个可行解,当且仅当J中的作业可以按照的次序又不违反任何一个期限的情况下来处理.2021/8/224P123-8 证明思想: 位置a,b的作业交换顺序 作业ra和rb仍然可以完成任务 作业ra和rb之间的作业也能够完成任务20

12、21/8/225P123-8证明:显然即使证明:显然即使ti0(diti),如果),如果J中的作业可以中的作业可以按照按照 的次序而又不违反任何一个期限来处理,的次序而又不违反任何一个期限来处理, 即对即对 次序中的任一个作业次序中的任一个作业k,应满足,应满足dk ,则,则J就是一个可行解。就是一个可行解。下面证明如果下面证明如果J是可行解,是可行解, =i1i2ik使得使得J中的作业中的作业可以按照可以按照di1di2din 序列排列而又不违反任何序列排列而又不违反任何一个期限。一个期限。kjjt12021/8/226 J是可行解,则必存在是可行解,则必存在 =r1r2rn,使得对任意的,

13、使得对任意的rk,都有,都有 drk , 我们设我们设 是按照是按照di1di2din排列的作业序列。排列的作业序列。假设假设 ,那么令,那么令a是使是使ra ia的最小下标,设的最小下标,设rb=ia,显然,显然ba,在,在 中将中将ra与与rb相交换,因为相交换,因为drbdra,显然,显然ra和和rb可以按期完成作业。可以按期完成作业。 = r1rarb rn (可行解)(可行解) = i1ia in (d递增)递增) t = drb dra t drj1krjjt2021/8/227 我们还要证明我们还要证明ra和和rb之间的作业也能按期完成。因之间的作业也能按期完成。因为为drbdr

14、a,而显然二者之间的所有作业,而显然二者之间的所有作业rt,都有,都有drbdrt,又由于,又由于 是可行解,所以是可行解,所以 ,所以作业,所以作业ra和和rb交换后,仍满足交换后,仍满足 drt , 即所有作业可依新产生的排列即所有作业可依新产生的排列 =s1s2sn的次的次序处理而不违反任何一个期限序处理而不违反任何一个期限 连续使用这种方法,连续使用这种方法, 就可转换成就可转换成 且不违反任何且不违反任何一个期限,定理得证。一个期限,定理得证。1krjjt2021/8/228P123-9 对于5.3节的作业排序问题证明:当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解;如

15、果J中的作业I还没分配处理时间,则将它分配在时间片a-1,a处理,其中a是使得1rdi的最大整数r,且时间片a-1,a是空的。 仿照例5.4的格式,在习题8所提供的数据集上执行算法5.5。2021/8/229P123-9 易证如果J中的作业能按上述规则处理,显然J是可行解; 如果J是可行解,根据定理5.3可知,J中的作业根据时间期限的非降次序排列,得到i1i2ik in ,并且按照这个顺序,可以处理J中所有作业,而对这一序列中的任意作业ik,如果它的时间期限是dk,且时间片dk-1,dk是空的,则分配之;若时间片dk-1,dk非空,则向前找最大的非空r-1,r时间片,1rdk。因为J是可行解,

16、所以一定可以找到如此时间片。故命题得证。 2021/8/230 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,maxd(i) =min7,4 =42021/8/231F(0)F(1)F(2)F(3)F(4)01234-10-11-12-13-14F(0)F(1)F(2)F(3)F(4)01134-10-2112-13-14空空7F(0)F(1)F(2)F(3)F(4)011337,

17、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)2021/8/232F(0)F(1)F(2)F(3)F(4)011137,3,4-10-41121334F(0)F(1)F(2)F(3)F(4)001137,3,4,610-51121334(p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1),对应的期限为对应的期限为(2,4,3,1,3,1,2)2021/8/233P123-11 证明如果一棵树的所有内部节点的度都为k,则外部

18、节点数n满足n mod (k-1)=1. 证明对于满足 n mod (k-1)=1的正整数n,存在一棵具有n个外部节点的k元树T(在一棵k元树中,每个节点的度至多为k)。进而证明T中所有内部节点的度为k.2021/8/234P123-11 证明如果一棵树的所有内部节点的度都为k,则外部节点数n满足n mod (k-1)=1. 证明: 设这棵树内部节点的个数是i,外部结点的个数是n,边的条数是e,则有 e=i+n-1 e=i * k i*k=i+n-1 (k-1)i=n-1 n mod (k-1)=1 2021/8/235P123-11 证明对于满足 n mod (k-1)=1的正整数n,存在一

19、棵具有n个外部节点的k元树T(在一棵k元树中,每个节点的度至多为k)。进而证明T中所有内部节点的度为k. 利用数学归纳法(m表示外部结点数目)。 当m =k时,存在外部结点数目为k的k元树T,并且T中内部结点的度为k;例如:例如:m=33mod(3-1)=12021/8/236 假设当 m n,且满足m mod (k-1)=1时,存在一棵具有m个外部结点的k元树T,且所有内部结点的度为k; 我们将外部结点数为m的符合上述性质的树T中某个外部结点用内部结点 a替代,且结点a生出k个外部结点.a2021/8/237 易知新生成的树T中外部结点的数目为n= m -1+k= m +(k-1),因为 m

20、 mod (k-1)=1,所以n为满足n mod (k-1)=1,且比m大的最小整数,而树T每个内结点的度为k,所以n= m +(k-1)时,存在符合上述性质的树。故命题得证。a2021/8/238P123-12 证明如果n mod (k-1)=1,则在定理5.4后面所描述的贪心规则对于所有的(q1,q2,qn)生成一棵最优的k元归并树。 当(q1,q2,q11)=(3,7,8,9,15,16,18,20,23,25,28)时,画出使用这一规则所得到的最优3元归并树。2021/8/239P123-12 证明如果n mod (k-1)=1,则在定理3.6后面所描述的贪心规则对于所有的(q1,q2,qn)生成一棵最优的k元归并树。 通过数学归纳法证明: 对于n=1,返回一棵没有内部结点的树且这棵树显然是最优的。 假定该算法对于(q1,q2,qm),其中m=(k-1)s+1 (s0),都生成一棵最优树, 则只需证明对于(q1,q2,qn),其中n=(k-1)(s+1)+1,也能生成最优树即可。2

温馨提示

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

评论

0/150

提交评论