计算机算法分析—第五章作业

1、计算机算法分析计算机算法分析习题课习题课第五章：第五章：3 、6、7、8 、 9 、11 、 12P122-3n3（0/1背包问题）如果将背包问题）如果将5.3节讨论的背包节讨论的背包问题修改成问题修改成n 极大化极大化 n 约束条件约束条件 n xi=0或或1 1inn这种背包问题称为这种背包问题称为0/1背包问题。它要求物品背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按题的一种贪心策略是：按pi/wi的非增次序考虑的非增次序考虑这些物品，只要正被考虑的物品能装的进就将这些物品，只要正被考虑的物品能装的进就将其装入背

2、包。证明这种策略其装入背包。证明这种策略不一定不一定能得到最优能得到最优解。解。1niip x1 niiw xMP122-3q证明（反证法）：设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) 。问题得证。q若所装入的物品能装满背包时，为最优解P122-30/1背包问题可行解集合q结论：当按照pi /wi的非增次序考虑物品存放背包时，如果所装入的物品能装满背包

3、时，显然为最优解，否则未必是最优解.背包问题可行解集合装满时对应的可行解P122-3q附：0/1背包问题是一个NP完全问题，NP完全问题是否存在多项式时间的求解算法目前仍未可知，这也是计算机科学领域最著名的开放问题“NP = P是否成立”（绝大多数人相信NP = P不成立），因此，谁如果对0/1背包问题给出一种正确的贪心算法，必然获得图灵奖P122- 6n假定要将长为假定要将长为l1,l2,ln的的n个程序存入一盘磁个程序存入一盘磁带，程序带，程序Ii被检索的频率是被检索的频率是fi。如果程序按。如果程序按i1,i2,in的次序存放，则期望检索时间（的次序存放，则期望检索时间（ERT）是是:1

4、()/jkjiiijkflfn 证明按证明按li的非降次序存放程序不一定得到最的非降次序存放程序不一定得到最小的小的ERT。n 证明按证明按fi的非增次序存放程序不一定得到最的非增次序存放程序不一定得到最小的小的ERT。n 证明按证明按fi/li的非增次序来存放程序时的非增次序来存放程序时ERT取取最小值。最小值。P122- 6n问题实例:(l1, l2, l3) = (5, 6, 12)，(f1, f2, f3) = (0.2, 0.3, 0.5)nli的非降次序： 1 = (1, 2, 3) nfi的非增次序： 2 = (3, 2, 1) nfi /li的非增次序的非增次序： 3 = (2

5、, 3, 1)nERT( 1) = 50.2 + (5+6)0.3 + (5+6+12) 0.5 = 15.8nERT( 2)=120.5+(12+6) 0.3+(12+6+5) 0.2=16nERT( 3)=60.3 + (6+12)0.5 + (6+12+5) 0.2=15.4P122 - 6 证明按证明按fi/li的非增次序来存放程序时的非增次序来存放程序时ERT取最小值。取最小值。n 假设假设i1,i2,in按照按照fi/li的非增次序存放，即的非增次序存放，即fi1/li1fi2/li2fin/lin，则得到，则得到 ERT=fi1li1+fi2(li1+li2)+fik(li1+l

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

7、0，既有，既有ERT ERT，显然，显然ERT也是最优解。也是最优解。n最优解中所有这样类似于反序对的程序互换位置，最优解中所有这样类似于反序对的程序互换位置，每次得到的解不比原来的最优解差，所以最终变每次得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序换后得到的解也是最优解，而最终的解恰是程序按按fi/li的非增次序来存放得到的顺序。的非增次序来存放得到的顺序。n命题得证。命题得证。P123-8n 当当n=7，（，（p1 , p7）=(3,5,20,18,1,6,30) 和和(d1,d7)=(1,3,4,3,2,1,2)时，算法时，算法5.4所生所生成的解是什

8、么？成的解是什么？n 证明即使作业有不同的处理时间定理证明即使作业有不同的处理时间定理5.5亦亦真。这里，假定作业真。这里，假定作业i的效益的效益pi0，要用的处，要用的处理时间理时间ti0，限期，限期diti.P123-8n解：解：根据根据pi的非增排序得到（的非增排序得到（p7, p3, p4, p6, p2, p1, p5）=(30,20,18,6,5,3,1)，对应的期限，对应的期限为为(2,4,3,1,3,1,2)，按照算法，按照算法5.4生成的解为：生成的解为：nJ(1)=7(2), nJ(1)=7(2), J(2)=3(4)；nJ(1)=7(2), J(2)=4(3),J(3)=

9、3(4)；1.J(1)=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)；P123-8n 证明即使作业有不同的处理时间定理证明即使作业有不同的处理时间定理5.3亦真。这亦真。这里，规定作业里，规定作业i的效益的效益pi0，要用的处理时间，要用的处理时间ti0，限，限期期diti.(P106)n定理定理5.3:设设J是是K个作业的集合个作业的集合, =i1i2ik是是J中作业中作业的一种排序的一种排序,它使得它使得di1di2dik .J是一个可行解是一个可行解,当当且仅当且仅当J中的作业可以按照中的作业可以按照 的次序又不违反任何一个的次序又不违反任何一个期限的情况下来处

