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

算法分析與設(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ō)明，這個(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回路。,解釋怎么歸約！,1,1,1,1,1,1,1,K|V|,K|V|,K|V|,(3)分析 GH存在Hamilton回路OPT(GTSP)=|V| A(GTSP)K*OPT(GTSP)=K|V| GH不存在Hamilton回路OPT(GTSP)K|V| A(GTSP)OPT(GTSP)K|V| 所以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|V|,K|V|,K|V|,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í)例,圖靈歸約,NP-Hard,存在算法A,1.近似度想多么小，就多么??； 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，t1t2tn (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，4，1 T1,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，則jK+1，所以0, F(I)-tj區(qū)間所有機(jī)器非空閑， 又tK+1tj，所以在0，F(xiàn)(I)-tK+1區(qū)間所有處理器非空閑。 最后一個(gè)完成的任務(wù)Tj, tj tK+1。,(3),= mF(I)-(m-1)tK+1,t1 tK tK+1 tn,無(wú)論哪種排工，鴿籠原理。,(5)分析算法時(shí)間復(fù)雜度TA(m,n)=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()I1+ (2)A()的時(shí)間復(fù)雜度是實(shí)例I長(zhǎng)度的多項(xiàng)式函數(shù)， 則，A()稱為求解問(wèn)題的多項(xiàng)式時(shí)間近似方案。,另外給問(wèn)題增加一個(gè)輸入數(shù)據(jù)，是個(gè)常數(shù)。,Polynomial time approximation scheme,近似性能比1+，時(shí)間復(fù)雜度O(n3)，這個(gè)不行,Polynomial time approximation scheme,設(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=139 W=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=1,1,1,1,0,0,1,0 Pmax=11+21+31+33+45=151 W=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,0 Pmax=11+21+31+43+53=159 W=109=1+11+2