關(guān)于連通誤報(bào)容錯(cuò)支配集的一個(gè)啟發(fā)式算法

李有浩,趙承業(yè),董合德

(中國計(jì)量大學(xué) 理學(xué)院,浙江 杭州 310018)

圖的支配問題在圖的相關(guān)研究中一直是一個(gè)很熱門的分支,因?yàn)槠渚哂泻芏嗟淖冃魏蛯?shí)際的相關(guān)應(yīng)用,從理論到算法[1-2],各種論點(diǎn)層出不窮.而連通支配集[3]就是圖支配的一個(gè)重要分支問題.定義集合C?V(G),G(C)是集合C在圖G=(V,E)中的生成子圖,N(v)表示頂點(diǎn)v所有鄰居節(jié)點(diǎn),N[v]=N(v)∪{v}如果滿足1)|N[v]∩C|≥1,?v∈V(G),2)G(C)是連通的,那么就稱集合C是圖G的連通支配集.相關(guān)的研究也有很多,如文獻(xiàn)[4,5].

誤報(bào)容錯(cuò)支配集是圖的支配問題的一個(gè)新的有趣的延伸[6-10],從容錯(cuò)的角度來看,其實(shí)是介于圖的2-tuple支配和3-tuple支配之間的一個(gè)圖的支配問題.這個(gè)問題最早是由Slater在2009年提出的[7],其實(shí)際意義可以對(duì)應(yīng)社交網(wǎng)絡(luò)中如下的一種情況.

我們對(duì)于一般的社交網(wǎng)絡(luò)可以用圖G=(V,E)來表示,圖G中的每一個(gè)點(diǎn)代表一個(gè)社交個(gè)體,如果兩個(gè)個(gè)體之間可以相互交換信息的話,那么就給這兩個(gè)個(gè)體所對(duì)應(yīng)的圖G中的點(diǎn)連上一條邊.這里假設(shè)圖G中的每一個(gè)點(diǎn)都可能是一個(gè)入侵節(jié)點(diǎn),例如一個(gè)著火點(diǎn)或是一個(gè)破壞者等等.假設(shè)存在這樣的入侵者點(diǎn)v′.網(wǎng)絡(luò)中還存在具有保護(hù)裝置的點(diǎn),它可以檢測(cè)出其鄰居節(jié)點(diǎn)是否是入侵節(jié)點(diǎn),并且匯報(bào)這一入侵點(diǎn)的位置.要求盡可能布置最少的保護(hù)節(jié)點(diǎn),而且還能準(zhǔn)確找到網(wǎng)絡(luò)中的入侵節(jié)點(diǎn).這在網(wǎng)絡(luò)的拓?fù)鋱D中,相當(dāng)于找到最小的滿足條件的支配集D,在D中所有的點(diǎn)布置保護(hù)裝置.然而這樣的保護(hù)裝置可能會(huì)損壞而不會(huì)匯報(bào)信息,為了使其能繼續(xù)準(zhǔn)確找到入侵點(diǎn),這樣的支配集D必須是雙支配集.此外,這樣的保護(hù)裝置可能會(huì)匯報(bào)假的信息,這個(gè)時(shí)候即使D是雙支配集也可能不能準(zhǔn)確的找到入侵的節(jié)點(diǎn).為了解決這一問題,Slater提出了誤報(bào)容錯(cuò)支配集這一概念,并且證明下面的引理[7].

引理1:集合L是圖G的一個(gè)誤報(bào)容錯(cuò)支配集當(dāng)且僅當(dāng):

1)集合L是圖的一個(gè)雙支配集;

2)對(duì)于圖G中的任意一對(duì)節(jié)點(diǎn)u,v,都有|(N[u]∪N[v])∩L|≥3.

1　連通誤報(bào)容錯(cuò)支配集問題精確算法

連通的誤報(bào)容錯(cuò)支配集問題已經(jīng)被證明是屬于NP-完全問題[9],即很難找到這種問題的多項(xiàng)式時(shí)間的算法.這節(jié)給出一般圖上構(gòu)造最小連通誤報(bào)容錯(cuò)支配集的精確算法,算法的思想就是根據(jù)連通誤報(bào)容錯(cuò)支配集的定義,對(duì)所有的點(diǎn)進(jìn)行遍歷判斷.

對(duì)于一般的連通圖(頂點(diǎn)數(shù)超過3)G=(V,E),頂點(diǎn)數(shù)為n,算法是從尋找其最小的雙支配集開始.

