劉子琳，王曉峰，2，蘆 磊，程亞南

(1. 北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，寧夏 銀川 750021；2. 北方民族大學(xué)圖像圖形智能處理國(guó)家民委重點(diǎn)實(shí)驗(yàn)室，寧夏 銀川 750021)

1 引言

在運(yùn)籌學(xué)中，最小支配集已經(jīng)被證明是一個(gè)NP難問(wèn)題[1]。最小支配集(Minimum Dominating Set，簡(jiǎn)稱(chēng)為MDS)是一種最重要的支配集問(wèn)題，在社會(huì)網(wǎng)絡(luò)[2]、城市交通網(wǎng)絡(luò)[3]，以及物流網(wǎng)絡(luò)中心的選址[4]等領(lǐng)域有著廣泛的應(yīng)用。最小支配集問(wèn)題的目的是構(gòu)造一個(gè)最小的節(jié)點(diǎn)集合，使得網(wǎng)絡(luò)的任何節(jié)點(diǎn)要么在該集合中，要么與該集合中至少一個(gè)節(jié)點(diǎn)相鄰。目前，求解最小支配集問(wèn)題的算法主要分為精確算法[5]和啟發(fā)式算法[6]，精確算法能夠處理一些小規(guī)模問(wèn)題，但處理大規(guī)模問(wèn)題時(shí)的時(shí)間復(fù)雜度和空間復(fù)雜度較高；啟發(fā)式算法能獲得較好近似度結(jié)果，時(shí)間復(fù)雜度較低，但容易陷入局部最優(yōu)解，其完備性和唯一性不能保證。

在無(wú)向圖G(V，E)中，V表示圖G中的所有節(jié)點(diǎn)，E表示所有節(jié)點(diǎn)之間的邊。令集合S={v1，v2，…，vm}，其中vm?V，若S?V，S≠?，對(duì)于?x∈V-S，x都與S中至少一個(gè)節(jié)點(diǎn)有邊相連，則稱(chēng)S是圖G的支配集。所有支配集中節(jié)點(diǎn)數(shù)目最少的則稱(chēng)為圖G的最小支配集。|S|為最小支配數(shù)，相關(guān)文獻(xiàn)中也用γ(G)表示[7]。

在求解最小支配集的相關(guān)算法研究中，文獻(xiàn)[5]描述了求解最小支配集的精確算法，錯(cuò)誤率較小，但時(shí)間復(fù)雜度極大。文獻(xiàn)[8]采用線性規(guī)劃的內(nèi)點(diǎn)法求解最大集合覆蓋，極大地降低了計(jì)算復(fù)雜度。文獻(xiàn)[9]比較了標(biāo)準(zhǔn)的貪婪算法、LP近似算法以及將貪婪算法和LP近似算法相結(jié)合而設(shè)計(jì)的混合算法的性能，得出了LP混合算法具有高效性。文獻(xiàn)[10]將粗糙集理論中的屬性序引入到圖論中，研究頂點(diǎn)序下圖的支配集問(wèn)題。文獻(xiàn)[11]通過(guò)對(duì)蟻群算法添加信息素校正策略，設(shè)計(jì)了求解最小連通支配集的蟻群優(yōu)化算法。局部搜索算法也已經(jīng)被提出來(lái)啟發(fā)式地解決MDS問(wèn)題[12-15]，到目前為止，最好的多項(xiàng)式算法只能保證得到的支配集的大小不超過(guò)最小值的lnN倍[16.17]。

線性規(guī)劃(Linear Programming)是運(yùn)籌學(xué)中研究、發(fā)展較成熟的一個(gè)重要分支，是一種用來(lái)輔助科研人員進(jìn)行科學(xué)研究的數(shù)學(xué)方法。線性規(guī)劃問(wèn)題一般是指求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問(wèn)題，構(gòu)建線性規(guī)劃方程來(lái)求問(wèn)題最優(yōu)解[18]。

