2016129()()2016-01-29綿 1/大1大234()4()2016-01-292016-01-29綿 2/大1大2344() 2016-01-29綿 3/()(()2016-01-29綿 4/100

近似算法與隨機算法的分析方法與應用實 2016-01-29綿 5/利弊利弊權()2016-01-29綿 6/()2016-01-29()2016-01-29綿 7/主要內 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 8/大1大2344() 2016-01-29綿 9/()近似算法和最優化算入）IAσAΠ的近似算法。A(I)=c(σ)AIc(σ)ΠIA(I)=OPT(I)A 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 10/近似rA=OPT(I)rA=OPT(I)ΠIrA(I)≤rArAr- 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 11/可近似?>0(1+?)- 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 12/(()2016-01-29綿 13/最小頂點覆蓋ΠG=?V最小頂點覆蓋V′Ve∈E，e∈V′最小頂點覆蓋集：MVC V′←whileE?=doeu,v)∈ V′←V′∪{u,E←E?{e|euvreturnV 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 14/最小頂點覆蓋集：MVC算法分kMVC(I)=|V′|=2kkOPT(I)≥k

MVC(I)≤2kOPT(I) kIGkMVC(I)=2k，OPT(I)=k，MVC(I) 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 15/多機調度問AmA1,A2,···,Am}∑

t(a)i=1,2,···a∈Ai 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 16/多機調度問題：GMPS算法分Mj時間和最多，akMj的最后一個作業Mjak后一定是時間最少的 GMPS(I)=1[T?t(a)k]+t(a)m=1T+(1?1 ≤OPT(I)+(1?1)OPT(I)m=(2

)OPT(I)m 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 17/多機調度問題：DGMPS算法算法Mj時間和最多，akMjMjak后一定是時間 t(a)，若Mj不止一個作DGMPS(I)=1[T?t(ak)]+m=1T+(1?1 ≤OPT(I)+1(1?1)OPT(I)m=(3 1)OPT(I) 22 2016-01-29綿 18/(()2016-01-29綿 19/滿足三角不等式的貨郎問題 算法分1G2在T上求經過每條邊恰好兩次 3在上 MST(I)≤=2·≤2OPT(I) 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 20/滿足三角不等式的貨郎問題：MM算法分1G 4在上 MM(I)= =T的邊權和+M≤OPT(I)+1OPT(I)222

OPT(I) 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 21/0-1背包niwi（≤BS?{12···n}，滿足∑

wi≤∑ vi最大 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 22/0-1背包問題：GKK算法V2jvj>V，則最終背包只放物品jOPT(I)<GKK(I)+vk≤GKK(I)+vj≤ 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 23/0-1背包問題：PTAS?算1?>0m=?1/?? 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 24/0-1背包問題：PTAS?算法S?|S?|>m?GKKkS?OPT(I)<PTAS?(I)+≤PTAS?(I)+1PTASm≤(1+1m≤(1+PTAS?(1+?)- 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 25/0-1背包問題：FPTAS?FPTAS?V=maxvi|i=12···n1?>0b=max(?V1+1)n?,2ii

=?vi/b?解 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 26/0-1背包問題：FPTAS?算法分?S?b=max(?V1+1)n?,1)>?OPT(I)?FPTAS(I) vi =( vi? v′)+ v′? v′)+ v′ vii

i v′ i ≤V/(1+1?≤OPT(I)/(1+1?FPTAS?是(1+?)- 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 27/大1大2344() 2016-01-29綿 28/()隨機算法分 型 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 29/隨機快速排if≤1returnA←pB←pC←pAreturnA,B, 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 30/(()2016-01-29綿 31/T(N)≤2nln

T(n)=(n?1)

ni

[T(i)+T(n?i?T(n)≤(n?1)

ni∫

2iln≤(n?1)+n1

2iln (n?1) (nlnn ≤2nln 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 32/ 量Xij

{ij T(n)=

Xij)

E(Xiji=1j=i+1 i=1j=i+1

P(Xij=1)i=1j=i+1 i=1j=i+1

j?i+

= +··· n?i+i<2n(1+1+···+1)<2nln 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 33/(()2016-01-29綿 34/串相等串相等1A2AM3Ap(xmodp4B(ymodp(xmodp

p|(x? 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 35/(()2016-01-29綿 36/π(n) k<2nnkπ(n)串相等測試：隨機算|x|=|y|=LM≥π(L) L/lnPerror<π(M)≈2L2/ L/ln ≤2L2/2ln

p的位數+(xmodp)≤2(?logM?+1)≈4log 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 37/模式匹|x|m≤n|y|經典算法：KMPO(mn) 近似算法與隨機算法的分析方法與應用實 2016-01-29綿 38/模式匹配：隨1M=2mn2M2xmod3y[i..(i+m?1)]modpx