基于核心化技術的點覆蓋改進算法

駱偉忠，蔡昭權

(惠州學院信息科學技術學院,廣東 惠州 516007)

1 引言

點覆蓋是Karp的21個NP完全問題之一，除非P=NP，否則無法在多項式時間內求解問題的最優解[1]。點覆蓋在社交和通信網絡、生物信息學、超大規模集成電路等領域具有越來越重要的應用[2,3]。

近來，人們從參數計算角度研究點覆蓋的最優化求解。Buss等人[10]首次提出時間復雜度為O(kn+2kk2k+2)的參數精確算法，其中k為問題解的大小。隨后，Balasubramanian等人[11]將底數降低到2以下，給出一個時間為O(kn+1.32kk2)的參數算法。目前，針對該問題的最好結果是Chen等人[12]基于分支限界技術提出的時間復雜度為O(1.27k+kn)的算法。文獻[13]研究點覆蓋在保證值以上的參數復雜性和參數算法設計。

針對點覆蓋的參數算法研究和啟發算法研究是兩條獨立線路，現有研究都沒有綜合兩者進行算法設計或優化。本文提出結合核心化操作和啟發式操作的算法框架，利用參數計算中的核心化技術進行點覆蓋的啟發式算法優化。啟發或近似算法基于貪婪或隨機策略，無法實現全局最優；而核心化操作對問題實例“難處理部分”無能為力。利用核心化技術，通過深入分析圖中頂點間的組合特性，挖掘出圖中必定屬于全局最優點覆蓋的頂點集。在原有啟發算法貪婪選擇頂點前執行核心化過程，將屬于全局最優的點集放入解中，從而提高解的精度。另一方面，啟發式操作進行了頂點或邊的刪除，改變了問題實例的原有結構，為下一輪的核心化操作提供可能。在隨機拓撲網絡和真實生物網絡上的測試表明，新算法在各種不同網絡實例中對原有算法進行了不同程度的優化。特別是在稀疏網絡中，新算法在大部分網絡實例中得到了最優解，且運行時間與原有算法相當。

2 預備知識

設G(V,E)為一個無向、簡單的連通圖，其中V是G的頂點集，E是G的邊集。對于u,v∈V,如果u與v相鄰，則用(u,v)表示u、v之間的邊。設v∈V，e=(u,v)∈E，Gv表示從圖G中刪除v以及依附于v的邊，Ge表示從圖G中刪除u、v以及依附于u、v的邊。設U?V,則G[U]表示U在圖G上的導出子圖。設e=(u,v)∈E，則頂點v(或u)能覆蓋邊e。

定義1(點覆蓋給定圖G(V,E)) 設C?V,如果對于圖G上的任何一條邊e∈E，存在頂點v∈C，使得v能覆蓋e,則稱C為圖G的點覆蓋。

設C?V為圖的某個點覆蓋,如果圖G的任何點覆蓋C′?V，滿足|C′|≥|C|，則稱C為圖G的最小點覆蓋。

3 現有算法分析

點覆蓋是NP難解問題，人們普遍認為需要指數時間求解該問題的最優解。但是，指數時間在實際中不可用，人們主要從啟發式算法或近似算法的角度在多項式時間內求解該問題的非最優解。

針對點覆蓋，最為著名的算法為Nixon提出的近似率為logn的算法和Fanica提出的近似率為2的算法[6,14]。Nixon提出的算法的基本思想是重復選取當前圖G中度最大的頂點v放入解中，并從圖G中刪除v以及依附于v的邊，如算法1所示(為便于描述，將Nixon提出的近似率為logn的算法命名為AppV，而Fanica提出的近似率為2的算法命名為AppE)。

另一近似算法的基本思想是不斷選取當前圖G中任意一條邊e=(u,v)，將u和v放入解中，并從G中刪除u、v以及依附于u、v的邊。

通過分析以上兩個算法可發現，啟發式或近似算法的本質是通過犧牲解的精確性來換取時間效率。因此，其主要缺陷是其解題步驟是一種“啟發式操作”，通常能實現局部最優，但無法實現全局最優。

