有很多問題有其理論上或?qū)嶋H上的重要性

35.ApproximationAlgorithms有很多問題有其理論上或?qū)嶋H上的重要性，但若不幸被證出它是NP-hard在目前強烈猜測它是不太可能有polynomialtimealgorithm，則是否我們就要放棄它們了呢?正好相反!目前猜測雖然是不太可能有polynomialtimealg.找出optimalsolution，但是在這一章要看一些例子，我們能有polynomialtimealgorithm找出nearlyoptimalsolution如此之a(chǎn)lgorithm雖不能保證找到optimalsolution，卻保證能找出nearlyoptimalsolution叫做approximationalg.針對NP-hardproblem，有時一定想找exactsolution，則下面舉一些方法:backtracking,branchandbound,dynamicprogramming…基本上這些方法都是exhaustsearch，所以可以料到的在worstcase下，表現(xiàn)都不會很好，但averagecase下有時是不錯的，這一類的paper常會受到重視的即使是worstcase有時也可證出:例如由O(2n)降到O(2n/2)，或由O(n!)降到O(2n)之類的或者得到一個pseudopolynomialtimealgorithm也是不錯的結(jié)果針對某些問題有時並不要求找出optimalsolution，只要找到一個不錯的solution就滿足了，則文獻中，也有人施出不同的招式，例如:1.Approximationalgorithm:absoluteapproximate,ε-approximate,polynomialtimeapproximationscheme,fullypolynomialtimeapproximationacheme2.Randomalgorithm,probabilisticalgorithmaveragecaseanalysis3.Subexponentialalgorithms,ex:O(2n)O(2n/2)4.Localsearch5.Heuristicalgorithms6.考慮specialcase，用specialalgorithms以上這些怪招都需看更多例子才能明瞭例:vertex-coverproblem下面一邊看例子，一邊介紹名詞Minvertex-coverproblem是NP-hard，但是卻有efficientalgorithm能找出一個approximatesolution作法很簡單:任意找一尚未被控制的edge把u和v兩vertices全部抓進vertexcoverC中，然後把u或v所能控制的edge全delete掉並繼續(xù)之下面要證明如此最後所得到的vertexcoverC與真正的minvertexcoverC*頂多是2倍而已。即ratiobound是C/C*≤2,即C≤2C*relativeerrorbound|C-C*|/C*≤1。或叫errorratiouev證明很明顯，此algorithm最終一定找出一個vertex-covertimecomplexO(|E|)要證出所找到的C與optimalvertexcoverC*頂多是C*的2倍而已考慮任一edge，則因C*是vertexcoveru或v中至少有一個在C*中，如此C*中任一vertex，我們頂多多拿了另一個vertex陪它，所以C≤2C*，得證此例叫做找到一個relativeerrorbound是1的approximationalg.，或找到一個rationbound是2的approximationalg.Traveling-salesmanproblem(T.S.P.)這是一個很著名的問題，而一直沒有滿意的解答，很多人使出各種怪招去解它，在這一節(jié)我們用另外一個角度去看它:不是去想怪招解它，而是提出一點證據(jù)顯示T.S.P.確是一個難纏的問題:因為1.T.S.P.是NP-hard；2.而且就算想放鬆一點條件:找一個polynomialtimeapproximationalgorithmwithanyratioboundρ，也是NP-hard，證明如下頁證明如果存在某一ρ≥1而存在某一個polynomialtimealg.，它能保證達到ratioboundρ的話，將證出hamiltonian-cycleproblem可以reduce到此問題How?假設(shè)G=(V,E)是一個hamiltoniancycleproblem的instance，用下面之技巧將此instance轉(zhuǎn)換成一個T.S.P.的instance將graphG之edgeassigncost如下:c(u,v)=1ifG有此edgec(u,v)=kifG無此edge就成為一completegraph叫G’=(V,E’)前述T.S.P.instance如果有一個hamiltoniancycle的話它的T.S.P.optimaltour總長c(T*)=|V|。它的secondbesttour呢?總長至少是k+(|V|-1)。Second和first之差距:至少k-1若有一個ratiobound是ρ的polynomialtimeapproxalgA它保證所找到的T.S.P.tourT其誤差與optimaltourT*不超過c(T)-c(T*)≤(ρ-1)c(T*),只要取k-1>(ρ-1)|V|,即k>(ρ-1)|V|+1，則用此algorithmA在G’找approximatetour確定會發(fā)生:如果G中有hamiltoniancycle則alg.A就會找到一個H.C.因為就算secondbest其誤差也超過(ρ-1)|V|，而alg.A保證誤差不超過(ρ-1)|V|!如果G中沒有H.C.呢?alg.A所找到的T.S.P.tour其總長至少k+(|V|-1)，因而可判知G沒有H.C.，得證H.C.problem≤P