1)利用整數(shù)規(guī)劃求得圖G的最小雙支配集的頂點(diǎn)數(shù)s.

2)求得所有從n個(gè)點(diǎn)中選取s個(gè)點(diǎn)的組合集D.

3)遍歷D中所有的集合L,判斷集合L是否滿足雙支配、點(diǎn)對(duì)三支配、子圖連通的條件,如果都滿足跳出循環(huán),輸出集合L.

4)如果遍歷完D中所有的集合都不能滿足其是連通誤報(bào)容錯(cuò)支配集的三個(gè)條件,則令s=s+1,并轉(zhuǎn)到步驟2繼續(xù)循環(huán).

由于這里用到的是遍歷判斷的思想,對(duì)于每一個(gè)點(diǎn)的情況,其可能屬于支配集,也可能不屬于支配集,所以算法的復(fù)雜度為O(2n).

2　連通誤報(bào)容錯(cuò)支配集問題的啟發(fā)式算法構(gòu)造

這節(jié)提出了構(gòu)造一般連通圖上的連通誤報(bào)容錯(cuò)支配集的一種基于貪婪策略的多項(xiàng)式時(shí)間啟發(fā)式算法.

2.1　問題描述及符號(hào)表示

問題描述:設(shè)圖G=(V,E),n=|V|為圖的節(jié)點(diǎn)數(shù).找到圖G的一個(gè)集合L,保證其圖G的連通誤報(bào)容錯(cuò)支配集的前提下,使L的節(jié)點(diǎn)數(shù)盡可能的少.

符號(hào)說明:在算法執(zhí)行過程中,節(jié)點(diǎn)和節(jié)點(diǎn)對(duì)的狀態(tài)都可能發(fā)生變化.節(jié)點(diǎn)可能出現(xiàn)未定義,1-被支配,2-被支配,支配這4種狀態(tài);節(jié)點(diǎn)對(duì)可能出現(xiàn)未定義,1-被支配,2-被支配,3-被支配這4種狀態(tài).假定在算法初始階段,所有節(jié)點(diǎn)和節(jié)點(diǎn)對(duì)狀態(tài)均為未定義.設(shè)當(dāng)前操作節(jié)點(diǎn)為v,定義關(guān)于節(jié)點(diǎn)v的下列符號(hào):

L0:節(jié)點(diǎn)狀態(tài)為未定義的節(jié)點(diǎn)集合.初始時(shí),L0=V.

L1:節(jié)點(diǎn)狀態(tài)為支配的節(jié)點(diǎn)集合.初始時(shí),L1=?.

L2:算法執(zhí)行過程中當(dāng)前的節(jié)點(diǎn)狀態(tài)為1-被支配,2-被支配的節(jié)點(diǎn)集合,其也是可能成為支配點(diǎn)的集合.初始時(shí),L2=?.

d0(v):N[v]中狀態(tài)為未定義的節(jié)點(diǎn)個(gè)數(shù).

d1(v):N[v]中狀態(tài)為1-被支配的節(jié)點(diǎn)個(gè)數(shù).

d2(v):N[v]中狀態(tài)為2-被支配的節(jié)點(diǎn)個(gè)數(shù).

P0:狀態(tài)為未定義的節(jié)點(diǎn)對(duì)集合.

P1:算法執(zhí)行過程中當(dāng)前節(jié)點(diǎn)對(duì)狀態(tài)為1-被支配或2-被支配的節(jié)點(diǎn)對(duì)集合.初始時(shí),P1=?.

P2:狀態(tài)為3-被支配的節(jié)點(diǎn)對(duì)集合.初始時(shí),P2=?.

d0(pv):節(jié)點(diǎn)v閉領(lǐng)域內(nèi)的節(jié)點(diǎn)對(duì)中狀態(tài)為未定義的節(jié)點(diǎn)對(duì)數(shù).

d1(pv):節(jié)點(diǎn)v閉領(lǐng)域內(nèi)的節(jié)點(diǎn)對(duì)中狀態(tài)為1-被支配或2-被支配的節(jié)點(diǎn)對(duì)對(duì)數(shù).

規(guī)則描述:在算法執(zhí)行過程中,狀態(tài)為支配的節(jié)點(diǎn)的閉鄰域內(nèi)的節(jié)點(diǎn)狀態(tài)也會(huì)發(fā)生變化,同時(shí)需要選擇新的支配節(jié)點(diǎn),直到滿足條件,具體規(guī)則如下:

