基本介紹
- 中文名：最大團問題
- 外文名：Maximum Clique Problem
- 簡稱：MCP
- 性質：一個經典的組合最佳化問題
概述,問題描述,套用背景,常用算法,順序貪婪啟發式算法,局部搜尋啟發式算法,智慧型搜尋啟發式算法,遺傳算法,模擬退火算法,禁忌算法,神經網路算法,改進蟻群算法-AntMCP,其它啟發式算法,回溯法,分支限界法,
概述
最大團問題又稱為最大獨立集問題（Maximum Independent Set Problem）。確定性算法有回溯法、分支限界法等，啟發式算法有蟻群算法、順序貪婪算法、DLS-MC算法和智慧型搜尋算法等。
問題描述
給定無向圖G=(V,E)，其中V是非空集合，稱為頂點集；E是V中元素構成的無序二元組的集合，稱為邊集，無向圖中的邊均是頂點的無序對，無序對常用圓括弧“( )”表示。如果U
V，且對任意兩個頂點u，v∈U有(u,v)∈E，則稱U是G的完全子圖。G的完全子圖U是G的團。G的最大團是指G的最大完全子圖。
如果UÍV且對任意u，v∈U有(u,v)不屬於E，則稱U是G的空子圖。G的空子圖U是G的獨立集若且唯若U不包含在G的更大的空子圖中。G的最大獨立集是G中所含頂點數最多的獨立集。
如果U是G的完全子圖，則它也是G'的空子圖，反之亦然。因此，G的團與G'的獨立集之間存在一一對應的關係。特殊地，U是G的最大團若且唯若U是G'的最大獨立集。
套用背景
近年來研究表明，單獨使用一種啟發式算法求解最大團問題，算法性能往往並不是很好，因此，常借鑑算法之間優勢互補策略，形成新的混合啟發式算法來求解最大團問題。當前求解該問題最好的啟發式算法有反作用禁忌搜尋（Reactive Tabu Search, RTS）算法、基於遺傳算法的簡單啟發式算法（Simple Heuristic Based Genetic Algorithm, HGA）、DLS-MC算法等。
常用算法
順序貪婪啟發式算法
順序貪婪啟發式算法是最早的求解最大團的啟發式算法。這類算法通過給一個團重複進行加點操作得到一個極大團或者對一組並不是團的子圖重複進行刪除頂點操作以得到一個團。1987年，Kopf和Ruhe把這類型算法分為Best in和Worst out兩類。
(1)Best in方法的基本思路：由一個團出發，和這個團中頂點相連的頂點組成候選集；然後以一定的啟發式信息，從中選擇頂點加入團中，以後反覆進行，直到最後得到一個極大團。
(2)Worst out方法的基本思路：從整個頂點集開始，然後按一定的啟發式信息，從中反覆進行刪除頂點操作，直到最後得到一個團。
順序貪婪啟發式算法有很大不足，該算法一旦找見一個極大團，搜尋就停止，因此找到最大團的機率相對較低。
局部搜尋啟發式算法
假設SG為圖的所有極大團的集合，由於順序貪婪啟發式算法僅能找見SG中的一個極大團，因此，為了提高解的質量，應當擴大在SG的搜尋區域，比如，可以在極大團S的鄰居中繼續進行搜尋，以擴大搜尋區域，進而提高解的質量。
在局部搜尋啟發式算法中，如果搜尋S的鄰居越多，提高解的質量的機會就越大。依賴不同的鄰居定義，局部搜尋啟發式算法可以得到不同的解。在局部搜尋啟發式算法中，比較有名的算法是K-interchange啟發式算法，它是一種基於K-neighbor鄰居實現的，在解集S的K鄰居中進行局部搜尋的方法。
WaynePullan和HolgerH．Hoos基於這一思想提出了求解最大團問題的DLS-MC算法，該算法是plateau search局部搜尋啟發式和算法疊代改善法相混合得到的，算法性能非常好，在該方法中引入了頂點懲罰函式，該函式在算法的求解過程中能夠動態改變；在算法執行過程中疊代改善法和plateau search算法輪流執行來提高解的質量。在基準圖上對該算法進行了測試，性能非常好。
智慧型搜尋啟發式算法
遺傳算法
遺傳算法（Genetic Algorithm, GA）是一種基於自然選擇和群體遺傳機理的搜尋算法，它模擬了自然選擇和自然遺傳過程中發生的複製、交叉和變異現象。
l998年，Marchiori提出了一種基於遺傳算法的簡單啟發式算法（simple heuristic based genetic algorithm, HGA)。算法由兩部分組成：簡單遺傳算法（simple genetic algorithm, SGA）和簡單的貪婪啟發式局部搜尋算法（simple greedy heuristic local search algorithm,SGHLSA）。在基準圖上對算法HGA的性能進行測試，證明了該算法在解的質量和計算速度方面都優於基於遺傳算法的其它算法。
因此，單純使用遺傳算法（改動變異、雜交、選擇等運算元）求解最大團問題時，算法的性能是比較差；要提高算法性能，遺傳算法最好能和局部搜尋算法相結合。
模擬退火算法
模擬退火（Simulated Annealing, SA）算法是N. Metropolis在1953年提出的一種基於物質退火過程的隨機搜尋算法，是一種疊代求解的啟發式隨機搜尋算法。首先在高溫下較快地進行搜尋，使系統進入“熱平衡”狀態，大致地找到系統的低能區域。隨著溫度的逐漸降低，搜尋精度不斷提高，可逐漸準確地找到最低能量的基態。作為局部搜尋算法的擴展，當鄰域的一次操作使當前解的質量提高時，接受這個改進解作為新的當前解；反之，以一定的機率接受相對質量比較差的解作為新的當前解。
Aarts和Korst提出使用模擬退火算法來解決獨立集問題，建議在算法設計時引入懲罰函式，但卻沒有提供任何的實驗結果。問題的解空間S是圖G的全部可能的子圖，並不要求是獨立集，對於任一子圖G*，成本函式為f(V')=|V'|-k|E'|，其中V'是圖G*的頂點集，E'是圖G*的邊集，k是權因子（k>1）。選擇鄰居時，費用值大的將被選中，因此求解最大獨立集問題也就是最大化成本函式問題。
Homer和Peinado把模擬退火算法和Johnson的貪婪啟發式算法、Boppan的隨機化算法、Halldorsson的子圖排除法3種啟發式算法進行比較，結果比這3種算法要好很多。總之，模擬退火算法在處理最大團問題上是一個非常好的算法。
禁忌算法
禁忌算法（Tabu Algorithm）是一種改進的局部搜尋算法。該算法為了避免在搜尋過程中出現死循環和開發新的搜尋區域，採用了一種基於禁止的策略。
神經網路算法
20個世紀80年代末期，Ballard、Godbeerl、Ramanujam和Sadayappan等都嘗試對最大團和相關問題按人工神經網路進行編碼，進而求解該問題。然而，這些研究只提供了很少的實驗結果。
Grossman提出一種離散的/確定性的Hopfield模型來求解最大團。這個模型有一個用來決定網路是否處於穩定態的臨界值參數。Grossman建議在這個參數上使用退火策略，並且使用自適應機制選擇網路的初始狀態和臨界值。在DIMACS基準圖上測試，得到比較好的結果，但與性能好的啟發式算法相比，其結果較差，比如結果要差於模擬退火算法。1995年Jagota對Hopfield模型進行了多處修改來近似求解最大團問題，其中有的是離散化的，有的是連續的；雖然有了一定改進，但是性能並沒有顯著提高。隨後，仍然有好多研究者使用Hopfield神經網路來求解最大團問題，但是與其它智慧型搜尋算法相比，效果比較差。
研究表明：(1) 前3種智慧型搜尋算法適合求解MCP，而通過神經網路算法求解MCP時的性能比較差；(2) 單獨使用智慧型搜尋算法來求解MCP，算法性能並不好，因此，常和局部搜尋算法相結合形成新的混合算法，比如：禁忌算法與局部搜尋算法相混合形成的反作用禁忌搜尋算法，遺傳算法與局部搜尋算法相混合形成的簡單啟發式算法等。
改進蟻群算法-AntMCP
蟻群算法是由Dorigo M.等人依據模仿真實的蟻群行為而提出的一種模擬進化算法。螞蟻之間是通過一種稱為信息素（Pheromone）的物質傳遞信息的，螞蟻能夠在經過的路徑上留下該種物質，而且能夠感知這種物質的存在及其強度，並以此來指導自己的運動方向。因此，由大量螞蟻組成的集體行為便表現出一種信息正反饋現象：某一條路徑上走過的螞蟻越多，該路徑上留下的信息素就越多，則後來者選擇該路徑的機率就越大。螞蟻之間就是通過這種信息素的交流，搜尋到一條從蟻巢到食物源的最短路徑。
2003年，Fenet和Solnon提出了求解最大團問題的蟻群算法AntClique，該算法仍然將信息素留在邊上，信息素tij是指把結點i和結點j分配到同一個團中的期望。由於沒有使用局部啟發信息，這使得疊代初期各候選頂點的選擇機率幾乎相等，這樣算法在疊代初期有一定的盲目性，往往需要更多的疊代次數才能得到最優解。針對這些不足及最大團問題的特點，曾艷於2010年提出了改進的蟻群算法-AntMCP。
算法偽代碼描述如下：
Procedure Vertex_AntClique
Initialize //初始化信息素和局部啟發信息
Repeat
For k in 1...nb Ants do:
Choose randomly a first vertex v f∈V
Ck←{v f }
Candidate ¬{v i |(v f,v i) ∈E}
While Candidate≠0 do
Choose a vertex v i∈Candidate with probability p(v i);
Ck←Ck∪{v i}
Candidate ←Candidate ∩{v j |(vi,v j) ∈E}
End of while
End of for
Update pheromone w.r.t {C1,…,CnbAnts}
Until max cyclesreached or optimal solution found
End of procedure
在AntMCP中，增加了局部啟發信息；信息素t和啟發信息h不是留在邊上，而是留在頂點上。這樣，變數t和h由二維降為一維，既可節省存儲空間，又可提高運行速度，大量實驗表明，該算法運算速度更快，效率更高。
其它啟發式算法
除上述幾種啟發式算法外，目前研究者們還提出了一些新的算法。當圖的頂點數不大於閾值M時，稱此圖為低度圖，求解低度圖的最大團問題的時間複雜度為O(d)，基於這一思想，王青松和范鐵生提出了一種求解低度圖的最大團的確定性算法。在該算法中，通過對圖按頂點逐步分解實現分別計算，較好地解決了低度圖的最大團問題，算法的時間複雜度為O(d*n^3)。針對遺傳算法在最大團求解中保持群體多樣性能力不足、早熟、耗時長、成功率高等缺陷，依據均勻設計抽樣理論對交叉操作進行重新設計，結合免疫機理定義染色體濃度設計克隆選擇策略，周本達、岳芹等提出了一種求解最大團問題的均價設計抽樣免疫遺傳算法。仿真算例表明，該算法在解的質量、收斂速度等各項指標上均有提高，與DLS-MC、QUALEX等經典搜尋算法相比，對部分算例能得到更好解。吳冬輝和馬良提出了基於遺傳算法的最大團問題求解算法，通過引入機率模型指導變異產生新的個體，並結合啟發式局部算法搜尋最大團。實例結果驗證了該算法的有效性。針對求解最大團問題的分層的邊權網路（Hierarchical Edge-Weight Network,HEWN）算法，郭長庚和潘曉偉設計了一個實現HEWN算法的數據結構，指出在HEWN算法中HEWN算法的存儲宜採用鄰接多重表和二叉表相結合的鍊表表示法，並進行了時間複雜度分析，得出HEWN算法的時間複雜度是指數級而不是O(n^8.5)。針對基於適應值的選擇交叉機制在最佳化具有欺騙性的最大團問題中性能退化的問題，張雁、黨群等提出了一種新的基於匹配教程的Memetic算法。算法中提出交叉匹配度的概念，用來估計兩個體交叉所能獲得的最佳適應值。通過匹配度的計算對交叉方向的選擇進行控制，保證了交叉操作以較大的機率生成新的優良模式。測試結果表明，該算法優於目前在最大團問題求解中性能最好的多階段動態局部搜尋算法。DNA計算是套用分子生物技術進行計算的新方法，具有高度並行性、大容量、低能耗等特點。針對這一特點，李濤提出了用DNA算法求解最大團問題，開創了以生物技術為工具解決複雜問題的新紀元，為解決NP完全問題開闢了一條新途徑。基於對貼上模型的組成、基本實驗及其生化實現過程的分析，根據最大團問題的需求，周康、劉朔等在貼上模型中，提出了基於電泳技術和分離實驗的DNA序列檢測方法。基於分離實驗提出了一種求解最大團問題的DNA算法，並給出了其生化實現過程。為了提高交叉熵算法求解最大團問題的性能，呂強、柏戰華等提出了一種領導者-跟隨者協作求解的並行策略來實現交叉熵算法，從而達到減少計算時間和保障解的質量兩者的平衡。算法中領導者活躍在並行處理器之間採集數據，並根據當前獲得信息對跟隨者作出決策；受控的跟隨者則主要根據領導者的決策信息自適應地調整搜尋空間，完成各自的集團產生任務。實驗結果表明該算法較基於種群的啟發式算法有一定的性能改善。
回溯法
回溯法（BacktrackingAlgorithm, BA）有“通用的解題法”之稱，用它可以系統地搜尋一個問題的所有解或任一解，是一個既帶有系統性又帶有跳躍性的搜尋算法。在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜尋解空間樹。算法搜尋至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該結點為根的子樹的系統搜尋，逐層向其祖先結點回溯；否則，進入該子樹，繼續按照深度優先的策略進行搜尋。BA在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜尋遍才結束。而BA在用來求問題的任一解時，只要搜尋到問題的一個解即可結束。這種以深度優先的方式系統地搜尋問題的解的算法稱為回溯法，它適用於解一些組合數較大的問題。
回溯法搜尋解空間樹時，根節點首先成為一個活結點，同時也成為當前的擴展節點。在當前擴展節點處，搜尋向縱深方向移至一個新節點。這個新節點就成為一個新的活結點，並成為當前擴展節點。如果當前擴展節點不能再向縱深方向移動，則當前的擴展節點就成為死結點。此時，往回回溯至最近的一個活節點處，並使這個活結點成為當前的擴展節點。
回溯法以這種方式遞歸地在解空間中搜尋，直至找到所有要求的解或解空間已無活結點為止。
剪枝：在搜尋至樹中任一結點時，先判斷該結點對應的部分解是否滿足約束條件，或者是否超出目標函式的界；也即判斷該結點是否包含問題的解，如果肯定不包含，則跳過對以該結點為根的子樹的搜尋，即剪枝（Pruning）；否則，進入以該結點為根的子樹，繼續按照深度優先的策略搜尋。
一般來講，回溯法求解問題的基本步驟如下：
(1)針對所給問題，定義問題的解空間；確定易於搜尋的解空間結構；以深度優先方式搜尋解空間，並在搜尋過程中利用Pruning函式剪去無效的搜尋。
(2)無向圖G的最大團問題可以看作是圖G的頂點集V的子集選取問題。因此可以用子集樹表示問題的解空間。設當前擴展節點Z位於解空間樹的第i層。在進入左子樹前，必須確認從頂點i到已入選的頂點集中每一個頂點都有邊相連。在進入右子樹之前，必須確認還有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。
(3)用鄰接矩陣表示圖G，n為G的頂點數，cn存儲當前團的頂點數，bestn存儲最大團的頂點數。cn+n-i為進入右子樹的上界函式，當cn+n-i<bestn時，不能在右子樹中找到更大的團，利用剪枝函式可將Z的右結點剪去。
實例分析
如圖1所示，給定無向圖G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根據MCP定義，子集{1,2}是圖G的一個大小為2的完全子圖，但不是一個團，因為它包含於G的更大的完全子圖{1,2,5}之中。{1,2,5}是G的一個最大團。{1,4,5}和{2,3,5}也是G的最大團。圖2是無向圖G的補圖G'。根據最大獨立集定義，{2,4}是G的一個空子圖，同時也是G的一個最大獨立集。雖然{1,2}也是G'的空子圖，但它不是G'的獨立集，因為它包含在G'的空子圖{1,2,5}中。{1,2,5}是G'的最大獨立集。{1,4,5}和{2,3,5}也是G'的最大獨立集。以圖1為例，利用回溯法搜尋其空間樹，具體搜尋過程（見圖3所示）如下：假設我們按照1®2®3®4®5的順序深度搜尋。開始時，根結點R是唯一活結點，也是當前擴展結點，位於第1層，此時當前團的頂點數cn=0，最大團的頂點數bestn=0。在這個擴展結點處，我們假定R和第二層的頂點1之間有邊相連，則沿縱深方向移至頂點1處。此時結點R和頂點1都是活結點，頂點1成為當前的擴展結點。此時當前團的頂點數cn=1，最大團的頂點數bestn=0。繼續深度搜尋至第3層頂點2處，此時頂點1和2有邊相連，都是活結點，頂點2成為當前擴展結點。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜尋至第4層頂點3處，由於頂點3和2有邊相連但與頂點1無邊相連，則利用剪枝函式剪去該枝，此時由於cn+n-i=2+5-4=3>bestn=0，則回溯到結點2處進入右子樹，開始搜尋。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜尋至第5層頂點4處，由於頂點3和4無邊相連，剪去該枝，回溯到結點3處進入右子樹，此時當前團的頂點數cn=2，最大團的頂點數bestn=0。繼續深度搜尋至第6層頂點5處，由於頂點5和4有邊相連，且與頂點1和2都有邊相連，則進入左子樹搜尋。由於結點5是一個葉結點，故我們得到一個可行解，此時當前團的頂點數cn=3，最大團的頂點數bestn=3。vi的取值由頂點1至頂點5所唯一確定，即v=(1, 2, 5)。此時頂點5已不能再縱深擴展，成為死結點，我們返回到結點4處。由於此時cn+n-i=3+5-6=2<bestn=3，不能在右子樹中找到更大的團，利用剪枝函式可將結點4的右結點剪去。以此回溯，直至根結點R再次成為當前的擴展結點，沿著右子樹的縱深方向移動，直至遍歷整個解空間。最後得到圖1的按照1®2®3®4®5的順序深度搜尋的最大團為U={1,2,5}。當然{1,4,5}和{2,3,5}也是其最大團。
圖1
圖2
圖3
圖1圖2圖3C++ 代碼
//MaxClique.cpp : 定義控制台應用程式的入口點。/*回溯法求解最大團問題*/#include <fstream>#include <iostream>#include <stdlib.h>#include <conio.h>using namespace std;#define MAX_v 50 //定義一個最大頂點個數typedef struct{ int a[MAX_v][MAX_v]; //無向圖G的鄰接矩陣 int v; //無向圖G的頂點 int e; //無向圖G的邊 int x[50]; //頂點與當前團的連線，x[i]=1 表示有連線 int bestx[50]; //當前最優解 int cnum; //當前團的頂點數目 int bestn; //最大團的頂點數目}MCP;void Creat(MCP &G);void Backtrack(MCP &G,int i);void Creat(MCP &G){ int i,j; ifstream fin("data.txt"); if (!fin) { cout<<"不能打開檔案:"<<"data.txt"<<endl; exit(1); } fin>>G.v; for (int i=1;i<=G.v;i++) for (int j=1;j<=G.v;j++) fin>>G.a[i][j]; for(i=1;i<=G.v;i++) //初始化 { G.bestx[i]=0; G.x[i]=0; G.bestn=0; G.cnum=0; } cout<<"————————————————"<<endl; cout<<"———回溯法求解最大團問題———"<<endl; cout<<"————————————————"<<endl; cout<<"輸入初始化無向圖矩陣為:"<<endl; //初始化 for(i=1;i<=G.v;i++) { for(j=1;j<=G.v;j++) cout<<G.a[i][j]<<" "; cout<<endl; }}void Backtrack(MCP &G,int i){ if (i>G.v){ for (int j=1; j<=G.v; j++) G.bestx[j] = G.x[j]; G.bestn =G.cnum; return ; } //檢查頂點i與當前團的連線 int OK = 1; for (int j=1; j<=i ; j++) if (G.x[j]&& G.a[i][j]==0){ //i不與j相連 OK = 0; break; } if (OK) { G.x[i] = 1;//把i加入團 G.cnum++; Backtrack(G,i+1); G.x[i]=0; G.cnum-- ; } if (G.cnum+G.v- i>G.bestn){ G.x[i] = 0; Backtrack(G,i+1); }}int main(){ MCP G; Creat(G); Backtrack(G,1); cout<<"最大團包含的頂點數為:"<<G.bestn<<endl; cout<<"最大團方案為:( "; for (int i=1;i<=G.v;i++) if(G.bestx[i]==1){ cout<<i<<" "; } cout<<")"<<endl; getch();}分支限界法
分支限界法常以廣度優先或最小耗費（最大效益）優先的方式搜尋解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。一旦活結點成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，捨棄那些導致不可行解或導致非最優解的兒子結點，將其餘兒子結點加入活結點表中。此後，從活結點表中取下一個結點成為當前擴展結點，並重複上述結點擴展過程，直至找到所需的解或活結點表為空時為止。
具體來講，分支限界法由“分支”策略和“限界”策略兩部分組成。“分支”體現在對問題空間是按廣度優先搜尋；“限界”策略是為了加速搜尋速度而採用啟發式剪枝的策略。分支搜尋法採用廣度優先的策略，依次生成E結點所有分支（即所有的子結點）。在生成的結點中，將採用更有效的約束函式（限界函式）控制搜尋路徑，去除那些不滿足約束條件（即不可能導出最優解）的結點，使之能更好地朝著狀態空間樹上有最優解的分支推進。
根據從活結點表中選擇下一個擴展結點的方式的不同，分支限界法主要分為以下兩類：
1.佇列式（FIFO）分支限界法
佇列式分支限界法將活結點表組織成一個佇列，並按佇列的FIFO原則選取下一個結點成為當前擴展結點。具體流程為：
A.初始化，根結點是唯一的活結點，根結點入隊。
B.從活結點隊中取出根結點後，作為當前E結點。對當前E結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函式的兒子加入活結點佇列中。
C.重複上述過程：再從活結點表中取出隊首結點（隊中最先進來的結點）為當前E結點，……；直到找到一個解或活結點佇列為空為止。
優先佇列式分支限界法將活結點表組織成一個優先佇列，並按優先佇列中規定的結點優先權選取優先權最高的下一個結點成為當前擴展結點。具體流程為：對每一活結點計算一個優先權，並根據這些優先權，從當前活結點表中優先選擇一個優先權最高（最有利）的結點作為擴展結點，使搜尋朝著解空間樹上有最優解的分支推進，以便儘快地找出一個最優解。
C++ 代碼
//MaxClique_BB.cpp : 定義控制台應用程式的入口點。/*分支限界法求解最大團問題*/#include <fstream>#include <iostream>#include <queue>#include <conio.h>using namespace std;typedef struct{ int v; //無向圖G的頂點 int e; //無向圖G的邊 int a[50][50]; //定義圖G的鄰接矩陣 int bestx[50]; //最優解}MCP;void Creat(MCP &G){ int i,j; ifstream fin("data.txt"); if(!fin) { cout<<"不能打開檔案:"<<"data.txt"<<endl; exit(1); } fin>>G.v; for(int i=1;i<=G.v;i++) for(int j=1;j<=G.v;j++) fin>>G.a[i][j]; for(i=1;i<=G.v;i++) //初始化 { G.bestx[i]=0; } cout<<"————————————————————————"<<endl; cout<<"———優先佇列式分支限界法求解最大團問題———"<<endl; cout<<"————————————————————————"<<endl; cout<<"輸入初始化無向圖矩陣為:"<<endl; //初始化 for(i=1;i<=G.v;i++) { for(j=1;j<=G.v;j++) cout<<G.a[i][j]<<" "; cout<<endl; }}struct BBNode{ BBNode *parent; //指向父結點的指針 bool LChild; //左兒子結點標誌};struct CliqueNode //定義優先佇列類型為CliqueNode{ int cnum; //當前團的頂點數 int un; //當前團最大頂點數的上界 int level; //結點在子集空間樹種所處的層次 BBNode *p; //指向活結點在子集樹中相應結點的指針 bool operator<(const CliqueNode &b) const //<號重載建立大根堆 { if (b.un>un) return true; if (b.un==un&& b.cnum>cnum) return true; else return false; }};void BBMaxClique(MCP&G){ BBNode *E=new(BBNode); //定義B代表記錄的佇列情況 //初始化 int j,i=1; int cnum=0,bestn=0; int OK=1; priority_queue<CliqueNode> Q; //定義優先佇列Q E->LChild=false; //初始化 E->parent=NULL; while(i!=G.v+1)//非葉結點 { //檢查頂點i與當前團中其它頂點之間是否有邊相連 OK=1; BBNode *B=E; //把當前點的數據給B，B為中間變數 for(j=i-1;j>0;B=B->parent,j--) if(B->LChild&& G.a[i][j]==0) //如果不滿足就停止 { OK=0; break; } if(OK) //滿足條件，即左兒子結點為可行結點 { CliqueNode *D=new(CliqueNode); //定義一個節點D D->p=new(BBNode); if(cnum+1>bestn)bestn=cnum+1; D->cnum=cnum+1; D->level=i+1; D->p->LChild=true; D->p->parent=E; D->un=cnum+1+G.v-i; Q.push(*D); //進佇列 } if(cnum+G.v-i>bestn) //不滿足條件但是還是可能有最優解 { CliqueNode *D=new(CliqueNode); //定義一個節點D D->p=new(BBNode); D->cnum=cnum; D->level=i+1; D->p->LChild=false; D->p->parent=E; D->un=cnum+G.v-i; Q.push(*D); //進佇列 } CliqueNode N; N=Q.top(); //取隊頂元素，最大堆 Q.pop(); //刪除隊頂元素 E=N.p; //記錄當前團的信息 cnum=N.cnum; //記錄當前團的頂點數 i=N.level; //所在的層次 } for(j=G.v;j>0;j--) //保存最優解 { G.bestx[j]=E->LChild; E=E->parent; bestn=cnum; }}int main(){ MCP G; Creat(G); BBMaxClique(G); cout<<"最大團方案為:("; for(int i=G.v;i>0;i--) if (G.bestx[i]==1){ cout<<i<<" "; } cout<<")"<<endl; getch();}