算法分析作業(yè)--第5章

1、2021/8/21算法分析作業(yè) 第5章2021/8/22貪心法 最優(yōu)化問題 約束條件 目標函數 最優(yōu)量度標準(貪心規(guī)則、貪心選擇性質) 試探、證明 貪心法不一定能求得最優(yōu)值，大多數情況得到較優(yōu)值；2021/8/23 2 、 3 、 6、 7 、8 、 9 、 11 、 122021/8/24P121-2 求以下情況背包問題的最優(yōu)解，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)是一個最優(yōu)解。

2、問FO(I)/ FG(I)是多少? 當物品按wi的非降次序輸入時，重復的討論。2021/8/25求背包問題的最優(yōu)解 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節(jié)討論的背包問題修

4、改成 極大化 約束條件 xi=0或1 1in 這種背包問題稱為0/1背包問題。它要求物品或者整件裝入背包或者整件不裝入。求解此問題的一種貪心策略是：按pi/wi的非增次序考慮這些物品，只要正被考慮的物品能裝的進就將其裝入背包。證明這種策略不一定能得到最優(yōu)解。1niip x1 niiw xM2021/8/29P122-3 證明： 按照pi/wi的非增次序考慮物品放入背包，如果從大到小連續(xù)放入且能裝滿背包時，顯然為最優(yōu)解。 否則未必是最優(yōu)解.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），而事實上最優(yōu)解是(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) 假設該問題的一個最優(yōu)解是按照j1,j2,jn的順序存放，并且其期望檢索時間是ERT，我們只需證明ERTERT，即可證明按照fi/li的非增次序存放得到的是最優(yōu)解。 從前向后考察最優(yōu)解序列：j1,j2,jn，若與i1,i2,in相同，命題得證。2021/8/216 否則，不妨設程序jk是第一個與其相鄰的程序jk+1存在關系fjk/ljk0，既有ERT ERT，顯然ERT也是最優(yōu)解

8、。2021/8/217 最優(yōu)解中所有這樣類似于反序對的程序互換位置，每次得到的解不比原來的最優(yōu)解差，所以最終變換后得到的解也是最優(yōu)解，而最終的解恰是程序按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 的次序來考慮程序，這種方法都不能不能產生最優(yōu)解 。iiAliiBliiAliiAliiBl2021/8/219 證明：按照l1 l2 ln不一定產生最優(yōu)解 證： 取l1 , l2 , l3 = 1，3，4 按l1 l2 l3次序得到A=1,4,B=3，最大值是5 若令A=1,3,B=4，最大值是4.這種方式更優(yōu)。 故命題得證。2021/8/220 證明：按照l1 l2 ln不一定產生最優(yōu)解 證： 取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. 這種方式更優(yōu)。 故命題得證。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所生成的解是什么？ 證明即使作業(yè)有不同的處理時間定理5.3亦真。這里，假定作業(yè)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 證明即使作業(yè)有不同的處理時間定理5.3亦真。這里，規(guī)定作業(yè)i的效益pi0，要用的處理時間ti0，限期diti.(P106) 定理5.3:設J是K個作業(yè)的集合, =i1i2ik是J中作業(yè)的一種排序,它使得di1di2dik .J是一個可行解,當且僅當J中的作業(yè)可以按照的次序又不違反任何一個期限的情況下來處理.2021/8/224P123-8 證明思想： 位置a,b的作業(yè)交換順序 作業(yè)ra和rb仍然可以完成任務 作業(yè)ra和rb之間的作業(yè)也能夠完成任務20

12、21/8/225P123-8證明：顯然即使證明：顯然即使ti0（diti），如果），如果J中的作業(yè)可以中的作業(yè)可以按照按照 的次序而又不違反任何一個期限來處理，的次序而又不違反任何一個期限來處理， 即對即對 次序中的任一個作業(yè)次序中的任一個作業(yè)k，應滿足，應滿足dk ，則，則J就是一個可行解。就是一個可行解。下面證明如果下面證明如果J是可行解，是可行解， =i1i2ik使得使得J中的作業(yè)中的作業(yè)可以按照可以按照di1di2din 序列排列而又不違反任何序列排列而又不違反任何一個期限。一個期限。kjjt12021/8/226 J是可行解，則必存在是可行解，則必存在 =r1r2rn，使得對任意的，