規(guī)則Ⅰ設(shè)節(jié)點(diǎn)v為支配節(jié)點(diǎn),則任意一非支配節(jié)點(diǎn)u∈N[v]的狀態(tài)變化如下:

1)若節(jié)點(diǎn)u的當(dāng)前狀態(tài)為未定義,則其狀態(tài)變?yōu)?-被支配;

2)若節(jié)點(diǎn)u的當(dāng)前狀態(tài)為1-被支配,則其狀態(tài)變?yōu)?-被支配.

規(guī)則Ⅱ設(shè)節(jié)點(diǎn)v為當(dāng)前支配節(jié)點(diǎn),選擇新的支配節(jié)點(diǎn)的規(guī)則如下:

1)找出L2中d0(u)最大值所對(duì)應(yīng)的節(jié)點(diǎn)u,若節(jié)點(diǎn)u唯一,則將該節(jié)點(diǎn)作為新的支配節(jié)點(diǎn),否則把這些節(jié)點(diǎn)放入一個(gè)集合里,記為D0(v),轉(zhuǎn)入2);

2)找出D0(v)中d1(u)最大值所對(duì)應(yīng)的節(jié)點(diǎn)u,若節(jié)點(diǎn)u唯一,則將該節(jié)點(diǎn)作為新的支配節(jié)點(diǎn),否則把這些節(jié)點(diǎn)放入一個(gè)集合里,記為D1(v),轉(zhuǎn)入3);

3)找出D1(v)中d2(u)最大值所對(duì)應(yīng)的節(jié)點(diǎn)u,若節(jié)點(diǎn)u唯一,則將該節(jié)點(diǎn)作為新的支配節(jié)點(diǎn),否則取這些節(jié)點(diǎn)中序號(hào)較小者作為新的支配點(diǎn).

規(guī)則Ⅲ若所有節(jié)點(diǎn)均為2-支配,部分節(jié)點(diǎn)對(duì)未滿足3-支配,選擇新的支配節(jié)點(diǎn)規(guī)則如下:

1)找出L2中d0(pu)最大值所對(duì)應(yīng)的節(jié)點(diǎn)u,若節(jié)點(diǎn)u唯一,則將該節(jié)點(diǎn)作為新的支配節(jié)點(diǎn),否則把這d1(pu)些節(jié)點(diǎn)放入一個(gè)集合里,記為P0(v),轉(zhuǎn)入2);

2)找出P0(v)中最大值所對(duì)應(yīng)的節(jié)點(diǎn)u,若節(jié)點(diǎn)u唯一,則將該節(jié)點(diǎn)作為新的支配節(jié)點(diǎn),否則取這些節(jié)點(diǎn)中序號(hào)較小者作為新的支配點(diǎn).

2.2　算法構(gòu)造

這節(jié)給出的連通誤報(bào)支配集的啟發(fā)式算法的主要思想是:首先使圖中的任意節(jié)點(diǎn)的狀態(tài)變化為2-被支配,繼續(xù)添加新的支配點(diǎn)使圖中所有的節(jié)點(diǎn)對(duì)狀態(tài)變?yōu)?-被支配.其中第一步是基于最小生成樹的思想,對(duì)圖G設(shè)置集合S來放置支配節(jié)點(diǎn),集合V-S中與集合S鄰接且度數(shù)相對(duì)較大的節(jié)點(diǎn)優(yōu)先考慮最為支配點(diǎn).不斷的重復(fù)這樣的操作,直到所有的節(jié)點(diǎn)狀態(tài)都是2-被支配或支配節(jié)點(diǎn)狀態(tài);第二步從所有的節(jié)點(diǎn)中,以為滿足3-被支配的節(jié)點(diǎn)對(duì)數(shù)目最大作為貪心選擇標(biāo)準(zhǔn)來選擇新的支配點(diǎn)加入到集合S中,直到所有的節(jié)點(diǎn)對(duì)狀態(tài)都為3-被支配.下面是相關(guān)的算法描述.

步驟1構(gòu)造節(jié)點(diǎn)2-支配集

1)在圖G中選擇節(jié)點(diǎn)度最大的節(jié)點(diǎn)(若度最大節(jié)點(diǎn)不唯一,則選擇序號(hào)最小的節(jié)點(diǎn))作為初始支配節(jié)點(diǎn)v0,把節(jié)點(diǎn)v0從集合L0中取出,放入集合L1中,按照規(guī)則Ⅰ改變N[v0]的節(jié)點(diǎn)狀態(tài).并且更新集合L0,L2,將狀態(tài)為1-被支配的節(jié)點(diǎn)從集合L0中取出,放入集合L2中.