近年來(lái)，信息傳播算法(Message Propagation Algorithm，MP)發(fā)展迅速，信息傳播算法基于統(tǒng)計(jì)物理學(xué)的“空腔”概念提出，是一種作用于因子圖(Factor Graph)上的概率算法[19，20]。在組合優(yōu)化問(wèn)題方面，信息傳播算法的應(yīng)用已取得豐碩的成果，如MAX-SAT問(wèn)題、Maximum-Weight Matching問(wèn)題、Minimum Cost Network Flow問(wèn)題、圖的著色、最大獨(dú)立集等[21]。文獻(xiàn)[20]提出了三種信息傳播算法求解可滿足問(wèn)題，分別為警示傳播(Warning Propagation，WP) 算法、置信傳播(Belief Propagation，BP) 算法和調(diào)查傳播(Survey Propagation，SP)算法，SP算法是目前求解可滿足問(wèn)題最為有效的算法，能夠稍高于線性時(shí)間求解難解SAT區(qū)域的具備107變量規(guī)模的實(shí)例，幾乎能夠有效求解接近相變點(diǎn)的可滿足性實(shí)例。文獻(xiàn)[22]指出，廣義葉子移除過(guò)程可以精確地解決MDS問(wèn)題，并用平均場(chǎng)方法求解了一個(gè)自旋玻璃模型來(lái)估計(jì)MDS的大小。文獻(xiàn)[23]指出，BP算法可以解決用線性規(guī)劃(Linear Programming，LP)公式來(lái)描述的組合優(yōu)化問(wèn)題，并且證明了其收斂性。文獻(xiàn)[24]設(shè)計(jì)了大量組合優(yōu)化問(wèn)題的BP算法，這對(duì)我們?cè)O(shè)計(jì)求解最小支配集的置信傳播算法很有參考意義。

基于上述研究，本文將MDS問(wèn)題的無(wú)向圖通過(guò)集合覆蓋映射為因子圖，基于因子圖構(gòu)建線性規(guī)劃方程，設(shè)計(jì)出一種求解最小支配集問(wèn)題的置信傳播算法。實(shí)驗(yàn)結(jié)果表明：本算法可以近似解決最小支配集問(wèn)題，且算法的性能優(yōu)于其它算法。

2 基本知識(shí)

2.1 集合覆蓋

給定一個(gè)全集U，集合S={S1，S2，…，Sn}，Si∈U且S1∪S2∪…∪Sn=U。集合覆蓋問(wèn)題要找到一個(gè)子集D={D1，D2，…Dk}，D∈S，使得D1∪D2∪…∪Dk=U，同時(shí)|D|最小。例如給定全集U={1，2，3，4，5}，S={{1，2，3}，{2，4}，{3，4}，{4，5}}，雖然S中所有元素的并集是U，但是可以找到S的一個(gè)最小子集D={{1，2，3}∪{4，5}}，使得{1，2，3}∪{4，5}=U，則集合D可以被稱(chēng)為一個(gè)集合覆蓋。

文獻(xiàn)[25]指出支配集可規(guī)約到集合覆蓋問(wèn)題，求解網(wǎng)絡(luò)無(wú)向圖的支配集時(shí)，可以先轉(zhuǎn)化成求集合覆蓋問(wèn)題的解。轉(zhuǎn)換的步驟為：遍歷所有的節(jié)點(diǎn)，將當(dāng)前遍歷到的節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)放置到同一個(gè)子集合中，則最小支配集問(wèn)題轉(zhuǎn)化為找到一個(gè)所含頂點(diǎn)個(gè)數(shù)最少的子集T，使得|T∩Sj|≥1，其中Sj是當(dāng)前節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的集合。相應(yīng)地，集合覆蓋問(wèn)題也可使用BP算法的思路去求解。

2.2 因子圖

因子圖(Factor Graph)用圖模型來(lái)代表變量之間的關(guān)系，可以將一個(gè)復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)模型化。因子圖是一個(gè)具有變量節(jié)點(diǎn)和因子節(jié)點(diǎn)的二部圖，可以將一個(gè)含有多個(gè)變量的全局函數(shù)因子分解，得到幾個(gè)局部函數(shù)的乘積。因此在最小支配集問(wèn)題上，網(wǎng)絡(luò)節(jié)點(diǎn)的聯(lián)合置信分布比較復(fù)雜的情況下，因子圖結(jié)合信息傳播算法可以將網(wǎng)絡(luò)節(jié)點(diǎn)的聯(lián)合置信分布進(jìn)行邊緣化，從而將復(fù)雜的實(shí)際問(wèn)題簡(jiǎn)單化。

圖1 因子圖模型

給定一個(gè)賦值指派z={x1，x2，…xn}∈{0，1}n，如圖1所示的因子圖模型，變量節(jié)點(diǎn)X={x1，x2，x3，x4}，因子節(jié)點(diǎn)F={fa，fb，fc}，當(dāng)且僅當(dāng)函數(shù)節(jié)點(diǎn)fn與變量節(jié)點(diǎn)xn之間有對(duì)應(yīng)關(guān)系時(shí)，兩者有邊相連。則圖1中的因子圖關(guān)系可以表示為Pr[Z=z]=fa(x1，x3)fb(x1，x2，x4)fc(x2，x4)。因此我們可用如下GM公式表示因子圖：

(1)

3 因子圖轉(zhuǎn)換算法

