最大團(tuán)問題的競爭決策算法

黃 飛，寧愛兵，劉志民，何永梅，張惠珍

（上海理工大學(xué) 管理學(xué)院，上海 200093）

最大團(tuán)問題（MCP）[1-3]是組合優(yōu)化中的NP 難題（non-deterministic polynomial problems），在實(shí)踐中有著廣泛的應(yīng)用，如社會網(wǎng)絡(luò)分析[4]、生物信息學(xué)[5]、分子生物學(xué)、編碼理論[6]及經(jīng)濟(jì)學(xué)[7]等，是圖論、運(yùn)籌學(xué)及離散數(shù)學(xué)等領(lǐng)域中一個重要的研究目標(biāo)。

本文介紹、提出并論證了最大團(tuán)的部分?jǐn)?shù)學(xué)性質(zhì)，在此基礎(chǔ)上設(shè)計了一個求解該問題的競爭決策算法（CDA）。為了闡述算法的基本原理，本文給出了一個簡單的案例，運(yùn)用該算法進(jìn)行手動求解。最后運(yùn)用該算法對最大團(tuán)問題的標(biāo)準(zhǔn)測試圖進(jìn)行求解，計算實(shí)驗(yàn)得到了較好的結(jié)果。測試中有些情況下還可以得到目前最優(yōu)解，如后面的實(shí)例p_hat300-2，MANN_a27 和MANN_a45。

1 競爭決策算法

自從CDA 在文獻(xiàn)[8]中提出之后，該算法被應(yīng)用在了很多NP 問題的求解上，具體可參閱文獻(xiàn)[9-13]，且都得到了較好的結(jié)果。本文僅給出算法的原理與概念，算法的詳細(xì)情況可參閱文獻(xiàn)[9]。

1.1 原理

競爭決策現(xiàn)象普遍存在于大自然中，這些競爭決策都在一定的法則下進(jìn)行，且同時受到一種或多種因素的共同影響。競爭決策就是參與競爭的各方根據(jù)競爭決策機(jī)制分別占據(jù)一定的資源的過程。競爭決策之后，會達(dá)到一個新的均衡狀態(tài)。如果新形成的均衡狀態(tài)優(yōu)于初始狀態(tài)，則能實(shí)現(xiàn)優(yōu)化的目的。CDA 就是模擬這個機(jī)制來實(shí)現(xiàn)優(yōu)化。它首先根據(jù)求解的問題構(gòu)造出一個或多個競爭參與者，參與對資源的競爭，然后利用相應(yīng)的競爭機(jī)制，通過決策判定競爭者是否占有資源以及占有哪些資源，直至達(dá)到均衡狀態(tài)。

1.2 基本概念

a.競爭者：參與競爭資源的各方，在本文中，如果算法中只存在一個競爭者，則假設(shè)存在另一個虛構(gòu)的競爭者N（可以假定代表自然），同時參與爭奪資源。N 沒有競爭力函數(shù)。

b.資源：競爭者所爭奪的目標(biāo)，整個算法的核心。

c.競爭決策狀態(tài)：某一瞬間，所有參與競爭的各方各自所占有的資源的一種狀態(tài)。初始狀態(tài)下，參與競爭的各方均不占有資源，虛擬競爭者除外，且占有所有資源。

d. 競爭力函數(shù)：代表競爭者爭奪資源的能力。

e. 決策函數(shù)：決策函數(shù)起到判定的作用，用于判定資源的分配，分3 種情況。

（a）若除了虛擬競爭者之外只有一個競爭者，決策函數(shù)用于判定該競爭者能否從虛擬競爭者那里爭奪資源；

（b）若除了虛擬競爭者之外有多個競爭者，決策函數(shù)不僅要判定哪些競爭者可以優(yōu)先占有資源，還要判定這些競爭者具體可以占有哪些資源；

（c）決定是否要從某個競爭者手中強(qiáng)制性地剝奪出資源，并將資源分配給另外一個競爭者。

