計算機算法分析—第五章作業(yè)

1、計算機算法分析計算機算法分析習題課習題課第五章：第五章：3 、6、7、8 、 9 、11 、 12P122-3n3（0/1背包問題）如果將背包問題）如果將5.3節(jié)討論的背包節(jié)討論的背包問題修改成問題修改成n 極大化極大化 n 約束條件約束條件 n xi=0或或1 1inn這種背包問題稱為這種背包問題稱為0/1背包問題。它要求物品背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按題的一種貪心策略是：按pi/wi的非增次序考慮的非增次序考慮這些物品，只要正被考慮的物品能裝的進就將這些物品，只要正被考慮的物品能裝的進就將其裝入背

2、包。證明這種策略其裝入背包。證明這種策略不一定不一定能得到最優(yōu)能得到最優(yōu)解。解。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)，而事實上最優(yōu)解是(1, 0, 1) 。問題得證。q若所裝入的物品能裝滿背包時，為最優(yōu)解P122-30/1背包問題可行解集合q結(jié)論：當按照pi /wi的非增次序考慮物品存放背包時，如果所裝入的物品能裝滿背包

3、時，顯然為最優(yōu)解，否則未必是最優(yōu)解.背包問題可行解集合裝滿時對應的可行解P122-3q附：0/1背包問題是一個NP完全問題，NP完全問題是否存在多項式時間的求解算法目前仍未可知，這也是計算機科學領域最著名的開放問題“NP = P是否成立”（絕大多數(shù)人相信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假設該問題的一個最優(yōu)解是按照假設該問題的一個最優(yōu)解是按照j1,j2,jn的順序的順序存放，并且其期望檢索存放，并且其期望檢索時間時間是是ERT，我們只需證，我們只需證明明ERTERT，即可證明按照，即可證明按照fi/li的非增次序存放的非增次序存放得到的是最優(yōu)解。得到的是最優(yōu)解。n從前向后考察最優(yōu)解序列：從前向后考察最優(yōu)解序列：j1,j2,jn，若與，若與i1,i2,in相同，命題得證。相同，命題得證。n否則，不妨設程序否則，不妨設程序jk是第一個與其相鄰的程序是第一個與其相鄰的程序jk+1存在關系存在關系fjk/ljk

7、0，既有，既有ERT ERT，顯然，顯然ERT也是最優(yōu)解。也是最優(yōu)解。n最優(yōu)解中所有這樣類似于反序?qū)Φ某绦蚧Q位置，最優(yōu)解中所有這樣類似于反序?qū)Φ某绦蚧Q位置，每次得到的解不比原來的最優(yōu)解差，所以最終變每次得到的解不比原來的最優(yōu)解差，所以最終變換后得到的解也是最優(yōu)解，而最終的解恰是程序換后得到的解也是最優(yōu)解，而最終的解恰是程序按按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 證明即使作業(yè)有不同的處理時間定理證明即使作業(yè)有不同的處理時間定理5.5亦亦真。這里，假定作業(yè)真。這里，假定作業(yè)i的效益的效益pi0，要用的處，要用的處理時間理時間ti0，限期，限期diti.P123-8n解：解：根據(jù)根據(jù)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 證明即使作業(yè)有不同的處理時間定理證明即使作業(yè)有不同的處理時間定理5.3亦真。這亦真。這里，規(guī)定作業(yè)里，規(guī)定作業(yè)i的效益的效益pi0，要用的處理時間，要用的處理時間ti0，限，限期期diti.(P106)n定理定理5.3:設設J是是K個作業(yè)的集合個作業(yè)的集合, =i1i2ik是是J中作業(yè)中作業(yè)的一種排序的一種排序,它使得它使得di1di2dik .J是一個可行解是一個可行解,當當且僅當且僅當J中的作業(yè)可以按照中的作業(yè)可以按照 的次序又不違反任何一個的次序又不違反任何一個期限的情況下來處

10、理期限的情況下來處理.n證明思想：證明思想：qq 位置位置a,b的作業(yè)交換順序的作業(yè)交換順序n作業(yè)作業(yè)ra和和rb仍然可以完成任務仍然可以完成任務n作業(yè)作業(yè)ra和和rb之間的作業(yè)也能夠完成任務之間的作業(yè)也能夠完成任務P123-8P123-9n 對于對于5.3節(jié)的作業(yè)排序問題證明：當且僅當節(jié)的作業(yè)排序問題證明：當且僅當子集合子集合J中的作業(yè)可以按下述規(guī)則處理時它表中的作業(yè)可以按下述規(guī)則處理時它表示一個可行解；如果示一個可行解；如果J中的作業(yè)中的作業(yè)I還沒分配處理還沒分配處理時間，則將它分配在時間片時間，則將它分配在時間片a-1，a處理，其處理，其中中a是使得是使得1rdi的最大整數(shù)的最大整數(shù)r，

11、且時間片，且時間片a-1，a是空的。是空的。n 仿照例仿照例5.4的格式，在習題的格式，在習題8所提供的數(shù)所提供的數(shù)據(jù)集上執(zhí)行算法據(jù)集上執(zhí)行算法5.5。P123-9n易證如果易證如果J中的作業(yè)能按上述規(guī)則處理，顯然中的作業(yè)能按上述規(guī)則處理，顯然J是可行是可行解；解；n如果如果J是可行解，根據(jù)定理是可行解，根據(jù)定理5.3可知，可知，J中的作業(yè)根據(jù)中的作業(yè)根據(jù)時間期限的非降次序排列，得到時間期限的非降次序排列，得到i1i2ik in ，并且按，并且按照這個順序，可以處理照這個順序，可以處理J中所有作業(yè)，而對這一序列中所有作業(yè)，而對這一序列中的任意作業(yè)中的任意作業(yè)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 證明如果一棵樹的所有內(nèi)部節(jié)點的度都為證明如果一棵樹的所有內(nèi)部節(jié)點的度都為k，則外部節(jié)點數(shù)則外部節(jié)點數(shù)n滿足滿足n mod (k-1)=1.n 證明對于滿足證明對于滿足 n mod (k-1)=1的正整數(shù)的正整數(shù)n，存在一棵具有存在一棵具有n個外部節(jié)點的個外部節(jié)點的k元樹元樹T(在一棵在一棵k元樹中，每個節(jié)點的度至多為元樹中，每個節(jié)點的度至多為k)。進而