根據(jù)網(wǎng)絡(luò)支配集的特性，可以將無(wú)向網(wǎng)絡(luò)圖的各個(gè)節(jié)點(diǎn)映射成變量節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)構(gòu)成的子集合映射成函數(shù)節(jié)點(diǎn)，即可生成對(duì)應(yīng)問(wèn)題的因子圖模型。相對(duì)應(yīng)的，在集合覆蓋問(wèn)題中，一個(gè)集合對(duì)應(yīng)一個(gè)因子節(jié)點(diǎn)，集合里面的變?cè)礊橐蜃庸?jié)點(diǎn)的所有鄰居節(jié)點(diǎn)。下面我們給出最小支配集問(wèn)題對(duì)應(yīng)的無(wú)向圖與因子圖之間的轉(zhuǎn)換算法。

算法開(kāi)始時(shí)隨機(jī)生成無(wú)向圖鄰接矩陣，首先生成各節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)構(gòu)成的集合，映射成函數(shù)節(jié)點(diǎn)，圖中的各個(gè)頂點(diǎn)則映射成變量節(jié)點(diǎn)。最后獲得變量節(jié)點(diǎn)和函數(shù)節(jié)點(diǎn)的對(duì)應(yīng)關(guān)系，構(gòu)造成因子圖。具體算法過(guò)程如下：

算法1：因子圖轉(zhuǎn)換算法

輸入：無(wú)向圖

輸出：因子圖模型

1)生成無(wú)向圖鄰接矩陣；

2)生成各節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)構(gòu)成的子集合；

3)無(wú)向圖中的節(jié)點(diǎn)映射為因子圖中的變量節(jié)點(diǎn)；

4)一個(gè)子集合為一個(gè)函數(shù)節(jié)點(diǎn)，并向集合里面的變?cè)?jié)點(diǎn)添加邊。

具體轉(zhuǎn)化結(jié)果如圖2、圖3所示。

圖2 無(wú)向圖G

圖2是一個(gè)無(wú)向圖G(V，E)，頂點(diǎn)集V={1，2，3，4，5，6}。最小支配集為{3，5}或{2，3}，最小連通支配集為{2，3}。轉(zhuǎn)化成集合覆蓋問(wèn)題，則有6個(gè)集合，分別為：S1={1，2，5}，S2={2，1，3，5}，S3={3，2，5，6}，S4={4，3}，S5={5，1，2，6}，S6={6，3，5}。

圖3 圖2對(duì)應(yīng)的因子圖模型

如圖3所示，將6個(gè)節(jié)點(diǎn)映射成為變量節(jié)點(diǎn)，6個(gè)集合S={S1，S2，S3，S4，S5，S6}代表每個(gè)節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)構(gòu)成的集合，映射成函數(shù)節(jié)點(diǎn)。算法由Sn與n之間相互傳遞消息，改變兩類(lèi)節(jié)點(diǎn)的信息，直至收斂。

4 最小支配集的信念傳播算法

4.1 置信迭代方程

BP算法的迭代方程為

(2)

(3)

其中Z是歸一化函數(shù)。

4.2 最小支配集線性規(guī)劃方程

最小支配集問(wèn)題是一類(lèi)經(jīng)典的組合優(yōu)化問(wèn)題，該問(wèn)題的LP方程

(4)

其中δ(a)是因子圖中因子節(jié)點(diǎn)a的所有相鄰變量節(jié)點(diǎn)，xi對(duì)應(yīng)因子圖中變量節(jié)點(diǎn)，xi=1表示選取該點(diǎn)選入最小支配集中，xi=0表示不選取，則對(duì)GM模型有如下定義

(5)

對(duì)于最小支配集問(wèn)題的能量函數(shù)ψa定義如下

(6)

4.3 最小支配集的置信傳播算法

算法2： BP-update算法

輸入：MDS對(duì)應(yīng)的因子圖，最大迭代次數(shù)tmax；精度ε

0)初始化：對(duì)于因子圖的每個(gè)邊a→i，隨機(jī)初始化消息μa→i(xi)∈[0，1]

1)從t=1到t=tmax：

(7)

因子圖變量節(jié)點(diǎn)的概率即為無(wú)向圖節(jié)點(diǎn)的取值概率，根據(jù)式(3)得到每個(gè)節(jié)點(diǎn)的取值概率，構(gòu)建出節(jié)點(diǎn)的概率向量p=(p(1)，p(2)…p(n))。通過(guò)以下算法求出具體的最小支配集。定義一個(gè)最小支配集τ={x1，x2，…，xn}，如果xi=1，則在最小支配集集合中；如果xi=0，則不在最小支配集集合中。下面給出求解MDS的BP算法，記為BP-MDS算法。

算法3： BP-MDS算法

輸入：節(jié)點(diǎn)的取值概率向量p；節(jié)點(diǎn)集合[nodes]

輸出：最小支配集τ

for i in [nodes]：

