近似算法與隨機(jī)化算法

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

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

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

3、*]=ε(n)，則稱ε(n)為該近似算法的相對(duì)誤差界。近似算法的性能比ρ(n)與相對(duì)誤差界ε(n)之間顯然有如下關(guān)系：ε(n)≤ρ(n)-1。頂點(diǎn)覆蓋問(wèn)題的近似算法問(wèn)題描述：無(wú)向圖G=(V,E)的頂點(diǎn)覆蓋是它的頂點(diǎn)集V的一個(gè)子集V'V，使得若(u,v)是G的一條邊，則v∈V'或u∈V'。頂點(diǎn)覆蓋V'的大小是它所包含的頂點(diǎn)個(gè)數(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用來(lái)存儲(chǔ)頂點(diǎn)覆蓋中的各頂點(diǎn)。初始為空，不斷從邊集e1中選取一邊(u,v)，將邊的端點(diǎn)加入cset中，并將e1中已被u和v覆蓋的邊刪去，直至cset已覆蓋所有邊。即e1為空。圖(a)~(e)說(shuō)明了算法的運(yùn)行過(guò)程及結(jié)果。(e)表示算法產(chǎn)生的近似最優(yōu)頂點(diǎn)覆蓋cset，它由頂點(diǎn)b,c,d,e,f,g所組成。(f)是圖G的一個(gè)最小頂點(diǎn)覆蓋，它只含有3個(gè)頂點(diǎn)：b,d和e。旅行售貨員問(wèn)題近似算法問(wèn)題描述：給定一個(gè)完全無(wú)向圖G=(V,E

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

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

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

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

11、C*

12、=min{

13、C

14、

15、CF且C覆蓋X}集合覆蓋問(wèn)題舉例：用12個(gè)黑點(diǎn)表示集合X。F={S1,S2,S3,S4,S5,S6,}，如圖所示。容易看出，對(duì)于這個(gè)例子，最小集合覆蓋為：C={S3,S4,S5,}。集合覆蓋問(wèn)題近似算法--貪心算法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、，