15、證明。進而證明T中所有內(nèi)部節(jié)點的度為中所有內(nèi)部節(jié)點的度為k.P123-11 證明如果一棵樹的所有內(nèi)部節(jié)點的度證明如果一棵樹的所有內(nèi)部節(jié)點的度都為都為k，則外部節(jié)點數(shù)，則外部節(jié)點數(shù)n滿足滿足n mod (k-1)=1.n證明：證明： 設這棵樹內(nèi)部節(jié)點的個數(shù)是設這棵樹內(nèi)部節(jié)點的個數(shù)是i，外部，外部結(jié)點的個數(shù)是結(jié)點的個數(shù)是n，邊的條數(shù)是，邊的條數(shù)是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的正整數(shù)的正整數(shù)n，存在一棵具有存在一棵具有n個外部節(jié)點的個外部節(jié)

16、點的k元樹元樹T(在一棵在一棵k元樹元樹中，每個節(jié)點的度至多為中，每個節(jié)點的度至多為k)。進而證明。進而證明T中所有內(nèi)中所有內(nèi)部節(jié)點的度為部節(jié)點的度為k.n 利用數(shù)學歸納法利用數(shù)學歸納法(m表示外部結(jié)點數(shù)目表示外部結(jié)點數(shù)目)。n當當m =k時，存在外部結(jié)點數(shù)目為時，存在外部結(jié)點數(shù)目為k的的k元樹元樹T，并且并且T中內(nèi)部結(jié)點的度為中內(nèi)部結(jié)點的度為k；例如：例如：m=33mod(3-1)=1n假設當假設當 m n，且滿足，且滿足m mod (k-1)=1時，存時，存在一棵具有在一棵具有m個外部結(jié)點的個外部結(jié)點的k元樹元樹T，且所有內(nèi)，且所有內(nèi)部結(jié)點的度為部結(jié)點的度為k；n我們將外部結(jié)點數(shù)為我們將外

17、部結(jié)點數(shù)為m的符合上述性質(zhì)的樹的符合上述性質(zhì)的樹T中某個外部結(jié)點用內(nèi)部結(jié)點中某個外部結(jié)點用內(nèi)部結(jié)點 a替代，且結(jié)點替代，且結(jié)點a生出生出k個外部結(jié)點個外部結(jié)點.an易知新生成的樹易知新生成的樹T中外部結(jié)點的數(shù)目為中外部結(jié)點的數(shù)目為n= m -1+k= m +(k-1)，因為，因為 m mod (k-1)=1，所以，所以n為滿足為滿足n mod (k-1)=1，且比，且比m大的最小整數(shù)，大的最小整數(shù)，而樹而樹T每個內(nèi)結(jié)點的度為每個內(nèi)結(jié)點的度為k，所以，所以n= m +(k-1)時，存在符合上述性質(zhì)的樹。故命題得證。時，存在符合上述性質(zhì)的樹。故命題得證。aP123-12n 證明如果證明如果n mo

18、d (k-1)=1，則在定理，則在定理5.4后后面所描述的貪心規(guī)則對于所有的（面所描述的貪心規(guī)則對于所有的（q1,q2,qn）生成一棵最優(yōu)的生成一棵最優(yōu)的k元歸并樹。元歸并樹。n 當（當（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）時，畫出使）時，畫出使用這一規(guī)則所得到的最優(yōu)用這一規(guī)則所得到的最優(yōu)3元歸并樹。元歸并樹。P123-12 證明如果證明如果n mod (k-1)=1，則在定理，則在定理3.6后面所描述的貪心規(guī)則對于所有的（后面所描述的貪心規(guī)則對于所有的（q1,q2,qn）生）生成一棵最優(yōu)的成一棵最優(yōu)的k元歸并樹。元歸并樹。n通過數(shù)學歸納法證明：通

19、過數(shù)學歸納法證明：n對于對于n=1，返回一棵沒有內(nèi)部結(jié)點的樹且這棵樹，返回一棵沒有內(nèi)部結(jié)點的樹且這棵樹顯然是最優(yōu)的。顯然是最優(yōu)的。n假定該算法對于（假定該算法對于（q1,q2,qm），其中），其中m=(k-1)s+1 (s0)，都生成一棵最優(yōu)樹，都生成一棵最優(yōu)樹，n則只需證明對于則只需證明對于(q1,q2,qn)，其中，其中n=(k-1)(s+1)+1，也能生成最優(yōu)樹即可。，也能生成最優(yōu)樹即可。n不失一般性，假定不失一般性，假定q1q2qn，且，且q1,q2,qk是算法所找到的是算法所找到的k棵樹的棵樹的WEIGHT信息段的值。信息段的值。于是于是q1,q2,qk可生成子樹可生成子樹T，設，設T是一棵對于是一棵對于（q1,q2,qn）的最優(yōu)）的最優(yōu)k元歸并樹。設元歸并樹。設P是距離是距離根最遠的一個內(nèi)部結(jié)點。如果根最遠的一個內(nèi)部結(jié)點。如果P的的k個兒子