近似算法與隨機化算法

《近似算法與隨機化算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應用文檔-天天文庫。

1、近似算法與隨機化算法近似算法基本概念所有已知的解決NP-難問題算法都有指數(shù)型運行時間。但是，如果我們要找一個"好"解而非最優(yōu)解，有時候多項式算法是存在的。給定一個最小化問題和一個近似算法，我們按照如下方法評價算法：首先給出最優(yōu)解的一個下界，然后把算法的運行結(jié)果與這個下界進行比較。對于最大化問題，先給出一個上界然后把算法的運行結(jié)果與這個上界比較。近似算法比較經(jīng)典的問題包括：最小頂點覆蓋、旅行售貨員問題、集合覆蓋等。迄今為止，所有的NP完全問題都還沒有多項式時間算法。對于這類問題，通常可采取以下幾種解

2、題策略。(1)只對問題的特殊實例求解(2)用動態(tài)規(guī)劃法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用啟發(fā)式方法求解若一個最優(yōu)化問題的最優(yōu)值為c*，求解該問題的一個近似算法求得的近似最優(yōu)解相應的目標函數(shù)值為c，則將該近似算法的性能比定義為max(c/c*,c*/c)。在通常情況下，該性能比是問題輸入規(guī)模n的一個函數(shù)ρ(n)，即max(c/c*,c*/c)=ρ(n)。該近似算法的相對誤差定義為Abs[(c-c*)/c*]。若對問題的輸入規(guī)模n，有一函數(shù)ε(n)使得Abs[(c-c*)/c

3、*]=ε(n)，則稱ε(n)為該近似算法的相對誤差界。近似算法的性能比ρ(n)與相對誤差界ε(n)之間顯然有如下關(guān)系：ε(n)≤ρ(n)-1。頂點覆蓋問題的近似算法問題描述：無向圖G=(V,E)的頂點覆蓋是它的頂點集V的一個子集V'V，使得若(u,v)是G的一條邊，則v∈V'或u∈V'。頂點覆蓋V'的大小是它所包含的頂點個數(shù)

4、V'

5、。VertexSetapproxVertexCover(Graphg){cset=；e1=g.e；while(e1！=){從e1中任取一條邊(u,v)；cset=cse

6、t∪{u,v}；從e1中刪去與u和v相關(guān)聯(lián)的所有邊；}returnc}Cset用來存儲頂點覆蓋中的各頂點。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點加入cset中，并將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。圖(a)~(e)說明了算法的運行過程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點覆蓋cset，它由頂點b,c,d,e,f,g所組成。(f)是圖G的一個最小頂點覆蓋，它只含有3個頂點：b,d和e。旅行售貨員問題近似算法問題描述：給定一個完全無向圖G=(V,E

7、)，其每一邊(u,v)∈E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。旅行售貨員問題的一些特殊性質(zhì)：比如，費用函數(shù)c往往具有三角不等式性質(zhì)，即對任意的3個頂點u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。當圖G中的頂點就是平面上的點，任意2頂點間的費用就是這2點間的歐氏距離時，費用函數(shù)c就具有三角不等式性質(zhì)。對于給定的無向圖G，可以利用找圖G的最小生成樹的算法設(shè)計找近似最優(yōu)的旅行售貨員回路的算法。voidapproxTSP(Graphg){(1)選擇g的任一頂點r；

8、(2)用Prim算法找出帶權(quán)圖g的一棵以r為根的最小生成樹T；(3)前序遍歷樹T得到的頂點表L；(4)將r加到表L的末尾，按表L中頂點次序組成回路H，作為計算結(jié)果返回；}當費用函數(shù)滿足三角不等式時，算法找出的旅行售貨員回路的費用不會超過最優(yōu)旅行售貨員回路費用的2倍。(b)表示找到的最小生成樹T；(c)表示對T作前序遍歷的次序；(d)表示L產(chǎn)生的哈密頓回路H；(e)是G的一個最小費用旅行售貨員回路。一般的旅行售貨員問題在費用函數(shù)不一定滿足三角不等式的一般情況下，不存在具有常數(shù)性能比的解TSP問題的多

9、項式時間近似算法，除非P=NP。換句話說，若P≠NP，則對任意常數(shù)ρ1，不存在性能比為ρ的解旅行售貨員問題的多項式時間近似算法。集合覆蓋問題的近似算法問題描述：給定一個完全無向圖G=(V,E)，其每一邊(u,v)∈E有一非負整數(shù)費用c(u,v)。要找出G的最小費用哈密頓回路。集合覆蓋問題的一個實例〈X,F〉由一個有限集X及X的一個子集族F組成。子集族F覆蓋了有限集X。也就是說X中每一元素至少屬于F中的一個子集，即X=。對于F中的一個子集CF，若C中的X的子集覆蓋了X，即X=，則稱C覆蓋了X。集合覆

10、蓋問題就是要找出F中覆蓋X的最小子集C*，使得

11、C*

12、=min{

13、C

14、

15、CF且C覆蓋X}集合覆蓋問題舉例：用12個黑點表示集合X。F={S1,S2,S3,S4,S5,S6,}，如圖所示。容易看出，對于這個例子，最小集合覆蓋為：C={S3,S4,S5,}。集合覆蓋問題近似算法--貪心算法SetgreedySetCover(X,F){U=X；C=；while(U！=){選擇F中使

16、S∩U

17、最大的子集S；U=U-S；C=C∪{S}；}returnC；}算法的循環(huán)體最多執(zhí)行min{

18、X

19、，