核心化是多項式時間處理NP難解問題的一種新技術。該技術對問題實例中“易處理部分”進行處理，識別出屬于全局最優解的元素。問題實例經過核心化處理后，得到“難處理部分”。除非打破“難處理部分”的結構，否則核心化過程無法繼續進行。

算法1AppV算法

輸入：G(V,E)。

輸出：V的子集D。

1D=?；

2 WhileE≠? do{

2.1 選取G中度最大的頂點v;

2.2D=D∪{v}；

2.3G=Gv;}

3 ReturnD;

啟發式操作和核心化操作是多項式時間處理NP難解問題的有效方法。但是，啟發式操作無法實現全局最優，而核心化操作對問題實例“難處理部分”無能為力。

4 改進算法

新算法融合啟發式操作和核心化操作，兩者重復輪流執行，如圖1所示。首先進行核心化操作，對問題實例中“易處理部分”進行處理，將屬于最小點覆蓋的點集放入解中，并刪除某些不屬于最小點覆蓋的頂點。經過核心化處理后，問題實例僅剩下“難處理部分”。接著執行啟發式操作，貪婪選擇實例中頂點放入解中。啟發式操作打破了實例的原有結構，為下一輪的核心化操作提供可能。重復以上過程，直到問題實例中不存在邊，完成問題求解。

Figure 1 Algorithm framework 圖1 算法框架

核心化過程會將屬于最優點覆蓋的頂點集加入解中，實現全局最優，從而提高解的精確性。該算法框架可以對點覆蓋現有的任何啟發式或近似算法進行優化。這里以近似算法AppV為例說明具體的優化過程。

4.1 核心化操作

首先給出針對圖中度為0、1或2的規約規則。

規則1設v∈V為圖G上一個度為0的頂點,則從G中刪除v。

度為0的孤立點，不能覆蓋任何邊，因此可以直接刪除。

規則2設v∈V為圖G上一個度為1的頂點，w∈V為v的鄰接點,將w放入解D中，并從G中刪除v和w。

v和w中至少有一個頂點在解中。同時，注意到頂點w的度至少為1，其覆蓋的邊數不會少于v覆蓋的邊數，因此優先將w放入解中。

規則3[12]設v∈V為圖G上一個度為2的頂點，w1,w2∈V為v的兩個鄰接點，且w1和w2相鄰，則將w1和w2放入解D中，并從G中刪除v、w1和w2。

v、w1和w2中至少有兩個頂點在解中，w1和w2組合的覆蓋能力比其它大小為2的頂點組合覆蓋能力強，因此優先將w1和w2放入解中。

規則4[12]設v∈V為圖G上一個度為2的頂點，w1,w2∈V為v的兩個鄰接點，且w1和w2不相鄰，則對w1或w2的所有鄰接點w(w≠v)，將邊(v,w)加入G中，并將w1和w2從G中刪除。

對于G上的最優點覆蓋D，D如果包含v，則不包含w1和w2；如果不包含v，則一定包含w1和w2。規則4不能確定是v，還是w1和w2在最優解中。因此，該規則執行后需保存v、w1和w2信息以構造問題輸入實例上的解。

接下來給出基于線性規劃的規約規則。

點覆蓋可以表示為一個線性規劃問題[15]。假設給定的圖為G(V,E),對于圖G的每一個頂點v∈V，構造變量xv，xv的取值為0≤xv≤1，點覆蓋可以轉變為以下線性規劃問題：

最小化：∑v∈Vxv。

約束：對于每條邊(u,v)∈E,滿足xu+xv≥1;對于每個與頂點v對應的變量xv，滿足0≤xv≤1。

求解以上線性規劃，可將V中頂點劃分為三部分：

C0={v∈V|xv>0.5};

V0={v∈V|xv=0.5};

I0={v∈V|xv<0.5}。

引理1[15]給定點覆蓋實例G(V,E),設C0、V0、I0為按以上方式求解得出的頂點子集,則G上存在最小點覆蓋S，使得C0?S,S∩I0=?。