10、理期限的情况下来处理.n证明思想：证明思想：qq 位置位置a,b的作业交换顺序的作业交换顺序n作业作业ra和和rb仍然可以完成任务仍然可以完成任务n作业作业ra和和rb之间的作业也能够完成任务之间的作业也能够完成任务P123-8P123-9n 对于对于5.3节的作业排序问题证明：当且仅当节的作业排序问题证明：当且仅当子集合子集合J中的作业可以按下述规则处理时它表中的作业可以按下述规则处理时它表示一个可行解；如果示一个可行解；如果J中的作业中的作业I还没分配处理还没分配处理时间，则将它分配在时间片时间，则将它分配在时间片a-1，a处理，其处理，其中中a是使得是使得1rdi的最大整数的最大整数r，

11、且时间片，且时间片a-1，a是空的。是空的。n 仿照例仿照例5.4的格式，在习题的格式，在习题8所提供的数所提供的数据集上执行算法据集上执行算法5.5。P123-9n易证如果易证如果J中的作业能按上述规则处理，显然中的作业能按上述规则处理，显然J是可行是可行解；解；n如果如果J是可行解，根据定理是可行解，根据定理5.3可知，可知，J中的作业根据中的作业根据时间期限的非降次序排列，得到时间期限的非降次序排列，得到i1i2ik in ，并且按，并且按照这个顺序，可以处理照这个顺序，可以处理J中所有作业，而对这一序列中所有作业，而对这一序列中的任意作业中的任意作业ik，如果它的时间期限是，如果它的时

12、间期限是dk，且时间片，且时间片dk-1,dk是空的，则分配之；若时间片是空的，则分配之；若时间片dk-1，dk非非空，则向前找最大的非空空，则向前找最大的非空r-1,r时间片，时间片，1rdk。因因为为J是可行解，所以一定可以找到如此时间片。故命是可行解，所以一定可以找到如此时间片。故命题得证。题得证。 nn=7(p1, p7)=(3,5,20,18,1,6,30)(d1,d7)=(1,3,4,3,2,1,2)n(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)

13、=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)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)(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

14、)F(4)011137,3,4-10-41121334F(0)F(1)F(2)F(3)F(4)001137,3,4,610-51121334F(0)F(1)F(2) F(3)F(4)001137,3,4,610-51121314P123-11n 证明如果一棵树的所有内部节点的度都为证明如果一棵树的所有内部节点的度都为k，则外部节点数则外部节点数n满足满足n mod (k-1)=1.n 证明对于满足证明对于满足 n mod (k-1)=1的正整数的正整数n，存在一棵具有存在一棵具有n个外部节点的个外部节点的k元树元树T(在一棵在一棵k元树中，每个节点的度至多为元树中，每个节点的度至多为k)。进而

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

16、点的k元树元树T(在一棵在一棵k元树元树中，每个节点的度至多为中，每个节点的度至多为k)。进而证明。进而证明T中所有内中所有内部节点的度为部节点的度为k.n 利用数学归纳法利用数学归纳法(m表示外部结点数目表示外部结点数目)。n当当m =k时，存在外部结点数目为时，存在外部结点数目为k的的k元树元树T，并且并且T中内部结点的度为中内部结点的度为k；例如：例如：m=33mod(3-1)=1n假设当假设当 m n，且满足，且满足m mod (k-1)=1时，存时，存在一棵具有在一棵具有m个外部结点的个外部结点的k元树元树T，且所有内，且所有内部结点的度为部结点的度为k；n我们将外部结点数为我们将外

17、部结点数为m的符合上述性质的树的符合上述性质的树T中某个外部结点用内部结点中某个外部结点用内部结点 a替代，且结点替代，且结点a生出生出k个外部结点个外部结点.an易知新生成的树易知新生成的树T中外部结点的数目为中外部结点的数目为n= m -1+k= m +(k-1)，因为，因为 m mod (k-1)=1，所以，所以n为满足为满足n mod (k-1)=1，且比，且比m大的最小整数，大的最小整数，而树而树T每个内结点的度为每个内结点的度为k，所以，所以n= m +(k-1)时，存在符合上述性质的树。故命题得证。时，存在符合上述性质的树。故命题得证。aP123-12n 证明如果证明如果n mo

18、d (k-1)=1，则在定理，则在定理5.4后后面所描述的贪心规则对于所有的（面所描述的贪心规则对于所有的（q1,q2,qn）生成一棵最优的生成一棵最优的k元归并树。元归并树。n 当（当（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使）时，画出使用这一规则所得到的最优用这一规则所得到的最优3元归并树。元归并树。P123-12 证明如果证明如果n mod (k-1)=1，则在定理，则在定理3.6后面所描述的贪心规则对于所有的（后面所描述的贪心规则对于所有的（q1,q2,qn）生）生成一棵最优的成一棵最优的k元归并树。元归并树。n通过数学归纳法证明：通

19、过数学归纳法证明：n对于对于n=1，返回一棵没有内部结点的树且这棵树，返回一棵没有内部结点的树且这棵树显然是最优的。显然是最优的。n假定该算法对于（假定该算法对于（q1,q2,qm），其中），其中m=(k-1)s+1 (s0)，都生成一棵最优树，都生成一棵最优树，n则只需证明对于则只需证明对于(q1,q2,qn)，其中，其中n=(k-1)(s+1)+1，也能生成最优树即可。，也能生成最优树即可。n不失一般性，假定不失一般性，假定q1q2qn，且，且q1,q2,qk是算法所找到的是算法所找到的k棵树的棵树的WEIGHT信息段的值。信息段的值。于是于是q1,q2,qk可生成子树可生成子树T，设，设T是一棵对于是一棵对于（q1,q2,qn）的最优）的最优k元归并树。设元归并树。设P是距离是距离根最远的一个内部结点。如果根最远的一个内部结点。如果P的的k个儿子