算法分析作业-第5章.ppt

《算法分析作业-第5章.ppt》由会员分享，可在线阅读，更多相关《算法分析作业-第5章.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法分析作业第5章贪心法最优化问题约束条件目标函数最优量度标准(贪心规则、贪心选择性质)试探、证明贪心法不一定能求得最优值，大多数情况得到较优值；2、3、6、7、8、9、11、12P121-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的非降次序输入时，重复的讨论。求背包问题的最优解n=7，m=15根据贪心（x

2、5,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 1111按照Pi的非增次序：n=7，m=15根据贪心（x6,x3,x1,x4,x5,x2,x7）=（1,1,1,4/7,0,0,0）即FG(I)的解为(0,1,0,1,1,0,4/7)，FG(I)=47FO(I)/FG(I)=166/141i1234567p1051576183w2357141x117/41物品按wi

3、的非降次序：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)=54FO(I)/FG(I)=166/162=83/81i1234567p1051576183w2357141x114/5111P122-3（0/1背包问题）如果将5.3节讨论的背包问题修改成极大化约束条件xi=0或1 1in这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装的进就将其装入背包。证明这种策略不

4、一定能得到最优解。P122-3证明：按照pi/wi的非增次序考虑物品放入背包，如果从大到小连续放入且能装满背包时，显然为最优解。否则未必是最优解.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)。问题得证。P122-6假定要将长为l1,l2,ln的n个程序存入一盘磁带，程序i被检索的频率是fi。如果程序按i1,i2,in的次序存放，则期望检索时间（ERT）是:证明按li的非降次序存放程序

5、不一定得到最小的ERT。证明按fi的非增次序存放程序不一定得到最小的ERT。证明按fi/li的非增次序来存放程序时ERT取最小值。P122-6证明按li的非降次序存放程序不一定得到最小的ERT。I:(l1,l2)=(10,12)(f1,f2)=(0.4,0.6)ERT(I)=10*0.4+(10+12)*0.6=17.2ERT(I)=12*0.6+(10+12)*0.4=16P122-6证明按fi的非增次序存放程序不一定得到最小的ERT。I:(l1,l2)=(2,1)(f1,f2)=(0.6,0.4)ERT(I)=2*0.6+(2+1)*0.4=2.4ERT(I)=1*0.4+(1+2)*0.

6、6=2.2P122-6证明按fi/li的非增次序来存放程序时ERT取最小值。假设i1,i2,in按照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相同，命题得证。否则，不妨设程序jk是第一个与其相邻的程序j

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