13、使得對任意的rk，都有，都有 drk ， 我們設我們設 是按照是按照di1di2din排列的作業(yè)序列。排列的作業(yè)序列。假設假設 ，那么令，那么令a是使是使ra ia的最小下標，設的最小下標，設rb=ia，顯然，顯然ba，在，在 中將中將ra與與rb相交換，因為相交換，因為drbdra，顯然，顯然ra和和rb可以按期完成作業(yè)。可以按期完成作業(yè)。 = r1rarb rn （可行解）（可行解） = i1ia in （d遞增）遞增） t = drb dra t drj1krjjt2021/8/227 我們還要證明我們還要證明ra和和rb之間的作業(yè)也能按期完成。因之間的作業(yè)也能按期完成。因為為drbdr

14、a，而顯然二者之間的所有作業(yè)，而顯然二者之間的所有作業(yè)rt，都有，都有drbdrt，又由于，又由于 是可行解，所以是可行解，所以 ，所以作業(yè)，所以作業(yè)ra和和rb交換后，仍滿足交換后，仍滿足 drt ， 即所有作業(yè)可依新產生的排列即所有作業(yè)可依新產生的排列 =s1s2sn的次的次序處理而不違反任何一個期限序處理而不違反任何一個期限 連續(xù)使用這種方法，連續(xù)使用這種方法， 就可轉換成就可轉換成 且不違反任何且不違反任何一個期限，定理得證。一個期限，定理得證。1krjjt2021/8/228P123-9 對于5.3節(jié)的作業(yè)排序問題證明：當且僅當子集合J中的作業(yè)可以按下述規(guī)則處理時它表示一個可行解；如

15、果J中的作業(yè)I還沒分配處理時間，則將它分配在時間片a-1，a處理，其中a是使得1rdi的最大整數r，且時間片a-1，a是空的。 仿照例5.4的格式，在習題8所提供的數據集上執(zhí)行算法5.5。2021/8/229P123-9 易證如果J中的作業(yè)能按上述規(guī)則處理，顯然J是可行解； 如果J是可行解，根據定理5.3可知，J中的作業(yè)根據時間期限的非降次序排列，得到i1i2ik in ，并且按照這個順序，可以處理J中所有作業(yè)，而對這一序列中的任意作業(yè)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 證明如果一棵樹的所有內部節(jié)點的度都為k，則外部

18、節(jié)點數n滿足n mod (k-1)=1. 證明對于滿足 n mod (k-1)=1的正整數n，存在一棵具有n個外部節(jié)點的k元樹T(在一棵k元樹中，每個節(jié)點的度至多為k)。進而證明T中所有內部節(jié)點的度為k.2021/8/234P123-11 證明如果一棵樹的所有內部節(jié)點的度都為k，則外部節(jié)點數n滿足n mod (k-1)=1. 證明： 設這棵樹內部節(jié)點的個數是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個外部節(jié)點的k元樹T(在一棵k元樹中，每個節(jié)點的度至多為k)。進而證明T中所有內部節(jié)點的度為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后面所描述的貪心規(guī)則對于所有的（q1,q2,qn）生成一棵最優(yōu)的k元歸并樹。 當（q1,q2,q11）=（3,7,8,9,15,16,18,20,23,25,28）時，畫出使用這一規(guī)則所得到的最優(yōu)3元歸并樹。2021/8/239P123-12 證明如果n mod (k-1)=1，則在定理3.6后面所描述的貪心規(guī)則對于所有的（q1,q2,qn）生成一棵最優(yōu)的k元歸并樹。 通過數學歸納法證明： 對于n=1，返回一棵沒有內部結點的樹且這棵樹顯然是最優(yōu)的。 假定該算法對于（q1,q2,qm），其中m=(k-1)s+1 (s0)，都生成一棵最優(yōu)樹， 則只需證明對于(q1,q2,qn)，其中n=(k-1)(s+1)+1，也能生成最優(yōu)樹即可。2