f. 競爭決策均衡狀態(tài)：完成資源的初步分配后所達(dá)到的一種狀態(tài)。均衡狀態(tài)下，非虛擬競爭者不能根據(jù)競爭決策機(jī)制爭奪更多資源，即除非引入資源交換規(guī)則，否則將不再進(jìn)行競爭決策。

g. 資源交換規(guī)則：達(dá)到均衡狀態(tài)后，資源交換規(guī)則將強(qiáng)制全部或部分競爭者（包括虛擬競爭者）之間相互交換資源，使競爭進(jìn)入非穩(wěn)定的均衡狀態(tài)。非穩(wěn)定的均衡狀態(tài)下，非虛擬的競爭者能根據(jù)競爭決策機(jī)制再次爭奪資源，直至達(dá)到一個新的均衡狀態(tài)。進(jìn)行資源交換后，必須使競爭進(jìn)入非穩(wěn)定的狀態(tài)，這樣才能使競爭者對資源再次進(jìn)行競爭，達(dá)到新的競爭決策均衡狀態(tài)，實(shí)現(xiàn)優(yōu)化的目的。

2 最大團(tuán)問題的競爭決策算法

2.1 問題介紹

最大團(tuán)問題描述如下：給定1 個簡單無向圖G=（V，E），S 是結(jié)點(diǎn)集合V 的1 個子集，若S 中任意2 個結(jié)點(diǎn)之間都相鄰，即由S 導(dǎo)出的子圖G[S]是完全子圖，且G[S]不包含在圖G 的更大的完全子圖中，則稱G[S]為團(tuán)。最大團(tuán)問題就是求出圖中結(jié)點(diǎn)個數(shù)最多的團(tuán)。

2.2 數(shù)學(xué)符號

G=（V，E）：G 代表簡單的無向圖，V 代表圖的結(jié)點(diǎn)集合，E 代表圖的邊集，且E 由V 中的結(jié)點(diǎn)對表示。

n：圖中結(jié)點(diǎn)的個數(shù)。

N（v）：結(jié)點(diǎn)v 的開鄰集，所有與結(jié)點(diǎn)v 相鄰的點(diǎn)的集合。

N[v]：結(jié)點(diǎn)v 的閉鄰集，即N（v）∪{v}。

d（v）：結(jié)點(diǎn)v 的度，即集合N（v） 中所包含的結(jié)點(diǎn)的個數(shù)。

G[V1]：G[V1]是圖G=（V，E）的點(diǎn)導(dǎo)出子圖，G[V1]=（V1，E1），其中，V1? V ，E1? E，且對于圖G 中的每一條2 個端點(diǎn)都在V1中的邊ei都有ei∈E1。

G1：初始狀態(tài)下，G1等于原圖G，即G1=（V，E）=（V1，E1）。

d（vi）：結(jié)點(diǎn)vi的度，即圖G 中與vi相鄰的點(diǎn)的個數(shù)。

d1（vi）：結(jié)點(diǎn)vi的度，即圖G1中與vi相鄰的點(diǎn)的個數(shù)。

p（i）：結(jié)點(diǎn)vi在G1圖中的競爭力函數(shù)。

Gb：算法在均衡時所求得的最大完全子圖。

Vad：與完全子圖Gb中各個結(jié)點(diǎn)相鄰結(jié)點(diǎn)的集合，即

Gmax：目前為止算法中所發(fā)現(xiàn)的最大團(tuán)。

|G|：G 圖中所包含的結(jié)點(diǎn)的個數(shù)。

|V|：結(jié)點(diǎn)集合所包含的結(jié)點(diǎn)個數(shù)。

2.3 數(shù)學(xué)性質(zhì)

現(xiàn)僅給出競爭決策算法所涉及到的最大團(tuán)的數(shù)學(xué)性質(zhì)，性質(zhì)1～3 的證明參閱文獻(xiàn)[9?10]。推論1 及性質(zhì)4 為本文提出的。算法中，推論1 用于刪除冗余結(jié)點(diǎn)，性質(zhì)4 用于資源交換。

