計(jì)算機(jī)算法分析-第五章作業(yè)

計(jì)算機(jī)算法分析—習(xí)題課第五章：3、6、7、8、9、11、12P122-33．（0/1背包問題）如果將5.3節(jié)討論的背包問題修改成極大化 約束條件

xi=0或11≤i≤n這種背包問題稱為0/1背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按pi/wi的非增次序考慮這些物品，只要正被考慮的物品能裝的進(jìn)就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。P122-3證明（反證法）： 設(shè)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)，而事實(shí)上最優(yōu)解是(1,0,1)。問題得證。若所裝入的物品能裝滿背包時(shí)，為最優(yōu)解P122-30/1背包問題可行解集合結(jié)論：當(dāng)按照pi/wi的非增次序考慮物品存放背包時(shí)，如果所裝入的物品能裝滿背包時(shí)，顯然為最優(yōu)解，否則未必是最優(yōu)解.背包問題可行解集合裝滿時(shí)對(duì)應(yīng)的可行解P122-3附：0/1背包問題是一個(gè)NP完全問題，NP完全問題是否存在多項(xiàng)式時(shí)間的求解算法目前仍未可知，這也是計(jì)算機(jī)科學(xué)領(lǐng)域最著名的開放問題“NP=P是否成立”（絕大多數(shù)人相信NP=P不成立），因此，誰(shuí)如果對(duì)0/1背包問題給出一種正確的貪心算法，必然獲得圖靈獎(jiǎng)P122-6．假定要將長(zhǎng)為l1,l2,…,ln的n個(gè)程序存入一盤磁帶，程序Ii被檢索的頻率是fi。如果程序按i1,i2,…,in的次序存放，則期望檢索時(shí)間（ERT）是:①證明按li的非降次序存放程序不一定得到最小的ERT。②證明按fi的非增次序存放程序不一定得到最小的ERT。③證明按fi/li的非增次序來(lái)存放程序時(shí)ERT取最小值。P122-6．問題實(shí)例:(l1,l2,l3)=(5,6,12)，(f1,f2,f3)=(0.2,0.3,0.5)li的非降次序：1=(1,2,3)

fi的非增次序：2

=(3,2,1)

fi/li的非增次序：3

=(2,3,1)ERT(1)=5×0.2+(5+6)×0.3+(5+6+12)×0.5=15.8ERT(2)=12×0.5+(12+6)×0.3+(12+6+5)×0.2=16ERT(3)=6×0.3+(6+12)×0.5+(6+12+5)×0.2=15.4P122-6．③證明按fi/li的非增次序來(lái)存放程序時(shí)ERT取最小值。假設(shè)i1,i2,…,in按照fi/li的非增次序存放，即fi1/li1≥fi2/li2≥…≥fin/lin，則得到ERT=[fi1li1+fi2(li1+li2)+…+fik(li1+li2+…+lik)+…+fin(li1+li2+…+lin)]/(fi1+..+fin)假設(shè)該問題的一個(gè)最優(yōu)解是按照j1,j2,…,jn的順序存放，并且其期望檢索時(shí)間是ERT’，我們只需證明ERT≤ERT’，即可證明按照fi/li的非增次序存放得到的是最優(yōu)解。從前向后考察最優(yōu)解序列：j1,j2,…,jn，若與i1,i2,…,in相同，命題得證。否則，不妨設(shè)程序jk是第一個(gè)與其相鄰的程序jk+1存在關(guān)系fjk/ljk<fjk+1/ljk+1，交換程序jk和程序jk+1，得到的期望檢索時(shí)間記為ERT’’。ERT’-ERT’’=(fjk+1ljk–fjkljk+1)/(fi1+..+fin)>0，既有ERT’’≤ERT’，顯然ERT’’也是最優(yōu)解。最優(yōu)解中所有這樣類似于反序?qū)Φ某绦蚧Q位置，每次得到的解不比原來(lái)的最優(yōu)解差，所以最終變換后得到的解也是最優(yōu)解，而最終的解恰是程序按fi/li的非增次序來(lái)存放得到的順序。命題得證。P123-8①當(dāng)n=7，（p1,…,p7）=(3,5,20,18,1,6,30)和(d1,…,d7)=(1,3,4,3,2,1,2)時(shí)，算法5.4所生成的解是什么？②證明即使作業(yè)有不同的處理時(shí)間定理5.5亦真。這里，假定作業(yè)i的效益pi>0，要用的處理時(shí)間ti>0，限期di≥ti.P123-8解：①根據(jù)pi的非增排序得到（p7,p3,p4,p6,p2,p1,p5）=(30,20,18,6,5,3,1)，對(duì)應(yīng)的期限為(2,4,3,1,3,1,2)，按照算法5.4生成的解為：