2)在集合L2中的所有節(jié)點(diǎn),按照規(guī)則Ⅱ選擇新的支配點(diǎn),并作為當(dāng)前操作節(jié)點(diǎn)v,按照規(guī)則Ⅰ改變N[v]中所有非支配節(jié)點(diǎn)的狀態(tài).更新集合L0,L1,L2,即將節(jié)點(diǎn)v從L2取出,放入到集合L1中;將狀態(tài)為1-被支配的節(jié)點(diǎn)從L0中取出,放入到集合L2中.

3)若圖G中非支配的節(jié)點(diǎn)均為2-被支配,則算法結(jié)束,否則轉(zhuǎn)2)繼續(xù)執(zhí)行.

步驟2構(gòu)造節(jié)點(diǎn)對(duì)3-支配集

1)根據(jù)當(dāng)前圖G中的節(jié)點(diǎn)對(duì)的狀態(tài),更新集合P0,P1,P2.

2)在集合L2中的所有節(jié)點(diǎn),按照規(guī)則Ⅲ選擇新的支配點(diǎn),并作為當(dāng)前操作的節(jié)點(diǎn)v,將該節(jié)點(diǎn)v從L2L2中取出,放入集合L1中.

3)若圖G中的節(jié)點(diǎn)對(duì)狀態(tài)均為3-被支配,則算法結(jié)束,否則,更新集合P0,P1,P2,轉(zhuǎn)2)繼續(xù)執(zhí)行.

定理1:根據(jù)規(guī)則Ⅰ、Ⅱ、Ⅲ經(jīng)過構(gòu)造節(jié)點(diǎn)2-支配集和節(jié)點(diǎn)對(duì)3-支配集得到的集合L1就是圖G的一個(gè)連通誤報(bào)容錯(cuò)支配集.

證明:首先證明集合的連通性.在構(gòu)造2-支配集時(shí),除了初始節(jié)點(diǎn),新的支配節(jié)點(diǎn)都是從L2中選取,即被支配的節(jié)點(diǎn)集合.保證新的支配節(jié)點(diǎn)總是與L1中至少一個(gè)節(jié)點(diǎn)相連接,因此最后得到的2-支配集就是連通的集合.同樣在構(gòu)造3-支配集時(shí),新的支配點(diǎn)也是從L2中選出,因而得到的節(jié)點(diǎn)對(duì)3-支配集即最后得到的集合L1是連通的;其次證明集合L12-支配圖G中所有的節(jié)點(diǎn),即|N[v]∩L1|≥2,?v∈V(G).在步驟1執(zhí)行后得到的集合L1,其2-支配圖G中所有的非支配集節(jié)點(diǎn),而對(duì)于L1中的節(jié)點(diǎn),由于連通性的保證,所以有|N[v]∩L1|≥2,?v∈L1.最后證明集合L13-支配圖G中的所有節(jié)點(diǎn)對(duì),即|(N[u]∪N[v])∩L|≥3,?u,v∈V(G)(u≠v).由算法步驟2最后的終止條件可以知道最后得到的L1一定3-支配所有的節(jié)點(diǎn)對(duì);否則算法一直進(jìn)行下去,因而圖中所有的節(jié)點(diǎn)對(duì)的狀態(tài)最后都是3-被支配.

綜上2.2所提出的算法最后得到的就是圖G的一個(gè)連通誤報(bào)容錯(cuò)支配集.

3　算法分析及實(shí)現(xiàn)

算法的步驟1形成2-支配的節(jié)點(diǎn)集合,按規(guī)則Ⅰ更新支配節(jié)點(diǎn)鄰域內(nèi)鄰接節(jié)點(diǎn)狀態(tài)的時(shí)間復(fù)雜度為O(n),更新節(jié)點(diǎn)閉鄰域內(nèi)的節(jié)點(diǎn)狀態(tài)的時(shí)間復(fù)雜度為O(n2);按規(guī)則Ⅱ選取的新的節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n),則構(gòu)造2-被支配的節(jié)點(diǎn)結(jié)合的時(shí)間復(fù)雜度為O(n3).算法步驟2形成節(jié)點(diǎn)對(duì)3-被支配集,更新各節(jié)點(diǎn)閉鄰域的節(jié)點(diǎn)對(duì)數(shù)的時(shí)間復(fù)雜度為O(n2);按規(guī)則Ⅲ選取新的支配節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n),則構(gòu)造節(jié)點(diǎn)對(duì)3-支配集的時(shí)間復(fù)雜度O(n3).綜上,2.2提出的啟發(fā)式算法的時(shí)間復(fù)雜度為O(n3).