8、分配给B。证明无论按l1 l2 ln 或是按l1 l2 ln 的次序来考虑程序，这种方法都不能不能产生最优解。证明：按照l1 l2 ln不一定产生最优解证：取l1,l2,l3=1，3，4按l1 l2 l3次序得到A=1,4,B=3，最大值是5若令A=1,3,B=4，最大值是4.这种方式更优。故命题得证。证明：按照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，最大值是21.若令A=10,9,B=8,6,5，最大值是19.这种方式更优。故命题得证。P123-8当n=7，（p1,p7）=(

9、3,5,20,18,1,6,30)和(d1,d7)=(1,3,4,3,2,1,2)时，算法5.4所生成的解是什么？证明即使作业有不同的处理时间定理5.3亦真。这里，假定作业i的效益pi0，要用的处理时间ti0，限期diti.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生成的解为：kJD(J(r)，r=1.k17227,32,437,4,32,3,446,7,4,31,2,3,4P123-8证明即使作业有不同的处理时间定理5.3亦真。这里，规定作业i的效益pi0

10、，要用的处理时间ti0，限期diti.(P106)定理5.3:设J是K个作业的集合,=i1i2ik是J中作业的一种排序,它使得di1di2dik.J是一个可行解,当且仅当J中的作业可以按照的次序又不违反任何一个期限的情况下来处理.P123-8证明思想：位置a,b的作业交换顺序作业ra和rb仍然可以完成任务作业ra和rb之间的作业也能够完成任务P123-8证明：显然即使证明：显然即使ti0（diti），如果），如果J中的作业可以中的作业可以按照按照 的次序而又不违反任何一个期限来处理，的次序而又不违反任何一个期限来处理，即对即对 次序中的任一个作业次序中的任一个作业k，应满足，应满足dk ，则，

11、则J就是一个可行解。就是一个可行解。下面证明如果下面证明如果J是可行解，是可行解，=i1i2ik使得使得J中的作业中的作业可以按照可以按照di1di2din 序列排列而又不违反任何序列排列而又不违反任何一个期限。一个期限。J是可行解，则必存在是可行解，则必存在=r1r2rn，使得对任意的，使得对任意的rk，都有，都有 drk ，我们设我们设 是按照是按照di1di2din排列的作业序列。排列的作业序列。假设假设，那么令，那么令a是使是使ra ia的最小下标，设的最小下标，设rb=ia，显然，显然ba，在，在 中将中将ra与与rb相交换，因为相交换，因为drbdra，显然，显然ra和和rb可以按

12、期完成作业。可以按期完成作业。=r1rarb rn （可行解）（可行解）=i1ia in （d递增）递增）t=drb dra t drj我们还要证明我们还要证明ra和和rb之间的作业也能按期完成。因之间的作业也能按期完成。因为为drbdra，而显然二者之间的所有作业，而显然二者之间的所有作业rt，都有，都有drbdrt，又由于，又由于 是可行解，所以是可行解，所以，所以作业，所以作业ra和和rb交换后，仍满足交换后，仍满足 drt ，即所有作业可依新产生的排列即所有作业可依新产生的排列=s1s2sn的次序的次序处理而不违反任何一个期限处理而不违反任何一个期限连续使用这种方法，连续使用这种方法，

13、就可转换成就可转换成 且不违反任何且不违反任何一个期限，定理得证。一个期限，定理得证。P123-9 对于5.3节的作业排序问题证明：当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解；如果J中的作业I还没分配处理时间，则将它分配在时间片a-1，a处理，其中a是使得1rdi的最大整数r，且时间片a-1，a是空的。仿照例5.4的格式，在习题8所提供的数据集上执行算法5.5。P123-9易证如果J中的作业能按上述规则处理，显然J是可行解；如果J是可行解，根据定理5.3可知，J中的作业根据时间期限的非降次序排列，得到i1i2ikin，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任

14、意作业ik，如果它的时间期限是dk，且时间片dk-1,dk是空的，则分配之；若时间片dk-1，dk非空，则向前找最大的非空r-1,r时间片，1rdk。因为J是可行解，所以一定可以找到如此时间片。故命题得证。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=minn,maxd(i)=min7,4=4F(0)F(1)F(2)F(3)F(4)01234-10-11-12-13-14F(0)F(1)F(2)F(3)F(4

15、)01134-10-2112-13-14空空7F(0)F(1)F(2)F(3)F(4)011337,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)F(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)P123-11证明如果一棵

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

17、度至多为k)。进而证明T中所有内部节点的度为k.利用数学归纳法(m表示外部结点数目)。当m=k时，存在外部结点数目为k的k元树T，并且T中内部结点的度为k；例如：例如：m=33mod(3-1)=1假设当mn，且满足mmod(k-1)=1时，存在一棵具有m个外部结点的k元树T，且所有内部结点的度为k；我们将外部结点数为m的符合上述性质的树T中某个外部结点用内部结点a替代，且结点a生出k个外部结点.a易知新生成的树T中外部结点的数目为n=m-1+k=m+(k-1)，因为mmod(k-1)=1，所以n为满足nmod(k-1)=1，且比m大的最小整数，而树T每个内结点的度为k，所以n=m+(k-1)时

18、，存在符合上述性质的树。故命题得证。aP123-12证明如果nmod(k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,qn）生成一棵最优的k元归并树。当（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。P123-12证明如果nmod(k-1)=1，则在定理3.6后面所描述的贪心规则对于所有的（q1,q2,qn）生成一棵最优的k元归并树。通过数学归纳法证明：对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于（q1,q2,qm），其中m=(k-1)s+1(s0)，都生成一棵最

19、优树，则只需证明对于(q1,q2,qn)，其中n=(k-1)(s+1)+1，也能生成最优树即可。不失一般性，假定q1q2qn，且q1,q2,qk是算法所找到的k棵树的WEIGHT信息段的值。于是q1,q2,qk可生成子树T，设T是一棵对于（q1,q2,qn）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是q1,q2,qk，则可以用q1,q2,qk和P现在的儿子进行交换，这样不增加T的加权外部路径长度。因此T也是一棵最优归并树中的子树。于是在T中如果用其权为q1+q2+qk的一个外部结点来代换T，则所生成的树T是关于(T,qk+1,qn)的一棵最优归并树。由归纳假设，在使用

20、其权为q1+q2+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于(T,qk+1,qn)的最优归并树。因此TREE生成一棵关于(q1,q2,qn)的最优归并树。（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）783232528915161820783232528915161820187832325289151618201840（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）7832325289151618201840567832325289151618201840567678323252891516182018405676172（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）