資源描述：
《算法分析解析與設(shè)計(jì)-2016第13講.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、算法分析與設(shè)計(jì)第13講-2016山東大學(xué)計(jì)算機(jī)學(xué)院解決問(wèn)題是最重要的，也是研究的源動(dòng)力。從設(shè)計(jì)算法開始。。再?gòu)母叱隹唇扑惴?。近似性能比r定義了絕對(duì)近似性能比漸進(jìn)近似性能比也具有同樣的含義。當(dāng)OPT(I)>N時(shí)，滿足RA(I)?r，r的下確界。回到另一面去看看：近似性能比能越來(lái)越小嗎？人們要考慮這樣的問(wèn)題。(1)是否能多花時(shí)間，提高解的質(zhì)量。使絕對(duì)近似性能比越來(lái)越?。?2)是否存在一個(gè)關(guān)于解質(zhì)量的界，這個(gè)界難以逾越?就像TSP問(wèn)題的近似算法，能設(shè)計(jì)近似性能比更小的多項(xiàng)式算法嗎？讓計(jì)算機(jī)多運(yùn)行一些時(shí)間，得到更好的解，可以嗎？要在多項(xiàng)式時(shí)間內(nèi)。要說(shuō)
2、明，這個(gè)算法存在，就能拿這個(gè)算法解答Hamilton回路問(wèn)題。說(shuō)明：TSP問(wèn)題不是在metric空間，不一定滿足三角不等式。漸進(jìn)近似性能比由Hamilton回路問(wèn)題到是否存在TSP問(wèn)題近似解的圖靈歸約Hamilton回路問(wèn)題實(shí)例TSP問(wèn)題實(shí)例Hamilton回路問(wèn)題實(shí)例TSP問(wèn)題實(shí)例上面的圖存在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回路問(wèn)題存在多項(xiàng)式時(shí)間算法。說(shuō)明：(1)找錯(cuò)一條邊，就會(huì)出大問(wèn)題，近似度超過(guò)任意常數(shù)，邊太長(zhǎng)了。(2)這不是metric空間的TSP問(wèn)題，是任意空間的TSP問(wèn)題，不存在任意常數(shù)近似度的近似算法。K
18、V
19、K
20、V
21、K
22、V
23、G=G1*G2的做法?(G)=?(G1)*?(G2)，如果G2是完全圖，當(dāng)然對(duì)。G1：G2：2種顏色拿這個(gè)算法去解答一個(gè)知道不行的問(wèn)題。實(shí)例：無(wú)向簡(jiǎn)單圖G詢問(wèn)：是否存在一種著色方案，使其顏色數(shù)不超過(guò)最小著色數(shù)的4/3倍。三著色問(wèn)題實(shí)例圖靈歸
24、約NP-Hard存在算法A1.近似度想多么小，就多么??；2.常數(shù)近似；3.Logn近似；4.n?近似。多項(xiàng)式時(shí)間近似方案TSP,排工§7.3多項(xiàng)式時(shí)間近似方案獨(dú)立任務(wù)排工的進(jìn)一步討論，n個(gè)任務(wù)，m臺(tái)機(jī)器，每個(gè)任務(wù)加工時(shí)間長(zhǎng)度ti。新算法，想辦法多費(fèi)點(diǎn)功夫，前K個(gè)任務(wù)求最優(yōu)排工。也與問(wèn)題有關(guān)。(1)任務(wù)排序：T={T1,T2,…,Tn}，t1?t2?…?tn(2)確定正整數(shù)K,對(duì)前K個(gè)任務(wù)，求最優(yōu)排工，O(mK)時(shí)間，后面n-k個(gè)任務(wù)，按照先大后小順序排工。上述算法叫F。舉個(gè)例子：T={T1,T2,T3,T4,T5,T6}加工時(shí)間：8，6，5，4
25、，4，1T1,T2,T3,T4先求最優(yōu)排工。后兩任務(wù)再排，得15。最優(yōu)為14。這個(gè)不是最優(yōu)的。特別好，看不出來(lái)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ū)間所有機(jī)器非空閑，又tK+1?tj，所以在[0，F(xiàn)(I)-tK+1]區(qū)間所有處理器非空閑。最后一個(gè)完成的任務(wù)Tj,tj?tK+1。(3)=mF(I)-(m-1)tK+1t1?…?tK?tK+1?…?tn無(wú)論哪種排工，鴿籠原理。(5)分析算法時(shí)間復(fù)雜度TA(m,n)
26、=O(mk+nlogn)，K=m，近似性能比小于1+1/2，K=2m；近似性能比小于1+1/3；說(shuō)明：K越大時(shí)間復(fù)雜度越高，解的優(yōu)化程度越高。定義7.2：若問(wèn)題?的近似算法A(?)滿足：對(duì)任意實(shí)例I，任意?>0(1)RA(?)[I]<1+?(2)A(?)的時(shí)間復(fù)雜度是實(shí)例I長(zhǎng)度的多項(xiàng)式函數(shù)，則，A(?)稱為求解問(wèn)題?的多項(xiàng)式時(shí)間近似方案。另外給問(wèn)題增加一個(gè)輸入數(shù)據(jù)?，是個(gè)常數(shù)。Polynomialtimeapproximationscheme近似性能比1+?，時(shí)間復(fù)雜度O(n3)，這個(gè)不行Polynomialtimeapproximations
27、cheme設(shè)元素：a1,a2,…,an(p1,w1)，(p2,w2),…,(pn,wn)加上數(shù)值M，就是背包問(wèn)題實(shí)例。這樣裝法顯然不一定多么好，若任意一種K個(gè)元素的組合都先放入背包嘗試，選擇其中最好的，則最后結(jié)果一定比直接裝入好。全部嘗試完后選擇最好的，作為最后結(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,
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)