J(1)=7(2),J(1)=7(2),J(2)=3(4)；J(1)=7(2),J(2)=4(3),J(3)=3(4)；

J(1)=6(1),J(2)=7(2),J(3)=4(3),J(4)=3(4)；P123-8②證明即使作業(yè)有不同的處理時(shí)間定理5.3亦真。這里，規(guī)定作業(yè)i的效益pi>0，要用的處理時(shí)間ti>0，限期di≥ti.(P106)定理5.3:設(shè)J是K個(gè)作業(yè)的集合,=i1i2…ik是J中作業(yè)的一種排序,它使得di1≤di2≤…≤dik.J是一個(gè)可行解,當(dāng)且僅當(dāng)J中的作業(yè)可以按照的次序又不違反任何一個(gè)期限的情況下來(lái)處理.證明思想：←→位置a,b的作業(yè)交換順序作業(yè)ra和rb仍然可以完成任務(wù)作業(yè)ra和rb之間的作業(yè)也能夠完成任務(wù)P123-8P123-9①對(duì)于5.3節(jié)的作業(yè)排序問題證明：當(dāng)且僅當(dāng)子集合J中的作業(yè)可以按下述規(guī)則處理時(shí)它表示一個(gè)可行解；如果J中的作業(yè)I還沒分配處理時(shí)間，則將它分配在時(shí)間片[a-1，a]處理，其中a是使得1≤r≤di的最大整數(shù)r，且時(shí)間片[a-1，a]是空的。②仿照例5.4的格式，在習(xí)題8①所提供的數(shù)據(jù)集上執(zhí)行算法5.5。P123-9易證如果J中的作業(yè)能按上述規(guī)則處理，顯然J是可行解；如果J是可行解，根據(jù)定理5.3可知，J中的作業(yè)根據(jù)時(shí)間期限的非降次序排列，得到i1i2…ik…in，并且按照這個(gè)順序，可以處理J中所有作業(yè)，而對(duì)這一序列中的任意作業(yè)ik，如果它的時(shí)間期限是dk，且時(shí)間片[dk-1,dk]是空的，則分配之；若時(shí)間片[dk-1，dk]非空，則向前找最大的非空[r-1,r]時(shí)間片，1≤r≤dk。因?yàn)镴是可行解，所以一定可以找到如此時(shí)間片。故命題得證。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)，對(duì)應(yīng)的期限為(2,4,3,1,3,1,2)b=min{n,max{d(i)}}=min{7,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空{(diào)7}F(0)F(1)F(2)F(3)F(4)01133{7,3}-10-2112-2334(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，對(duì)應(yīng)的期限為(2,4,3,1,3,1,2)(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，對(duì)應(yīng)的期限為(2,4,3,1,3,1,2)F(0)F(1)F(2)F(3)F(4)01113{7,3,4}-10-41121334F(0)F(1)F(2)F(3)F(4)00113{7,3,4,6}10-51121334F(0)F(1)F(2)F(3)F(4)00113{7,3,4,6}10-51121314P123-11①證明如果一棵樹的所有內(nèi)部節(jié)點(diǎn)的度都為k，則外部節(jié)點(diǎn)數(shù)n滿足nmod(k-1)=1.②證明對(duì)于滿足nmod(k-1)=1的正整數(shù)n，存在一棵具有n個(gè)外部節(jié)點(diǎn)的k元樹T(在一棵k元樹中，每個(gè)節(jié)點(diǎn)的度至多為k)。進(jìn)而證明T中所有內(nèi)部節(jié)點(diǎn)的度為k.P123-11①證明如果一棵樹的所有內(nèi)部節(jié)點(diǎn)的度都為k，則外部節(jié)點(diǎn)數(shù)n滿足nmod(k-1)=1.證明：①設(shè)這棵樹內(nèi)部節(jié)點(diǎn)的個(gè)數(shù)是i，外部結(jié)點(diǎn)的個(gè)數(shù)是n，邊的條數(shù)是e，則有e=i+n-1ik=eik=i+n-1(k-1)i=n-1nmod(k-1)=1P123-11②證明對(duì)于滿足nmod(k-1)=1的正整數(shù)n，存在一棵具有n個(gè)外部節(jié)點(diǎn)的k元樹T(在一棵k元樹中，每個(gè)節(jié)點(diǎn)的度至多為k)。進(jìn)而證明T中所有內(nèi)部節(jié)點(diǎn)的度為k.

②利用數(shù)學(xué)歸納法(m表示外部結(jié)點(diǎn)數(shù)目)。當(dāng)m=k時(shí)，存在外部結(jié)點(diǎn)數(shù)目為k的k元樹T，并且T中內(nèi)部結(jié)點(diǎn)的度為k；例如：m=33mod(3-1)=1假設(shè)當(dāng)m<n，且滿足mmod(k-1)=1時(shí)，存在一棵具有m個(gè)外部結(jié)點(diǎn)的k元樹T，且所有內(nèi)部結(jié)點(diǎn)的度為k；我們將外部結(jié)點(diǎn)數(shù)為m的符合上述性質(zhì)的樹T中某個(gè)外部結(jié)點(diǎn)用內(nèi)部結(jié)點(diǎn)

a替代，且結(jié)點(diǎn)a生出k個(gè)外部結(jié)點(diǎn).…a易知新生成的樹T’中外部結(jié)點(diǎn)的數(shù)目為n=m-1+k=m+(k-1)，因?yàn)閙mod(k-1)=1，所以n為滿足nmod(k-1)=1，且比m大的最小整數(shù)，而樹T’每個(gè)內(nèi)結(jié)點(diǎn)的度為k，所以n=m+(k-1)時(shí)，存在符合上述性質(zhì)的樹。故命題得證。…aP123-12①證明如果nmod(k-1)=1，則在定理5.4后面所描述的貪心規(guī)則對(duì)于所有的（q1,q2,…,qn）生成一棵最優(yōu)的k元?dú)w并樹。②當(dāng)（q1,q2,…,q11）=（3,7,8,9,15,16,18,20,23,25,28）時(shí)，畫出使用這一規(guī)則所得到的最優(yōu)3元?dú)w并樹。P123-12①證明如果nmod(k-1)=1，則在定理3.6后面所描述的貪心規(guī)則對(duì)于所有的（q1,q2,…,qn）生成一棵最優(yōu)的k元?dú)w并樹。通過數(shù)學(xué)歸納法證明：對(duì)于n=1，返回一棵沒有內(nèi)部結(jié)點(diǎn)的樹且這棵樹顯然是最優(yōu)的。假定該算法對(duì)于（q1,q2,…,qm），其中m=(k-1)s+1(s≥0)，都生成一棵最優(yōu)樹，則只需證明對(duì)于(q1,q2,…,qn)，其中n=(k-1)(s+1)+1，也能生成最優(yōu)樹即可。不失一般性，假定q1≤q2≤…≤qn，且q1,q2,…,qk是算法所找到的k棵樹的WEIGHT信息段的值。于是q1,q2,…,qk可生成子樹T，設(shè)T’是一棵對(duì)于（q1,q2,…,qn）的最優(yōu)k元?dú)w并樹。設(shè)P是距離根最遠(yuǎn)的一個(gè)內(nèi)部結(jié)點(diǎn)。如果P的k個(gè)兒子不是q1,q2,…,qk，則可以用q1,q2,…,qk和P現(xiàn)在的兒子進(jìn)行交換，這樣不增加T’的加權(quán)外部路徑長(zhǎng)度。因此T也是一棵最優(yōu)歸并樹中的子樹。于是在T’中如果用其權(quán)為q1+q2+…+qk的一個(gè)外部結(jié)點(diǎn)來(lái)代換T，則所生成的樹T’’是關(guān)于(T,qk+1,…,qn)的一棵最優(yōu)歸并樹。由歸納假設(shè)，在使用其權(quán)為q1+q2+…+qk的那個(gè)外部結(jié)點(diǎn)代換了T以后，過程TREE轉(zhuǎn)化成去求取一棵關(guān)于(T,qk+1,…,qn)的最優(yōu)歸并樹。因此TREE生成一棵關(guān)于(q1,q2,…,qn)的最優(yōu)歸并樹。（q1,q2,…,q11）=（3,7,8,9,15,16,18,20,23,25,28）78323252891516182078323