{1,2}-賦權(quán)圖最小最大2-路徑覆蓋問題的近似算法

姚會影，周 圓，陳光亭，陳 永，張 安

(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；2.臺州學(xué)院電子與信息工程學(xué)院，浙江 臺州 318000)

0 引 言

1 問題描述

邊賦權(quán)完全圖上的旅行售貨商問題與最小最大2-路徑覆蓋問題定義如下：給定一邊賦權(quán)完全圖G=(V,E)，其中|V|=n，邊e∈E的權(quán)重為w(e)。TSP問題的目標(biāo)是尋求覆蓋G中所有頂點的一個圈，使得圈中各邊的權(quán)重之和盡可能小。最小最大2-路徑覆蓋問題的目標(biāo)是尋求覆蓋G中所有頂點的2條頂點互不相交的路徑，使得權(quán)重較大的路徑的權(quán)重盡可能小，其中路徑的權(quán)重是指路徑中所有邊的權(quán)重之和。

本文研究邊權(quán)重為1或2的完全圖上最小最大2-路徑覆蓋問題，即G中各邊權(quán)重需滿足：

w(e)∈{1,2},?e∈E

(1)

對于該問題，當(dāng)n≤6時，問題規(guī)模較小，通過窮舉法就能得到最優(yōu)解。因此，本文僅對n≥7的情況來設(shè)計近似算法。

2 算法設(shè)計與分析

本文設(shè)計的近似算法主要基于文獻(xiàn)[4]提出的TSP算法，將其命名為基于TSP的近似算法。首先調(diào)用文獻(xiàn)[4]關(guān)于TSP問題的算法，找到覆蓋G中所有頂點恰好一次的圈C；然后刪除圈C中2條不相鄰的邊，構(gòu)成2條頂點不相交的路徑P1和P2，為了使得其中的最大路徑權(quán)重盡可能小，刪邊時應(yīng)確保P1和P2的權(quán)重盡量均衡。當(dāng)圈C中的邊權(quán)重均為1時，刪邊過程是簡單的；當(dāng)圈C中包含至少1條權(quán)重為2的邊時，本文算法采取一種貪婪的刪邊方法，具體步驟如下。

(2)在圈C中任選一條權(quán)重為2的邊，記為e1。從邊e1出發(fā)，按順時針順序?qū)θχ懈鳁l邊進(jìn)行編號，記EC={e1,e2,…,en}，刪去圈C中的邊e1。

(4)將由邊集{e2,e3,…，ej-1}構(gòu)成的路徑記為P1，由邊集{ej+1,ej+2,…,en}構(gòu)成的路徑記為P2。

(5)比較路徑P1和P2的權(quán)重，輸出權(quán)重較大的路徑P作為算法解。

w(P)=max{w(P1),w(P2)}

(2)

(3)

(4)

(5)

由式(1)可得：

(6)

由式(3)、式(5)、式(6)可得：

(7)

w(P*)≥3

(8)

證明由P1={e2,e3,…，ej-1}，P2={ej+1,ej+2,…，en}，3≤j≤n-1，可得：

(9)

由于路徑P1,P2和邊e1,ej構(gòu)成圈C，有

w(P1)+w(P2)+w(e1)+w(ej)=wtsp

(10)

由本文算法的步驟3可得：

(11)

(12)

由式(10)、式(11)，及w(e1)=2，可得：

(13)

由式(4)、式(12)、式(13)，知

(14)

由式(7)、式(8)、式(14)，知

為了便于理解本文提出的基于TSP的近似算法，通過1個算例來詳細(xì)闡述算法的執(zhí)行過程，如圖1所示。圖1中，實線表示權(quán)重為2的邊，虛線表示權(quán)重為1的邊，其中未畫出的邊權(quán)重均為1。

圖1 圖G、最優(yōu)解、圈C及算法解圖

假設(shè)1個頂點數(shù)n=11的{1,2}-賦權(quán)完全圖G=(V,E)，如圖1(a)所示。其中V={v1,v2,…,v11}，G中各邊權(quán)重定義如下：w(vi,vi+1)=2(i=1,2,…,10)，w(v1,vj)=2(j=3,4,…,10)，其余各邊權(quán)重均為1。

3 結(jié)束語