-第15章近似算法-PPT課件

1、第15章 近似算法0/1背包MMMSTTSP就是貨郎擔(dān)問(wèn)題第15章 近似算法很多問(wèn)題的輸入數(shù)據(jù)是用測(cè)量方法取得的, 存在一定的誤差, 即輸入數(shù)據(jù)是近似的。很多問(wèn)題的最優(yōu)解允許有一定程度的近似, 只要誤差在一個(gè)有效范圍內(nèi)即可。采用近似算法可以在很短時(shí)間內(nèi)得到問(wèn)題的解 (與指數(shù)時(shí)間相比較)。15.1 近似算法的性能比 1. 近似算法的基本要求算法能在問(wèn)題規(guī)模n的多項(xiàng)式時(shí)間內(nèi)完成;算法的近似解滿足一定的精度要求。2. 近似算法的近似比令表示一最小化問(wèn)題, I是的一個(gè)實(shí)例, A是求解的一個(gè)近似算法, A(I)是近似解值, OPT是求解的最優(yōu)算法, OPT(I)是最優(yōu)解值, 則近似算法A的近似比為:A(

2、I)=A(I)/OPT(I)若是最大化問(wèn)題, 則A(I)= OPT(I)/A(I)說(shuō)明: 1) 對(duì)最小化問(wèn)題, 有A(I)OPT(I) 對(duì)最大化問(wèn)題, 有A(I)OPT(I)2) 近似算法的近似比總大于等于13) 近似算法的近似比越小, 性能越好A(I)=A(I)/OPT(I)A(I)= OPT(I)/A(I)3. 近似算法的相對(duì)誤差相對(duì)誤差的定義:相對(duì)誤差的界(n): 近似比與相對(duì)誤差界的關(guān)系: (n) A(I)-1, 即A(I) 1+(n) 4. 優(yōu)化問(wèn)題的近似方案 (approximation scheme) 很多難解問(wèn)題可通過(guò)增加近似算法的計(jì)算量來(lái)改善其性能;優(yōu)化問(wèn)題的近似方案把滿足A

3、(I,)1+（在誤差范圍內(nèi)）的一類(lèi)近似算法A|0稱(chēng)為優(yōu)化問(wèn)題的近似方案, 這些算法的性能比率會(huì)聚于1。 多項(xiàng)式近似方案 若近似方案中的每個(gè)算法A均以輸入實(shí)例規(guī)模的多項(xiàng)式時(shí)間運(yùn)行, 則稱(chēng)該近似方案為多項(xiàng)式近似方案(Polynomial Approximation Scheme) 多項(xiàng)式近似方案中算法的計(jì)算時(shí)間不隨的減少而增長(zhǎng)太快。 完全多項(xiàng)式近似方案若近似方案中每個(gè)算法的計(jì)算時(shí)間是1/和n的多項(xiàng)式, 則稱(chēng)該近似方案為完全多項(xiàng)式近似方案(Fully Poly-nomial Approximation Scheme)滿足三角不等式的旅行商問(wèn)題 歐幾里得旅行商問(wèn)題:給定賦權(quán)無(wú)向圖G=(V,E), 旅行

4、商問(wèn)題求圖中最短Hamilton回路。若圖中頂點(diǎn)是平面上的頂點(diǎn), 以任意兩頂點(diǎn)之間的歐幾里德距離作為它們之間的距離, 則為歐幾里德旅行商問(wèn)題。15.2 歐幾里得旅行商問(wèn)題算法1. 最近鄰算法(NN, 貪心)kruscal任選一個(gè)頂點(diǎn)作為起點(diǎn), 選取最鄰近該起點(diǎn)的一個(gè)頂點(diǎn), 關(guān)聯(lián)于起點(diǎn)和該頂點(diǎn)的邊作為初始旅游通路;令v表示剛加到旅游通路上的新頂點(diǎn)。在不屬于該旅游通路上的頂點(diǎn)中選一個(gè)最鄰近頂點(diǎn)v的頂點(diǎn)v, 將關(guān)聯(lián)于v與v的邊加到已有旅游通路上;重復(fù)執(zhí)行(2), 逐點(diǎn)擴(kuò)充旅游通路, 直到所有頂點(diǎn)都包含在這條旅游通路上;將形成的旅游通路的起點(diǎn)和終點(diǎn)用邊聯(lián)結(jié), 形成所求的旅游回路.NN算法: NN=算法

5、2. 最小生成樹(shù)算法(MST)對(duì)旅行商問(wèn)題任意實(shí)例對(duì)應(yīng)的賦權(quán)圖, 調(diào)用最小生成樹(shù)算法, 求其最小生成樹(shù); prim O(n2) 或 kruscal O(nlogn)復(fù)制最小生成樹(shù)的每條邊, 即沿每條邊來(lái)回走兩次, 形成歐拉圖;在這個(gè)歐拉圖中尋找其歐拉回路;利用“抄近路”方法將歐拉回路變成所求旅游回路 (因滿足三角不等式,故采用“抄近路”方法不會(huì)增加旅游回路的長(zhǎng)度)。定理1. 對(duì)滿足三角不等式的旅行商問(wèn)題的任意實(shí)例I, 有MST2證明: 因最小生成樹(shù)長(zhǎng)度 OPT(I), AMST(I) 2*最小生成樹(shù)長(zhǎng)度, 故 AMST(I) 2*OPT(I) 即 MST(I)=AMST(I)/OPT(I)2M

