算法分析與設(shè)計(jì)2006第e講

《算法分析與設(shè)計(jì)2006第e講》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、上次內(nèi)容：(1)圖著色不能多項(xiàng)式時(shí)間近似到小于，TSP問(wèn)題不能多項(xiàng)式時(shí)間近似到任意常數(shù)。(2)，時(shí)間復(fù)雜度O(mK+nlogn)，K越大求解優(yōu)化程度越高，1+e，T=O()。M是常數(shù)時(shí)可以認(rèn)為是多項(xiàng)式時(shí)間近似方案。什么是多項(xiàng)式時(shí)間近似方案：定義7.2：若問(wèn)題p的近似算法A(e)若滿足對(duì)任意實(shí)例I任意e>0(1)RA(e)[I]<1+e；(2)A(e)的時(shí)間復(fù)雜度是I輸入長(zhǎng)度的多項(xiàng)式函數(shù)。則A(e)稱為求解問(wèn)題p的多項(xiàng)式時(shí)間近似方案。解釋：(1)1+e很容易說(shuō)明，但后面的多項(xiàng)式需要解釋,時(shí)間復(fù)雜度一定與e有關(guān)。

2、近似性能比1+e，時(shí)間復(fù)雜度為：O()，O(n)，O(n2)，PTAS。特殊情況：O()等等，各種情況。一定是e越小，時(shí)間復(fù)雜度越大。最后一種情況又稱為完全多項(xiàng)式時(shí)間近似方案。FPTAS完全多項(xiàng)式時(shí)間近似方案：近似度1+e；時(shí)間復(fù)雜度：P(n,)，P(·,·)是多項(xiàng)式函數(shù)。(2)為什么叫多項(xiàng)式近似方案，而不叫多項(xiàng)式近似算法。因?yàn)閑沒(méi)有確定大小，只有程序運(yùn)行時(shí)才能確定。再考慮背包問(wèn)題：設(shè)計(jì)真正的多項(xiàng)式時(shí)間近似方案。，xi?{0,1},I=1,…,n設(shè)元素：a1,a2,…,an

3、p1,p2,…,pn

4、w1,w2,

5、…,wn(1)簡(jiǎn)單算法描述先挑k個(gè)元素放入背包，然后調(diào)用前面7.1節(jié)算法選擇其他元素裝包。兩種規(guī)則，價(jià)值重量比大者優(yōu)先；價(jià)值大者優(yōu)先，二者擇優(yōu)選一為最終解。這樣裝法顯然不一定多么好，若對(duì)任意一種k個(gè)元素的組合都先放入背包嘗試，則最后結(jié)果一定比直接裝入好。全部嘗試完后選擇最好的，作為最后結(jié)果。算法描述：Proceduree-approx(P,W,M,n,K)1Pmax=0;2forallcombinationsIofsize￡Kandweight￡Mdo//不超過(guò)K元素的組合3PI=;4Pmax=max{Pma

6、x,PI+L(I,P,W,M,n)}//L(I,P,W,M,n)是子程序。用于計(jì)算剩余容量裝包。5endfor6end下面這個(gè)算法是先試裝k個(gè)后再繼續(xù)裝ProcedureL(I,P,W,M,n)//I是已經(jīng)裝入的元素集合(1)S=0;T=M-;IS=?(2)Fori=1tondo(3)Ifi?IandWi￡Tthen(4)S=S+Pi;T=T-Wi;IS=IS+{i}(5)Endif(6)EndforReturn(max{S,max{Pi

7、i?I,1￡i￡n}})//S是由第一種策略裝進(jìn)包的，后面是第二種策略

8、裝進(jìn)包的，比較取優(yōu)。End例子：n=8，M=110。P1P2P3P4P5P6P7P81121313343535565111212333434555上面已經(jīng)按照價(jià)值重量比排好序了。(1)K=0時(shí)，直接從頭開始裝入：x1,x2,x3,x4,x5,x6,x7,x8=11111000，前5個(gè)裝入背包Pmax=11+21+31+33+43=139W=1+11+21+23+33=89(2)K=1，時(shí)，先裝入1個(gè)，再裝入其他，得到1,2,3,4,7最好x1,x2,x3,x4,x5,x6,x7,x8=11110010Pmax

9、=11+21+31+33+45=151W=1+11+21+23+45=101(3)k=2，先裝入2個(gè)，再裝入其他，得到1,2,3,5,6最好x1,x2,x3,x4,x5,x6,x7,x8=1,1,1,0,1,1,0,0Pmax=11+21+31+43+53=159W=109=1+11+21+33+43這是最優(yōu)解。定理7.15設(shè)背包問(wèn)題最優(yōu)解為P*，Pmax是前述先裝算法e-approx得到的解，則對(duì)任意背包問(wèn)題實(shí)例均成立。證明：//為什么會(huì)很好呢？因?yàn)橛锌赡軐⒆顑?yōu)解前K個(gè)價(jià)值最大的先裝入。(1)給定實(shí)例，設(shè)R

10、是該實(shí)例最優(yōu)解的裝入背包元素下標(biāo)集合，若

11、R

12、￡K，則能夠求到最優(yōu)解，以下假設(shè)

13、R

14、>K。(2)將R中的元素的價(jià)值重量寫成有序?qū)?，按照以下?guī)則重新排序：(),(),…,()

15、

16、(),…,()。(*),…,是R中元素前k個(gè)最大價(jià)值，3…33，1￡j￡

17、R

18、-k。(*)從i=k+1開始按照價(jià)值重量比排序3…3。(3)考慮先將R中前K個(gè)元素裝入背包的情況，有一種這樣情況。PI=設(shè)S是調(diào)用L(I,P,W,M,n)增加的收益。會(huì)不會(huì)將R中元素全部裝入包？則：P*

19、背包的R中元素的價(jià)值。這一步特別關(guān)鍵，要找一個(gè)比P*還好的界限，要說(shuō)明白。為什么，因?yàn)檠b入以后就超重了。還是很難說(shuō)明的。為什么放進(jìn)背包別的東西了，因?yàn)槟切┰貎r(jià)值重量比更大。如果將同樣重量，不屬于最優(yōu)解的元素替換出來(lái)，一定使價(jià)值變小。Pmax3PI+L，這僅是一種情況得到裝包收益為PI+S，算法是所有情況都試遍得到的解，結(jié)果不會(huì)比這次差。，m>k,S3，Pmax3(K+1)所以前面的不等式成立。沒(méi)有