性質(zhì)1若結(jié)點(diǎn)集合V 中某個結(jié)點(diǎn)v 的度是0，那么，v 必然不屬于所求的最大團(tuán)的結(jié)點(diǎn)集合S[14]。

性質(zhì)2若結(jié)點(diǎn)集合V 中某結(jié)點(diǎn)v 的度為n?1，那么，v 必然屬于所求的最大團(tuán)的結(jié)點(diǎn)集合S。

性質(zhì)3S 為求得的最大團(tuán)的結(jié)點(diǎn)集合，若v∈S 且d（v）=k；那么， | S|k+1[15]。

推論1設(shè)已求出的最大完全子圖為Gmax，其結(jié)點(diǎn)個數(shù)為|Gmax|，G1中某一結(jié)點(diǎn)v 的度d（v）=k，如果k<|Gmax|，則可以將v 從G1中刪除，從而使問題得到簡化。

證明根據(jù)性質(zhì)3 可得，度為k 的結(jié)點(diǎn)v 所在的完全子圖最多有k+1 個頂點(diǎn)，若k |Gmax|?1，則包含v 的完全子圖的頂點(diǎn)個數(shù)最多為|Gmax|個，不大于已求出的最大完全子圖Gmax的結(jié)點(diǎn)個數(shù)，所以，將v 作為冗余結(jié)點(diǎn)從G1中刪除，從而使問題得到簡化而不影響求解結(jié)果。

性質(zhì)4G2=（V2，E2）是G1=（V1，E1）的1 個子圖，且是完全圖，若V3? V1?V2，G3=（V3，E3）=G[V3]，V4? V2，V3與V2?V4中的所有結(jié)點(diǎn)都相鄰，若|V3|>|V4|，那么，將V4從G2中刪除，將V3加入G2，此時，G2為更大的完全子圖。

證明G3本身是1 個完全子圖，且V3中的所有結(jié)點(diǎn)與V2?V4中的所有結(jié)點(diǎn)都相鄰，因而新生成的圖G2是1 個結(jié)點(diǎn)個數(shù)更多的完全子圖。

2.4 算法思想

在CDA 中，結(jié)點(diǎn)是競爭者爭奪的資源，所需求解的最大團(tuán)是競爭者A，同時參與競爭的是虛擬競爭者N。初始狀態(tài)時，虛擬競爭者N 占有全部結(jié)點(diǎn)，競爭者A 不占有任何結(jié)點(diǎn)。達(dá)到均衡狀態(tài)時，競爭者A 具有的結(jié)點(diǎn)即為所求的最大團(tuán)。

2.5 初始狀態(tài)、競爭力函數(shù)、決策函數(shù)、資源交換規(guī)則

a.初始狀態(tài)。

對于含有n 個結(jié)點(diǎn)的圖，一共有n 個初始狀態(tài)，將結(jié)點(diǎn)按各個度的大小降序排列之后，第i 個初始狀態(tài)為競爭者A 僅占有資源vi，其余結(jié)點(diǎn)資源都被虛擬競爭者N 所占有。在每個初始狀態(tài)開始時需要檢查d（vi）是否小于已知最大完全子圖中結(jié)點(diǎn)的個數(shù)，若是，則該初始狀態(tài)不會出現(xiàn)更好的解且放棄掉該初始狀態(tài)。

b.競爭力函數(shù)。

采用一個競爭力函數(shù)

c.決策函數(shù)。

本文只有一個決策函數(shù)，即在競爭中將競爭力函數(shù)值p（i）最大的結(jié)點(diǎn)優(yōu)先加入到圖Gb中，當(dāng)多個結(jié)點(diǎn)的競爭力函數(shù)值相等時，則將編號小的結(jié)點(diǎn)加入到圖中。

d.資源交換規(guī)則。

資源交換規(guī)則見下面的算法流程。

2.6 算法的過程

算法的過程如下：

