最少頂點(diǎn)覆蓋問題的研究

張惠玲+謝邱敏+李煒

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

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

一、問題簡述

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

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

【67個(gè)頂點(diǎn)的坐標(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ī)模最少頂點(diǎn)覆蓋問題

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

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

設(shè)計(jì)如下算法：

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

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

Step3：用MATLAB軟件畫圖。

結(jié)果整理如下：

[11100 000 00010010110 000 00000000 000

0 01010 010 010110000000101110111010 0]

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

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

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

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

2.2.1 貪心算法

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

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

貪心算法可描述為：

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

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

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

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

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

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

從圖中看出，有一些圓重復(fù)覆蓋了，使得頂點(diǎn)個(gè)數(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é)點(diǎn)位置改變后的遺傳算法

三、結(jié)束語

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

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

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

參 考 文 獻(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]廖飛雄，馬良，禁忌遺傳算法求解最小支配集，計(jì)算機(jī)工程與應(yīng)用，（ 24） 43， 81， 2007[3]《運(yùn)籌學(xué)的原理和方法》（第二版），鄧成梁，華中科技大學(xué)出版社