if pi(1)>pi(0)：

xi=1

elif pi(1)

xi=0

else：

xi=none

if τ is not [dominating set]：

for i in [nodes]：

if len([xi+neighbor(xi)])<1：

j=random[xi+neighbor(xi)]

xj=1

for i in [nodes]：

if xi==0：

continue

else：

xi=0

if τ is not [dominating set]：

xi=1

5 數(shù)值實(shí)驗(yàn)及分析

本文實(shí)驗(yàn)以普通PC的64位Windows10操作系統(tǒng)為平臺(tái)，基于Python3.7進(jìn)行算法測(cè)試。

圖4 不同節(jié)點(diǎn)規(guī)模的收斂速度

圖4所示為BP-MDS算法在不同節(jié)點(diǎn)規(guī)模下的收斂速度。隨機(jī)選取三組節(jié)點(diǎn)規(guī)模的無(wú)向圖，其中節(jié)點(diǎn)規(guī)模n={50，100，200}，不同規(guī)模分別隨機(jī)生成100組實(shí)例進(jìn)行實(shí)驗(yàn)。橫坐標(biāo)是迭代次數(shù)，縱坐標(biāo)是收斂概率。由圖可見(jiàn)，隨著節(jié)點(diǎn)規(guī)模增加，迭代次數(shù)增大，收斂速度變慢，意味著算法的效率逐漸降低。但后期始終可以收斂，說(shuō)明收斂速度并沒(méi)有影響算法的尋優(yōu)質(zhì)量，很好地驗(yàn)證了BP-MDS算法的可行性。

圖5 三種算法的平均最優(yōu)解

圖5是KCenters算法、貪婪算法與BP-MDS算法在不同節(jié)點(diǎn)規(guī)模下得到的平均最小支配集大小。對(duì)n個(gè)節(jié)點(diǎn)生成的隨機(jī)無(wú)向圖求最小支配集，對(duì)三種算法在50組實(shí)例中取得的解求平均值進(jìn)行比較?？梢钥吹叫∫?guī)模實(shí)例中(n<=20)，三種算法的求解質(zhì)量相近。但隨著節(jié)點(diǎn)規(guī)模增加，BP-MDS算法的求解質(zhì)量明顯優(yōu)于KCenters算法和貪婪算法。由此可見(jiàn)，隨著n增大，BP-MDS算法求解性能優(yōu)于另外兩種算法。

圖6 BP-MDS算法收斂性

圖6所示是BP-MDS算法在不同規(guī)模下的收斂性。隨著規(guī)模n的增大，算法求得的解空間也較大，大大增加了運(yùn)行時(shí)間和迭代次數(shù)，當(dāng)?shù)螖?shù)達(dá)到最大值，算法強(qiáng)制退出。雖然隨著問(wèn)題規(guī)模的增大BP算法效率有一定降低，但是經(jīng)過(guò)表1可得，BP算法的效率仍然優(yōu)于其他算法。

表1是BP-MDS算法與KCenters算法、遺傳算法在不同規(guī)模下求得平均最優(yōu)解的時(shí)間比較。其中n是節(jié)點(diǎn)規(guī)模，AVG是平均最優(yōu)解，Time是求得最優(yōu)解的平均時(shí)間?？梢钥吹皆谛∫?guī)模實(shí)例下，雖然BP-MDS算法的求解效率略低于KCenters算法，求得解的質(zhì)量卻始終優(yōu)于KCenters算法。隨著規(guī)模增大，BP-MDS算法在時(shí)間和求解質(zhì)量上都要優(yōu)于另外兩種算法。

表1 三種算法的平均時(shí)間

6 總結(jié)

本文設(shè)計(jì)了求解無(wú)向圖的最小支配集問(wèn)題的置信傳播算法，將把最小支配集映射成因子圖，構(gòu)建基于因子圖的線性規(guī)劃方程，代入BP迭代方程中，不斷迭代直至收斂得到實(shí)驗(yàn)結(jié)果，同時(shí)這種算法也為集合覆蓋問(wèn)題的求解提供了思路。實(shí)驗(yàn)結(jié)果表明，置信傳播算法求解的時(shí)間復(fù)雜度較低，效率較高，總體來(lái)說(shuō)其性能優(yōu)于傳統(tǒng)的啟發(fā)式算法和分布式算法。但缺陷是隨著問(wèn)題規(guī)模的增大，可能產(chǎn)生不收斂的現(xiàn)象。接下來(lái)的工作是盡量解決大規(guī)模不收斂的情況，設(shè)計(jì)求解最小支配集的調(diào)查傳播算法、用信息傳播算法求解支配集及其變種問(wèn)題、將線性規(guī)劃模型推廣到更多的組合優(yōu)化問(wèn)題等等。