6、ST算法的實(shí)現(xiàn)步驟用Prim或Kruskal算法構(gòu)造給定賦權(quán)圖的最小生成樹(shù);用深度優(yōu)先搜索算法遍歷最小生成樹(shù), 得到按先序遍歷順序存放的頂點(diǎn)序號(hào)（得到序列）, 則數(shù)組中順序存放的頂點(diǎn)序號(hào)即為歐幾里德TSP的近似解。算法3. MM算法對(duì)旅行商問(wèn)題任意實(shí)例對(duì)應(yīng)的賦權(quán)圖, 調(diào)用最小生成樹(shù)算法, 求其最小生成樹(shù)T; 對(duì)最小生成樹(shù)T中頂點(diǎn)的度數(shù)為奇數(shù)的頂點(diǎn)集V=a1,a2,a2k, 調(diào)用最小對(duì)集（偶數(shù)個(gè)頂點(diǎn)的完全圖）算法, 在圖G中求出V的最小對(duì)集M;（度數(shù)為奇數(shù)的點(diǎn)一定是偶數(shù)個(gè)）。在最小生成樹(shù)T上添加V的最小對(duì)集M, 形成歐拉圖G;（每個(gè)點(diǎn)的度數(shù)都是偶數(shù)）在歐拉圖G中尋找其歐拉回路（找到定點(diǎn)序列）;利

7、用“抄近路”方法將歐拉回路變成所求的旅游回路。定理2. 對(duì)滿足三角不等式的貨郎問(wèn)題的任意實(shí)例I, 有MM3/2證明: (1)最小生成樹(shù)T的邊長(zhǎng)之和小于最短旅游回路; d(T)OPT(I)(2)因?qū)嵗凉M足三角不等式, 故賦權(quán)圖G中經(jīng)過(guò)V中頂點(diǎn)的最短旅游回路長(zhǎng)度必小于經(jīng)過(guò)圖G中所有頂點(diǎn)的最短旅游回路長(zhǎng)度。d(ep)=1/2opt(i)在經(jīng)過(guò)V中頂點(diǎn)的最短旅游回路中, 每隔一條邊刪除一條邊, 得到V的對(duì)集M, 而步驟(2)找出的是V的最小對(duì)集M。它們之間的關(guān)系為:最小對(duì)集M中邊長(zhǎng)度之和 對(duì)集M中邊長(zhǎng)度之和 V中最短回路長(zhǎng)度的一半 實(shí)例I中最短回路長(zhǎng)度的一半因此,步驟(2)中求出的V中最小對(duì)集M的邊長(zhǎng)

8、度之和不會(huì)超過(guò)實(shí)例I中最短回路長(zhǎng)度之和的一半;(3)歐拉圖G的所有邊長(zhǎng)度之和小于實(shí)例I中最短回路長(zhǎng)度之和的3/2倍; (4)因滿足三角不等式, 故采用抄近路方法在歐拉圖G中找出的旅游回路長(zhǎng)度AMM(I)小于實(shí)例I中最短回路長(zhǎng)度的3/2倍.因此, AMM(I)3/2OPT(I), 即MM 2 算法所求解為u1, 最優(yōu)解為u2C可能任意大, 故性能比可能無(wú)界.對(duì)算法做簡(jiǎn)單修改可使性能比為2.修改算法的步驟:對(duì)物體按pi/vi降序排序, 并依次裝入背包, 得到價(jià)值為pr的解; 挑選一個(gè)價(jià)值最大的物體裝入背包, 得到價(jià)值為ps;選擇pr和ps中較大者作為輸出。算法 Knapsack-Problem近似

9、算法輸入: U=u1,u2,un,V=v1,v2,vn, P=p1,p2,pn, C輸出: 價(jià)值最大的子集SU 排序使 p1/v1 p2/v2 pn/vn i0; v0; p0; S; /初始化 while in and vC if vi C-v SSui; vv+vi; pp+pi; ii+1; 令S=us, 其中us為價(jià)值最大物體; If pps return S; else return S.0/1背包問(wèn)題的多項(xiàng)式近似方案算法步驟: n個(gè)物體按價(jià)值體積比遞減排序; k=1/; i=0; for(i=0;i=k;i+)for(j=1;j= Cni;j+)2) j=1; 3)從n個(gè)物體中選取

10、i個(gè)物體放進(jìn)背包,這種選擇共有Cni組, 選擇第j組i個(gè)物體, 其余物體的選擇按貪心算法執(zhí)行; 令結(jié)果背包中物體總價(jià)值為vj, 保存背包中物體序號(hào)的數(shù)組為kpj;4)若jk, 令Y=u1,u2,uk是X中k個(gè)價(jià)值最大的物體集合,令Z=uk+1, uk+2, , ur是X中其余物體的集合。平均數(shù)：當(dāng)ik+1時(shí)，平均值一直在減少假定對(duì)滿足k+1 i r-1的所有的i, 有 對(duì)所有的i, i=k+1, , r, 有 |X|k, 集合Y必是算法第3步中Cni組選擇中的某一組選擇。算法所選物體一部分包含在集合Z中, 另一部分不包含在集合Z中。令不包含在Z中那部分物體為W, 必定存在物體um使得Z中uk+1, uk+2,um-1是算法所選物體。把最優(yōu)解的結(jié)果寫(xiě)成: 把算法的結(jié)果寫(xiě)成: 令