a.初始圖Gb和Gmax是1 個沒有結(jié)點(diǎn)、沒有邊的空圖，首先將G1中競爭力函數(shù)p（i）最大的點(diǎn)vi加入Gb中，然后將Vad中競爭力函數(shù)值p（i）最大的結(jié)點(diǎn)加入到Gb中。根據(jù)式（1）重新計算Vad，持續(xù)該步驟，直到Vad為空集。

b.檢查是否存在冗余結(jié)點(diǎn)，如果存在冗余結(jié)點(diǎn)，則刪除冗余結(jié)點(diǎn)并更新競爭力函數(shù)。具體的做法參見下面的算法流程。

c.執(zhí)行資源交換，交換后再次檢查是否存在冗余結(jié)點(diǎn)，如果存在，則剔除冗余結(jié)點(diǎn)后更新競爭力函數(shù)。詳細(xì)的內(nèi)容見下面的算法流程。

2.7 算法流程

步驟0k=1；將結(jié)點(diǎn)按各個結(jié)點(diǎn)的度從大到小排序，Vmax={ }，Emax={ }，Gmax=（Vmax，Emax）。

步驟1初始化。

設(shè)置初始狀態(tài)。競爭者A 只占有資源vk，其余結(jié)點(diǎn)都被虛擬競爭者N 占有。由推論1 可知，若|d（vi）|<|Vmax|，則該初始狀態(tài)不會出現(xiàn)更好的解，因此，此時跳到步驟3 而放棄該初始狀態(tài)；否則，繼續(xù)執(zhí)行下面的操作：

G1=（V1，E1）=（V，E）=G，從G1中刪除結(jié)點(diǎn)vk以及不與vk相鄰的所有結(jié)點(diǎn)，Vb={vk}，Eb={ }，Gb= （Vb，Eb），Vi={vk}，V*={ }，E*={ }，G*=（V*，

步驟2競爭決策。

根據(jù)式（2），計算初始狀態(tài)下競爭者A 對結(jié)點(diǎn)資源的競爭力函數(shù)值p（i），并降序排列。

a.本輪競爭階段1：資源分配階段。

（a）根據(jù)性質(zhì)1，刪除競爭力函數(shù)值為0 的結(jié)點(diǎn)，若刪除后G1為空集，算法結(jié)束，問題沒有意義。

根據(jù)性質(zhì)2 將度為n?1 的結(jié)點(diǎn)全部放入Gb中。

（b）根據(jù)式（1）計算Vad，并將Vad中競爭力函數(shù)值p（i）最大的結(jié)點(diǎn)加入到Gb中，之后重新計算Vad，持續(xù)該過程，直到Vad為空集。此時得到的圖是1 個完全子圖，且結(jié)點(diǎn)個數(shù)為|Gb|。若|Gb|>|Gmax|，則|Gmax|=|Gb|；否則，執(zhí)行步驟c。

b.本輪競爭階段2：刪除冗余結(jié)點(diǎn)。

利用推論1 刪除冗余結(jié)點(diǎn)，即將圖G1中度小于|Gmax|的頂點(diǎn)刪除，并重新計算G1中結(jié)點(diǎn)的競爭力函數(shù)，降序排列，輸出圖G1此時的結(jié)點(diǎn)個數(shù)n。

c.本輪競爭階段3：資源交換階段。

為了提高算法的速度，本算法只找出性質(zhì)4 中|V3|=2 且|V4|=1 的結(jié)點(diǎn)，用V3中的2 個結(jié)點(diǎn)交換V4中的1 個結(jié)點(diǎn)，這樣能得到一個更大的完全子圖Gb。持續(xù)查找和替換這種操作，直至圖G1中不存在這種滿足資源交換條件的結(jié)點(diǎn)。此時，若|Gb|>|Gmax|，則|Gmax|=|Gb|，利用推論1 刪除冗余結(jié)點(diǎn)；否則，舍棄Gb，執(zhí)行步驟3。

步驟3k=k+1，若k n，則跳到步驟1；否則，跳到步驟4。

步驟4算法結(jié)束。

輸出競爭決策的結(jié)果。

3 算法的時間復(fù)雜度分析