ρapproximateT.S.P.problem已知左方是NP-hard右方也是NP-hard。得證c(T)≤c(minhamiltoniancycle)--B由A和Bc(3)≤2倍c(minhamiltoniancycle)，得證Timecomplexity?Polynomialtime!介紹名詞Approximatealgorithm:一個approximatealgorithm能保證relativeerror在ε以內(nèi)，即|C*-C|/C≤εApproximatescheme:是一個approximatealgorithm其input不只是instanceoftheproblem，還input任一個ε，對任一個ε，它都能保證是ε-approximatealgorithmPolynomialtimeapproximatescheme:是一個approximatescheme，而其timecomplexity是polynomialfunctionininputsizen，例O(n1/ε)Fullypolynomialtimeapproximatescheme:是一approximatescheme，而其timecomplexity是polynomialfunctioninbothinputsizenandin1/ε，對n及1/ε兩者看都是poly.function。例:O(n1/ε)不是；O((1/ε)2n3)是!以一例說明fullypolynomialtimeapproximateschemeSubsetsumproblem:decision形式:給定S={x1,x2,…xn}及t，皆正整數(shù)。問S是否有一subset其加總等於t例S={1,4,5}，t=3無；t=6有此問題有一個polynomialequivalent的optimization形式。給定S={x1,x2,…xn}及t，皆正整數(shù)。要找出S的一個subset使其加總不超過t，但希望加總越大越好。稱為Knapsackproblem下面要看一個解Knapsackproblem的approximatealg.，最後會看出其timecomplexity是O(n2lnt/ε)是poly.functionininputsizen，lntand1/ε用一個來瞭解課本之a(chǎn)pproximatealgorithm:這是一個Knapsackproblem:S={104,102,201,101},t=308但容許relativeerrorε=0.2仔細思考一下，可以省一點事1.t=308凡是大於308之node就應(yīng)及早殺掉，避免再作虛功2.容許relativeerrorε:(1-ε)C*≤C≤C*，所以在同一level中，任兩nodes若發(fā)現(xiàn)y2,y1使得(1-ε)y1≤y2≤y1，就可以把y1之node殺掉，因y2可代表y1，有y2就可使relativeerror在容許範(fàn)圍內(nèi)例:在level2中，(1-ε)104≤102≤104，於是104的node可殺掉，有102代表104就可例:其他level中也有些node可殺掉:重點是每產(chǎn)生一層就要立刻殺掉該殺的，就可省下大量功夫3.但2.之作法有點問題，如下:例如在某一level中發(fā)現(xiàn)(1-ε)y1≤y2≤y1，於是殺掉nodey1，y2可代表y1。但在下一level中又發(fā)現(xiàn)(1-ε)y2≤y3≤y2，於是殺掉nodey2，y3可代表y2y3還得代表y1，但如此relativeerror加大了:因上述兩式(1-ε)2y1≤y3≤y1，relativeerror擴增為2ε-ε2=ε(2-ε)，幾乎擴大兩倍。以此類推，若y2代表y1，(1-ε)y1≤y2≤y1；y3代表y2，(1-ε)y2≤y3≤y2；…；yn代表yn-1，(1-ε)yn-1≤yn≤yn-1，則(1-ε)ny1≤yn≤y1，relativeerror增大不少!用微積分易證出:(1-ε)n≥1-nε

(1-ε)ny1≤yn≤y1，relativeerror可能增大至nε而無法接受解決方法殺掉node時不要太大刀闊斧，要保守一點。若容許relativeerror是ε，則用ε/n作砍頭的relativeerror標(biāo)準。即發(fā)現(xiàn)(1-ε/n)y1≤y2≤y1，才殺掉nodey1，問題就解決了。最後找出的approximatesolutionC(1-ε/n)nC*≤C≤C*，OK最後還有一個問題:timecomplexity呢?用上述heuristic規(guī)則殺掉nodes後，可以證出如下頁的結(jié)果Theorem1.上述generatingtree經(jīng)過上述規(guī)則trim後，其每一level之node