對(duì)本文提出的基于貪婪策略的連通誤報(bào)容錯(cuò)支配集啟發(fā)式算法進(jìn)行仿真實(shí)驗(yàn),測(cè)試所用的無線傳感器網(wǎng)絡(luò)隨機(jī)圖通過如下方式產(chǎn)生:在500×500的平面內(nèi),隨機(jī)產(chǎn)生n個(gè)節(jié)點(diǎn),假設(shè)這樣的無線傳感器網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的通信半徑是相同的,記為R,如果兩個(gè)節(jié)點(diǎn)的距離不大于R,則認(rèn)為這兩個(gè)節(jié)點(diǎn)是有邊連接的.如果構(gòu)造得到的圖不是連通的,那就重新構(gòu)造,直到構(gòu)造的圖連通為止.現(xiàn)在以節(jié)點(diǎn)數(shù)n為150,節(jié)點(diǎn)之間的通信半徑80為例,用圖來說明構(gòu)造的連通誤報(bào)容錯(cuò)支配集的過程.(如圖1)圖中用藍(lán)色節(jié)點(diǎn)表示被支配節(jié)點(diǎn),紅色節(jié)點(diǎn)表示形成節(jié)點(diǎn)2支配產(chǎn)生的支配節(jié)點(diǎn),用黑色節(jié)點(diǎn)表示形成節(jié)點(diǎn)對(duì)3-支配集產(chǎn)生的支配節(jié)點(diǎn).從圖中可知,所得到就是圖G的一個(gè)連通誤報(bào)容錯(cuò)支配集.

圖1　連通誤報(bào)容錯(cuò)支配集構(gòu)造Figure 1　Construction of connected liar’s dominating set

為體現(xiàn)文中提出的啟發(fā)式算法的計(jì)算效率和最終得到連通誤報(bào)容錯(cuò)支配集和最優(yōu)值之間的誤差大小,我們對(duì)精確算法和啟發(fā)式算法進(jìn)行了仿真(表1),仿真的圖也是基于計(jì)算機(jī)隨機(jī)生成的連通圖,圖的生成算法以及具體結(jié)果如下.

實(shí)驗(yàn)所用圖的生成算法:

1)在500×500的平面內(nèi),隨機(jī)生成n個(gè)頂點(diǎn).

2)兩個(gè)節(jié)點(diǎn)之間的距離小于100,就連接兩個(gè)節(jié)點(diǎn).

3)用深度優(yōu)先搜索判斷生成的圖是否連通,連通則輸出該圖,否則跳到步1)精確算法和啟發(fā)式算法對(duì)應(yīng)的結(jié)果如下.

表1　啟發(fā)式算法的相關(guān)實(shí)驗(yàn)結(jié)果

表2　精確算法的相關(guān)實(shí)驗(yàn)結(jié)果

從表2中可知,由于精確算法的復(fù)雜度比較高,因此我們可以得到精確解的網(wǎng)絡(luò)規(guī)模大小比較有限.通過表1和表2比較,我們可以看到啟發(fā)式算法在計(jì)算時(shí)間和網(wǎng)絡(luò)規(guī)模上具有很大的優(yōu)勢(shì),其結(jié)果和精確解比較差距較小.

仿真實(shí)驗(yàn)所用計(jì)算平臺(tái):CPU酷睿i5-7200u,內(nèi)存8 G,硬盤SSD 256G.

4　總結(jié)與展望

本文先是提出了一個(gè)連通誤報(bào)容錯(cuò)支配集問題的精確算法,并證明了其計(jì)算復(fù)雜度是指數(shù)型.隨后給出了該問題的一個(gè)時(shí)間復(fù)雜度為O(n3)的啟發(fā)式算法,最后通過計(jì)算機(jī)模擬實(shí)現(xiàn)兩個(gè)算法,并從運(yùn)行時(shí)間和準(zhǔn)確度上比較兩個(gè)算法.文中給出的算法屬于集中式的算法,此外可以考慮分布式算法,對(duì)于局部的信息進(jìn)行支配集構(gòu)造,最后合并處理,這樣計(jì)算的時(shí)間復(fù)雜度應(yīng)該能降低.