步驟2的a 最壞的情況下時間復(fù)雜度為O（n2）；步驟2 的b 剔除圖中冗余結(jié)點(diǎn)在最壞的情況下時間復(fù)雜度為O（n）；步驟2 的c 最多執(zhí)行的次數(shù)為n 次，1 個初始狀態(tài)查找并執(zhí)行1 次交換的時間復(fù)雜度為O（n2），因此，步驟2 的c 在最壞的情況下時間復(fù)雜度為O（n3）。綜上所述，該算法的時間復(fù)雜度為O（n3）。

4 示例分析

現(xiàn)給出1 個案例來闡述算法的原理以及過程，同時也只給出第1 個初始狀態(tài)下的競爭決策過程，如圖1 所示。

圖1 示例圖G1Fig.1 Sample graph G1

競爭決策計算如下：

a.初始化階段。

給出第1 個初始狀態(tài)下的競爭決策過程，因此，最開始時可以設(shè)置競爭者A 沒有占有資源結(jié)點(diǎn)v1，其他結(jié)點(diǎn)資源都被虛擬競爭者N 占有。從圖G1中刪除v1以及不與v1相鄰的所有結(jié)點(diǎn)v4和v5，V=V1={v2，v3，v6，v7，v8}，G1=（V，E）=（ V1， E1） ， Gb=（ Vb， Eb） ， Vb={v1}， Eb={ }，Gmax=（Vmax，Emax），Vmax={v1}，Emax={ }。

b.資源分配階段。

根據(jù)式（1）可得集合Vad={v2，v3，v6，v7，v8}，計算競爭力函數(shù)，p（1）=0，p（2）=5，p（3）=5，p（4）=0，p（5）=0，p（6）=4，p（7）=3，p（8）=3。

將Vad中競爭力函數(shù)值最大的1 個結(jié)點(diǎn)加入Vb中，如果存在若干個競爭力函數(shù)值最大的結(jié)點(diǎn)，任選1 個加入到Vb中。因此，先將v2加入到Vb，再重復(fù)計算1 次后將v3也加入到Vb，此時得到1 個團(tuán)Vb={v1，v3，v2}，且Vad為空集。

因 初 始 時Vmax={v1}， 所 以， 此 時 滿 足|Gb|>|Gmax|，將Gb中的結(jié)點(diǎn)放入Gmax，|Gmax|=3，Vmax={v1，v3，v2}。

c.根據(jù)b 刪除圖中冗余結(jié)點(diǎn)。

刪除V1中度小于 |Vmax|=3 的所有結(jié)點(diǎn)及與其相連的邊，因圖中所有結(jié)點(diǎn)的度都大于等于3，所以，此過程沒有冗余結(jié)點(diǎn)被刪除。

d.資源交換階段。

找出性質(zhì)4 中|V3|=2 且|V4|=1 的結(jié)點(diǎn)，此時找到V3={v4，v5}，V4={v1}，用V3中的2 個結(jié)點(diǎn)替換V4中的1 個結(jié)點(diǎn)，從而得到1 個更大的完全子圖Gb=（Vb，Eb），其 中，Vb=Vmax={v2，v3，v4，v5}，該完全子圖如圖2 所示。在圖1 中利用推論1 刪除冗余結(jié)點(diǎn)，即將圖1 中度小于|Vmax|=4 的頂點(diǎn) 刪除，據(jù)此 依次 刪 除v7，v8，v6，v1，v2，v3，v4，v5，圖1 變 為 空 圖，因 此，S={v2，v3，v4，v5}為最優(yōu)解。雖然這個實(shí)例得到了最優(yōu)解，但是，這個算法并不能保證求解所有的實(shí)例時都能得到最優(yōu)解。

e.輸出競爭決策結(jié)果。

Vmax={v2，v3，v4，v5}，最優(yōu)，其代表的圖如圖2 所示。

圖2 最大團(tuán)的圖Fig.2 Graph of maximum clique

5 數(shù)值計算及分析