引理1表明，存在某個最小點覆蓋包含C0中的所有點，同時不包含I0中的任何點。

基于引理1，得出核心化的下一條規則。

規則5設C0、V0、I0為按以上方式求解得出的頂點子集,將C0放入解D中；并將I0與C0從G中刪除，即G=G[V0]。

規則5將線性規劃得到的點集C0放入解中，并從G中刪除C0∪I0以及依附于其上的邊。問題規模降低為G[V0]。

接下來證明V0的規模與G[V0]最小點覆蓋大小之間的關系。

□

由規則1～規則5得出針對點覆蓋的核心化過程Kernel，如算法2所示。

算法2Kernel (G(V,E),D)算法

1 WhileE≠? Do{

1.1 WhileE≠? Do{

1.1.1 執行規則1；

1.1.2 執行規則2；

1.1.3 執行規則3；

1.1.4 執行規則4；

1.1.5 如果規則1～規則4均沒有被成功執行，則退出當前循環；}

1.2 執行規則5}

2 Return

步驟1.1.1～步驟1.1.4均會在圖G中尋找滿足規則執行條件的局部結構，若存在則執行規則并進入下一步驟。某規則沒有被成功執行，表示當前圖中不存在滿足該規則執行條件的局部結構。規則5因為要執行線性規劃，是所有規則中最費時的，所以放到最后執行。只有當執行時間較快的規則1～規則4均不能被成功執行時，才會執行規則5。

4.2 基于核心化的算法

基于核心化操作，提出改進的算法Kernel_AppV，如算法3所示。Kernel_AppV在貪婪選擇頂點前進行核心化操作。

算法3Kernel_AppV算法

輸入：G(V,E)。

輸出：V的子集D。

1D=?；

2 WhileE≠? do{

2.1Kernel(G,D);

2.2 選取G中度最大的頂點v;

2.3D=D∪{v}；

2.4G=Gv;}

3 根據D構造輸入實例上的解D′;

4 ReturnD′

核心化操作將屬于全局最優解的點集放入解中，提高了解的精度。同時，核心化操作會將實例中不屬于最優解的點集刪除，降低實例規模，并保證核心化后結果圖中超過一半的頂點屬于最優解，這提高了后續貪婪選擇的頂點屬于最優解的概率。另一方面，核心化后續的貪婪操作會改變圖的結構，使得圖結構滿足核心化的執行條件，從而使下一輪的核心化操作能繼續進行。核心化操作和貪婪操作是一對相互促進的操作。

步驟3根據D以及規則4執行時保存的頂點信息，來構造問題輸入實例上的解：如果D包含規則4中保存的頂點v，則用w1和w2替換v；如果不包含v，則加入v。

核心化操作并不會降低原有算法的近似率，接下來給出理論上的證明。

定理2算法Kernel_AppV的近似率為2。

□

定理2表明，在原有近似算法中加入核心化操作，不會使算法的近似率變差。原算法AppV的近似率為logn，加入核心化操作后改進到2。

5 仿真實驗

為了測試新算法Kernel_AppV的有效性，通過仿真實驗將其與點覆蓋經典近似算法AppV進行比較。算法Kernel_AppV和AppV均為多項式時間的近似算法，無法對任何實例得到最優解。為了更好地進行測試，使用分支技術求解出問題實例的最優解作為比較標桿。使用的分支技術能得到問題任何實例的最優解，但需花費指數時間。實驗平臺配置為：Intel i3-3110M,主頻 2.40 GHz,4 GB內存。

實驗在隨機網絡和實際生物網絡中進行。生物網絡來源于DIP數據庫的蛋白質相互作用網絡[16]。隨機網絡的生成方法如下：給定代表網絡節點個數的n和網絡邊條數的m，首先產生一個節點個數為n的且不包含任何邊的網絡G；然后逐漸往網絡G中添加m條邊，對n個頂點從0到n-1進行編號。隨機產生兩個在0和n-1之間的代表頂點的不同數字v和w，如果邊(v,w)不在G中，則將其添加到G中；重復以上過程，直到G中邊的條數為m。通過設置n和m的大小來控制網絡的規模和稀疏度。

