算法分析解析與設(shè)計-2016第13講.ppt

《算法分析解析與設(shè)計-2016第13講.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、算法分析與設(shè)計第13講-2016山東大學(xué)計算機學(xué)院解決問題是最重要的，也是研究的源動力。從設(shè)計算法開始。。再從高出看近似算法。近似性能比r定義了絕對近似性能比漸進近似性能比也具有同樣的含義。當(dāng)OPT(I)>N時，滿足RA(I)?r，r的下確界?；氐搅硪幻嫒タ纯矗航菩阅鼙饶茉絹碓叫幔咳藗円紤]這樣的問題。(1)是否能多花時間，提高解的質(zhì)量。使絕對近似性能比越來越小？(2)是否存在一個關(guān)于解質(zhì)量的界，這個界難以逾越?就像TSP問題的近似算法，能設(shè)計近似性能比更小的多項式算法嗎？讓計算機多運行一些時間，得到更好的解，可以嗎？要在多項式時間內(nèi)。要說

2、明，這個算法存在，就能拿這個算法解答Hamilton回路問題。說明：TSP問題不是在metric空間，不一定滿足三角不等式。漸進近似性能比由Hamilton回路問題到是否存在TSP問題近似解的圖靈歸約Hamilton回路問題實例TSP問題實例Hamilton回路問題實例TSP問題實例上面的圖存在Hamilton回路，下面的不存在Hamilton回路。解釋怎么歸約！1111111K

3、V

4、K

5、V

6、K

7、V

8、(3)分析GH存在Hamilton回路?OPT(GTSP)=

9、V

10、A(GTSP)?K*OPT(GTSP)=K

11、V

12、GH不存在Hamilton回路?

13、OPT(GTSP)>K

14、V

15、A(GTSP)?OPT(GTSP)>K

16、V

17、所以Hamilton回路問題存在多項式時間算法。說明：(1)找錯一條邊，就會出大問題，近似度超過任意常數(shù)，邊太長了。(2)這不是metric空間的TSP問題，是任意空間的TSP問題，不存在任意常數(shù)近似度的近似算法。K

18、V

19、K

20、V

21、K

22、V

23、G=G1*G2的做法?(G)=?(G1)*?(G2)，如果G2是完全圖，當(dāng)然對。G1：G2：2種顏色拿這個算法去解答一個知道不行的問題。實例：無向簡單圖G詢問：是否存在一種著色方案，使其顏色數(shù)不超過最小著色數(shù)的4/3倍。三著色問題實例圖靈歸

24、約NP-Hard存在算法A1.近似度想多么小，就多么??；2.常數(shù)近似；3.Logn近似；4.n?近似。多項式時間近似方案TSP,排工§7.3多項式時間近似方案獨立任務(wù)排工的進一步討論，n個任務(wù)，m臺機器，每個任務(wù)加工時間長度ti。新算法，想辦法多費點功夫，前K個任務(wù)求最優(yōu)排工。也與問題有關(guān)。(1)任務(wù)排序：T={T1,T2,…,Tn}，t1?t2?…?tn(2)確定正整數(shù)K,對前K個任務(wù)，求最優(yōu)排工，O(mK)時間，后面n-k個任務(wù)，按照先大后小順序排工。上述算法叫F。舉個例子：T={T1,T2,T3,T4,T5,T6}加工時間：8，6，5，4

25、，4，1T1,T2,T3,T4先求最優(yōu)排工。后兩任務(wù)再排，得15。最優(yōu)為14。這個不是最優(yōu)的。特別好，看不出來tj(2)在[0，F(xiàn)(I)-tK+1]區(qū)間所有處理器非空閑。t1?t2?…?tK?tK+1?…?tn由(1)決定，最后完成任務(wù)為Tj，則j?K+1，所以[0,F(I)-tj]區(qū)間所有機器非空閑，又tK+1?tj，所以在[0，F(xiàn)(I)-tK+1]區(qū)間所有處理器非空閑。最后一個完成的任務(wù)Tj,tj?tK+1。(3)=mF(I)-(m-1)tK+1t1?…?tK?tK+1?…?tn無論哪種排工，鴿籠原理。(5)分析算法時間復(fù)雜度TA(m,n)

26、=O(mk+nlogn)，K=m，近似性能比小于1+1/2，K=2m；近似性能比小于1+1/3；說明：K越大時間復(fù)雜度越高，解的優(yōu)化程度越高。定義7.2：若問題?的近似算法A(?)滿足：對任意實例I，任意?>0(1)RA(?)[I]<1+?(2)A(?)的時間復(fù)雜度是實例I長度的多項式函數(shù)，則，A(?)稱為求解問題?的多項式時間近似方案。另外給問題增加一個輸入數(shù)據(jù)?，是個常數(shù)。Polynomialtimeapproximationscheme近似性能比1+?，時間復(fù)雜度O(n3)，這個不行Polynomialtimeapproximations

27、cheme設(shè)元素：a1,a2,…,an(p1,w1)，(p2,w2),…,(pn,wn)加上數(shù)值M，就是背包問題實例。這樣裝法顯然不一定多么好，若任意一種K個元素的組合都先放入背包嘗試，選擇其中最好的，則最后結(jié)果一定比直接裝入好。全部嘗試完后選擇最好的，作為最后結(jié)果。(1)K=0時，直接從頭開始裝入：x1,x2,x3,x4,x5,x6,x7,x8=11111000，前5個裝入背包Pmax=11+21+31+33+43=139W=1+11+21+23+33=89(2)K=1，時，先裝入1個，再裝入其他，得到1,2,3,4,7最好x1,x2,x3,

28、x4,x5,x6,x7,x8=1,1,1,1,0,0,1,0Pmax=11+21+31+33+45=151W=1+11+21+23+45=101(3)