為了對算法的有效性進(jìn)行驗(yàn)證，用Java 語言在PC 機(jī)上進(jìn)行計算實(shí)驗(yàn)。運(yùn)用本算法對DIMACS(The Center for Discrete Mathematics and Theoretical Computer Scinence)的基準(zhǔn)圖進(jìn)行求解，并與目前最好的結(jié)果進(jìn)行比較，如表1 所示，相關(guān)的測試實(shí)例可以登錄http://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark#detDSJC1000_5 下載。

式中：e 為誤差率；m 為目前最好解；l 為本文解。

最大團(tuán)問題是NP 難解問題，除非能夠證明所有NP 問題都可以轉(zhuǎn)化為具有多項(xiàng)式算法的判定問題，否則不存在多項(xiàng)式時間的精確算法。精確算法能夠求出最優(yōu)解，但是，求解時間隨著問題規(guī)模的增大而呈指數(shù)增長，時間復(fù)雜度較高。啟發(fā)式算法求解速度快，但是，一般情況下不能找到最優(yōu)解，只能找到近似解或者局部最優(yōu)解。本文的競爭決策算法是啟發(fā)式算法，利用本文算法對基準(zhǔn)圖進(jìn)行計算求解，在Eclipse 軟件上運(yùn)行，從表1 中可以看出，利用CDA 求得的解，和最優(yōu)解之間的誤差率基本保持在10%以內(nèi)。有些示例可以取得與目前最好的結(jié)果相同的解，如示例hamming8?4 和示例p_hat300?2，有些示例可以取得與目前最好結(jié)果極其相近的解，如示例C125.9，MANN_a27，MANN_a45。作 為 比 較，Belachew 等[11]用秩為1 的對稱非負(fù)矩陣逼近算法求解DIMACS 中的示例， 求解示例C500.9，MANN_a27，p_hat1500?2，p_hat1500?3 得到的最好解分別為50，123，61，92，而本文的求解結(jié)果分別為52，125，59，85。文獻(xiàn)[16]還將求解結(jié)果與其他2 個啟發(fā)式算法的求解結(jié)果進(jìn)行比較，結(jié)果顯示，啟發(fā)式算法在求解的36 個案例中，只有 3個案例得到了與該算法相近的解。

表1 CDA 算法結(jié)果與目前最好結(jié)果的比較Tab.1 Comparison between the results of CAD algorithum and the best results at present

6 結(jié)束語

競爭決策算法是解決組合優(yōu)化問題的有效算法，該算法根據(jù)所求解的問題的數(shù)學(xué)性質(zhì)設(shè)計出競爭規(guī)則、競爭力函數(shù)、決策函數(shù)以及設(shè)定初始格局就能很好地求解組合優(yōu)化問題。求解最大團(tuán)問題時，該算法在資源分配階段即可形成1 個初始解，根據(jù)性質(zhì)4 判斷是否存在滿足資源交換條件的結(jié)點(diǎn)，若存在則進(jìn)入資源交換階段，若不存在則舍棄該解，進(jìn)入新一輪的競爭決策，同時根據(jù)推論1 刪除冗余結(jié)點(diǎn)。初始解越接近最優(yōu)解，即初始解越好，求解速度就越快，可以通過設(shè)計合理的競爭規(guī)則和競爭力函數(shù)以及決策函數(shù)來得到較好的初始解。特別是在求解稀疏圖的最大團(tuán)問題時，競爭決策算法可以得到較好的初始解，同時根據(jù)推論1 快速刪除較多冗余結(jié)點(diǎn)，實(shí)現(xiàn)快速求解。例如，1 個度小于等于2 的圖，根據(jù)性質(zhì)3 可知，該圖的最大團(tuán)最多只有3 個結(jié)點(diǎn)，競爭決策算法可以在資源分配階段就能得到最優(yōu)解，同時根據(jù)推論1 刪除所有結(jié)點(diǎn)，問題得以快速求解。競爭決策算法原理簡單，目前已經(jīng)應(yīng)用于TSP 問題(旅行商問題)、多目標(biāo)TSP 問題、0?1 背包問題、最小頂點(diǎn)覆蓋問題等，具有普遍的適用性。