5.1 隨機網絡

核心化操作和啟發式操作是一對互補的操作，核心化操作提高了解的精度，而啟發式操作改變了網絡拓撲的原有結構，為下一輪的核心化操作提供可能。主要從以下三方面進行測試：核心化操作的優化效果、啟發式操作對核心化過程的促進和算法時間效率。

(1) 核心化操作對解精度的提高。

測試在不同規模和不同稀疏度的網絡上進行。表1～表3展示的是網絡規模n為30，網絡中邊數m分別為50、100、300的結果。每組測試中生成500個隨機實例。求解最優解的時間復雜度隨網絡規模n指數增長。因此，考慮到時間效率，將n設置為30。表中行表示算法的名稱，列表示差值，即算法求解得到的解的大小與最優解大小的差值。

表1中邊m為50，代表的是稀疏網絡。算法Kernel_AppV在500個實例中得到的解均為最優解；算法AppV在240個實例中取得了最優解，大部分實例中求得的解比最優解大1或2，最差情況下比最優解大3。

Table 1 Optimization in sparse networks (n=30,m=50)

表2中邊m為100，代表的是中等稠密網絡，算法Kernel_AppV性能有所下降，在451個實例中取得了最優解。

Table 2 Optimization in moderatelydense networks (n=30,m=100)

表3中邊m為300，代表的是稠密網絡，算法Kernel_AppV和算法AppV的差距在縮小，算法Kernel_AppV取得最優解的實例降低到391；而算法AppV取得最優解的實例上升到309。

Table 3 Optimization in dense networks (n=30,m=300)

表1～表3的結果表明，算法Kernel_AppV的性能與網絡稀疏度相關。圖2的結果進一步展示了稀疏度對算法優化的影響。將網絡規模n設為30個頂點，邊數m從30逐步增加到330(步長為20)。當邊數逐步增加時，網絡的密度也逐步增加。對于特定的n和m，生成100個不同的測試實例。圖2中的橫坐標表示邊數，縱坐標表示在100個實例中，算法Kernel_AppV取得的解比算法AppV取得的解要嚴格小的實例個數。從圖2的整體趨勢來看，算法Kernel_AppV在稀疏網絡上對算法AppV的優化效果較好。隨著網絡稀疏度的增加，算法Kernel_AppV對算法AppV的優化次數下降。其主要原因是核心化操作中的規約規則主要針對的是網絡中的低度頂點。當網絡較稀疏時，低度點較多，解中的頂點大多數來自核心化操作。

Figure 2 Impact of network density on optimization performance 圖2 網絡稠密度對優化性能的影響

圖3為網絡規模增加后，Kernel_AppV和AppV兩個算法的性能對比。網絡規模n設為500個頂點，邊數m設為1 000。隨機生成50個實例進行測試。從圖3可看出，在50個實例中，算法Kernel_AppV得到的解大小均比算法AppV得到的解要小，表明Kernel_AppV在網絡規模較大時，仍能取得較好的優化效果。

Figure 3 Optimization in relatively large scale networks圖3 較大規模網絡上的優化

(2)啟發式操作對核心化過程的促進。

啟發式操作會改變網絡拓撲的結構，為下一輪的核心化操作提供可能。表4展示啟發式操作的執行情況。當n=100，m=100時，該網絡實例是稀疏結構，核心化操作單獨完成整個解的求解。但是，當網絡的邊增加到200時，網絡稠密度增加，核心化操作不能完成整個解的求解。有三次核心化操作無法繼續執行，這時啟發式操作將相關頂點放入解中并將該頂點刪除，改變了網絡的結構，從而使得核心化操作能夠繼續執行。當m=300和m=500時，網絡稠密度進一步增加，啟發式操作參與的次數也隨之增加。

Table 4 Execution of heuristic operation

