最少頂點覆蓋問題的研究

張惠玲+謝邱敏+李煒

【摘要】 對此最少頂點覆蓋問題，我們巧妙提出了兩種方法：1）建立整數(shù)規(guī)劃模型，用分支定界算法求解模型;2）將其轉(zhuǎn)換成最小支配集問題，最小支配集問題是NP完全問題，找不到多項式時間算法，我們分別采用貪心算法和近似算法（經(jīng)典的遺傳算法）求解。在此基礎(chǔ)上，我們還分析了兩種方法的優(yōu)缺點并將模型推廣使用。

【關(guān)鍵詞】最少頂點覆蓋整數(shù)規(guī)劃最小支配集貪心算法近似算法

一、問題簡述

考慮如下數(shù)學(xué)問題：

現(xiàn)有一片的矩形網(wǎng)絡(luò)圖，給定67個頂點的位置坐標(biāo)，現(xiàn)要選取其中的某些頂點作為圓心，以20為半徑作圓，要求能覆蓋全部頂點，求要選取頂點的最少數(shù)目，畫出覆蓋圖形。（如圖1）

【67個頂點的坐標(biāo)分別為（10，115），（33，26），（58，141），（0，19）， （1，170）， （77，149）， （80，68）， （46，46）， （91，111）， （70，56），（91，127）， （75，180）， （71，163）， （16，141）， （34，123）， （45，15）， （44，92），（34，183）， （33，75）， （17，181）， （15，26）， （57，70）， （92，82）， （97，182），（29，97）， （64，7）， （1，94）， （37，149）， （19，199）， （56，157）， （85，192），（82，39）， （75，134）， （96，65）， （97，42）， （50，128）， （68，112）， （80，6），（40，197）， （96，13）， （86，96）， （44，61）， （45，170）， （99，143）， （20，6），（4，151），（1，135），（0，54），（65，35），（48，113），（77，83），（30，55），（76，23），（49，30），（58，85），（62，188），（12，43），（1，190），（35，0），（69，97），（9，67），（21，165），（90，165），（16，88），（4，3），（99，198），（27，40）】

二、模型建立

2.1 基于整數(shù)規(guī)劃模型求解小規(guī)模最少頂點覆蓋問題

以所選頂點個數(shù)最少為目標(biāo)函數(shù)，約束條件是使得每個頂點都被覆蓋。即：

其中Vi為頂點符號，i=l，2…..67，S（vi）表示以Vi為圓心，半徑為d（=20）的區(qū)域，

設(shè)計如下算法：

Stepl：用MATLAB軟件確定67個頂點相互之間距離小于d的，整理成一張表格，即任意兩點之間距離小于d的記為l，否則記為0;

Step2：用LINGO軟件求解整數(shù)規(guī)劃問題;

Step3：用MATLAB軟件畫圖。

結(jié)果整理如下：

[11100 000 00010010110 000 00000000 000

0 01010 010 010110000000101110111010 0]

其中為1的地方表示此頂點被選為圓心，坐標(biāo)與題目所給數(shù)據(jù)相對應(yīng)。（如圖2）

結(jié)果顯示：21個。

2.2轉(zhuǎn)換為最小支配集問題求解

我們可以把這個問題當(dāng)做是尋找最小支配集。記頂點集合為v，最小支配集v*里面的頂點即為所求頂點，對于v-v*中的任一點Vj，必能找到V*中的點Vi，使得Vi與Vj之間有邊相連（距離小于d）。

2.2.1 貪心算法

首先我們考慮貪心算法，即先考慮能覆蓋最多頂點的頂點，以這些頂點為圓心，并同時排除與之相關(guān)聯(lián)的頂點。

把所給的矩形網(wǎng)絡(luò)圖視為一個無向圖（每個點是它的頂點，兩頂點相鄰接當(dāng)且僅當(dāng)兩點間的距離小于d），記頂點vi所對應(yīng)的度數(shù)（即鄰接頂點數(shù)）為ni。

貪心算法可描述為：

Stepl：將v中的頂點按頂點度數(shù)從大到小逆序排列成點集v′并全部頂點設(shè)置為未標(biāo)號;

Step2：取v中第一個頂點，若該點已經(jīng)標(biāo)號，在刪除該點v′，轉(zhuǎn)至步驟Step3;否則，將該點標(biāo)號為1，并將與之相關(guān)聯(lián)且未標(biāo)號的頂點標(biāo)號為0，在v′刪除該點;

Step3：若v′為空，轉(zhuǎn)至Step4;否則，轉(zhuǎn)至Step2;

Step4：取標(biāo)號為1的頂點作為支配點，把這些點組成的點集為最小支配集。

此算法求出的結(jié)果是圖的一個極小支配集。

利用MATLAB編程求得的極小支配集共有27個頂點，覆蓋圖形如下（如圖3）：

從圖中看出，有一些圓重復(fù)覆蓋了，使得頂點個數(shù)沒有達(dá)到最優(yōu)值。

2.2.2遺傳算法

參考相關(guān)文獻(xiàn)[3]，采用遺傳算法，模擬T=10000代，群體規(guī)模N=80，交叉概率取pm=0.05，變異概率pc=0.7，得到的最小支配集數(shù)目為：21。覆蓋圖形如下（如圖D）：

圖4節(jié)點位置改變后的遺傳算法

三、結(jié)束語

此問題的模型也可以進(jìn)一步推廣到更多的現(xiàn)實生活中的具體決策中來，比如已知需要保護(hù)的地區(qū)數(shù)量選擇最少的警衛(wèi)問題、無線傳感網(wǎng)絡(luò)最少偵聽器診斷問題等。針對本文最少頂點覆蓋問題，我們提出的兩種方法雖很巧妙，有很多優(yōu)點也有它的不足之處。

整數(shù)規(guī)劃模型很新穎，但處理過程有點煩雜，對于小規(guī)模問題一定是精確解，但畢竟LINGO軟件求解整數(shù)規(guī)劃是用分支定界算法，規(guī)模擴大十倍百倍計算機運行的時間就難以估量;貪心算法雖然針對小規(guī)模的問題誤差很大，但當(dāng)規(guī)模擴大，計算速度大大提高，誤差也會稍有改善;近似算法很好理解，但畢竟不是準(zhǔn)確算法，誤差也很難計量。

總而言之，此問題可以有很多解決的方法，而且我所提出的方法也有一些不足之處，希望讀者勇于思考，歡迎跟我一同探討。

參 考 文 獻(xiàn)[l]Han.Bo， Fu. Hao.huan， Lin.Lidong， Jia.Weijia，

"Efficient construction ofconnected dominatingset in wireless ad hoc networks" ，IEEE Intemational， Fort Lauderdale， FL， United states， 2004[2]廖飛雄，馬良，禁忌遺傳算法求解最小支配集，計算機工程與應(yīng)用，（ 24） 43， 81， 2007[3]《運籌學(xué)的原理和方法》（第二版），鄧成梁，華中科技大學(xué)出版社