算法分析與設計-2016第13講.ppt

算法分析與設計,第13講-2016 山東大學計算機學院,解決問題是最重要的，也是研究的源動力。 從設計算法開始。,。,再從高出看近似算法。,近似性能比r,定義了絕對近似性能比,漸進近似性能比也具有同樣的含義。 當OPT(I)N時，滿足RA(I)r，r的下確界。 回到另一面去看看：近似性能比能越來越小嗎？ 人們要考慮這樣的問題。 (1)是否能多花時間，提高解的質(zhì)量。使絕對近似性能比越來越?。?(2)是否存在一個關于解質(zhì)量的界，這個界難以逾越?,就像TSP問題的近似算法，能設計近似性能比更小的多項式算法嗎？,讓計算機多運行一些時間，得到更好的解，可以嗎？要在多項式時間內(nèi)。,要說明，這個算法存在，就能拿這個算法解答Hamilton回路問題。,說明：TSP問題不是在metric空間，不一定滿足三角不等式。,漸進近似性能比,由Hamilton回路問題到是否存在TSP問題近似解的圖靈歸約,Hamilton回路問題實例,TSP問題實例,Hamilton回路問題實例,TSP問題實例,上面的圖存在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回路問題存在多項式時間算法。,說明： (1)找錯一條邊，就會出大問題， 近似度超過任意常數(shù)，邊太長了。 (2)這不是metric空間的TSP問題，是任意空間的TSP問題， 不存在任意常數(shù)近似度的近似算法。,K|V|,K|V|,K|V|,G=G1*G2的做法 (G)= (G1)*(G2)，如果G2是完全圖，當然對。,G1：,G2：,2種顏色,拿這個算法去解答一個知道不行的問題。,實例：無向簡單圖G 詢問：是否存在一種著色方案，使其顏色數(shù)不超過最小著色數(shù)的4/3倍。,三著色問題實例,圖靈歸約,NP-Hard,存在算法A,1.近似度想多么小，就多么?。?2.常數(shù)近似； 3.Logn近似； 4.n近似。,多項式時間近似方案,TSP, 排工,7.3多項式時間近似方案 獨立任務排工的進一步討論，n個任務，m臺機器， 每個任務加工時間長度ti。 新算法，想辦法多費點功夫，前K個任務求最優(yōu)排工。 也與問題有關。 (1)任務排序：T=T1, T2, , Tn，t1t2tn (2)確定正整數(shù)K,對前K個任務，求最優(yōu)排工，O(mK)時間， 后面n-k個任務，按照先大后小順序排工。,上述算法叫F。舉個例子： T=T1,T2,T3,T4,T5,T6 加工時間：8，6，5，4，4，1 T1,T2,T3,T4先求最優(yōu)排工。后兩任務再排，得15。最優(yōu)為14。,這個不是最優(yōu)的。,特別好，看不出來,tj,(2)在0，F(xiàn)(I)-tK+1區(qū)間所有處理器非空閑。 t1 t2 tK tK+1 tn 由(1)決定， 最后完成任務為Tj，則jK+1，所以0, F(I)-tj區(qū)間所有機器非空閑， 又tK+1tj，所以在0，F(xiàn)(I)-tK+1區(qū)間所有處理器非空閑。 最后一個完成的任務Tj, tj tK+1。,(3),= mF(I)-(m-1)tK+1,t1 tK tK+1 tn,無論哪種排工，鴿籠原理。,(5)分析算法時間復雜度TA(m,n)=O(mk+nlogn)， K=m，近似性能比小于1+1/2，K=2m；近似性能比小于1+1/3； 說明：K越大時間復雜度越高，解的優(yōu)化程度越高。 定義7.2：若問題的近似算法A()滿足：對任意實例I，任意0 (1)RA()I1+ (2)A()的時間復雜度是實例I長度的多項式函數(shù)， 則，A()稱為求解問題的多項式時間近似方案。,另外給問題增加一個輸入數(shù)據(jù)，是個常數(shù)。,Polynomial time approximation scheme,近似性能比1+，時間復雜度O(n3)，這個不行,Polynomial time approximation scheme,設元素：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=139 W=1+11+21+23+33=89 (2)K=1，時，先裝入1個，再裝入其他，得到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個，再裝入其他，得到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