(3) 時間代價。

算法Kernel_AppV相比算法AppV取得了較好的優化效果，但其付出的主要代價是算法運行時間增加了。在500個頂點、500條邊的隨機網絡上，算法Kernel_AppV和算法AppV的運行時間分別為125 ms和78 ms。兩者運行時間相當，這是因為，此時該網絡是稀疏結構，核心化操作中的規則1～規則4幾乎完成整個解的求解，而耗時的規則5的執行次數很少。注意到規則1～規則4的執行時間與啟發式操作執行時間相當。保持網絡規模500不變，而邊增加到1 000，算法AppV的運行時間增加到94 ms，而算法Kernel_AppV的運行時間急劇增加到15 978 ms。這是因為，當邊增加時，網絡稠密度增加，耗時的線性規劃的執行次數也相應增加。

從以上分析可以發現，算法Kernel_AppV通過增加算法運行時間獲得了解的優化。點覆蓋是一個NP難解問題。最優化求解該問題，人們普遍認為不能在多項式時間內完成。現有實現點覆蓋最優化求解的算法均付出了指數時間代價，一般情況下，指數時間是實際不可解的。算法Kernel_AppV在幾乎所有稀疏網絡實例上都獲得了最優解，其代價是在原有多項式時間的啟發式算法AppV上增加了多項式時間。使用傳統方法需要付出指數時間的代價，而算法Kernel_AppV僅付出多項式時間代價。因此，算法Kernel_AppV以較低的時間代價獲得了較好的解優化效果。

5.2 生物網絡

使用DIP數據庫20101010的酵母相互作用網絡數據。去除網絡中的自相互作用和重復相互作用后，網絡中包含5 093個蛋白質和24 743對相互作用。該網絡可抽象為一個無向圖：每個蛋白質抽象為一個頂點，如果兩個蛋白質間存在相互作用，則對應的兩個頂點間添加邊。

算法Kernel_AppV求解得到的解大小為2 109個頂點，而算法AppV求解得到的解大小為2 153個頂點。算法Kernel_AppV中由核心化操作得到的頂點個數為2 094，啟發式操作得到的頂點個數為15。注意到核心化操作求解得到的頂點均屬于某最優解，因此該解非常接近最優解。核心化操作能夠完成幾乎整個解的求解，主要原因是該生物網絡是稀疏結構，且網絡中存在大量的度為1和2的頂點，核心化操作能處理實例中絕大部分的頂點和邊。

算法Kernel_AppV的運行時間為8.7 s，而算法AppV的運行時間為51.8 s。算法Kernel_AppV的執行速度比算法AppV的執行速度更快，表明在某些大規模稀疏網絡中，算法Kernel_AppV的時間效率更高。

5.3 對其它算法的優化

采用與算法Kernel_AppV對算法AppV優化的類似過程，核心化操作可以對任何其它點覆蓋近似算法或啟發式算法進行優化。

圖4展示的是對Fanica提出的近似率為2的近似算法的優化。其中AppE為原算法，Kernel_AppE為引入核心化過程后的新算法。從圖4可發現，Kernel_AppE對AppE平均優化的個數為10左右。

Figure 4 Optimization for algorithm AppE圖4 對算法AppE的優化

6 結束語

針對啟發式或近似算法無法實現全局最優的不足，提出融合啟發式操作和核心化操作的點覆蓋通用算法優化框架。核心化操作和啟發式操作循環交叉執行，核心化操作挖掘全局最優的頂點集，啟發式操作改變網絡拓撲結構，使得下一輪核心化能夠繼續，兩者共同作用實現點覆蓋求解的優化。實驗表明，本文提出的新算法在隨機網絡和生物網絡等各種不同的網絡實例中均能實現優化。特別是在稀疏網絡中，該算法運行時間與原有算法相當，在大部分實例中能得到最優解。下一步研究可考慮提出針對高度頂點的規約規則，對稠密網絡進一步優化。另一方面，可將提出的算法優化框架應用于其它難解問題求解的優化。