最大團(tuán)算法研究課件

1、2009最大團(tuán)算法研究主要介紹：Company Logo最大團(tuán)定義以其研究進(jìn)展1最大團(tuán)的算法介紹2回溯法和分支限界法詳細(xì)介紹3最大團(tuán)的應(yīng)用4MCP描述Company Logo最大團(tuán)問題 (Maximum Clique Problem, MCP)描述： 對于給定圖G( V，E)， 其中，V =(1，n)是圖G的頂點(diǎn)集，E VxV是圖G的邊集。圖G的團(tuán)就是一兩兩之間有邊的頂點(diǎn)集合。如果一個(gè)團(tuán)不被其它任一團(tuán)所包含，即它不是其它任一團(tuán)的真子集，則稱該團(tuán)為圖G的極大團(tuán)。頂點(diǎn)最多的極大團(tuán)，稱之為圖G的最大團(tuán)。 最大團(tuán)問題的目標(biāo)就是要找到給定圖的最大團(tuán)。MCP數(shù)學(xué)描述Company Logo MCP作為一個(gè)

2、整數(shù)規(guī)劃問題有許多等價(jià)的描述。整數(shù)規(guī)劃問題的描述(二次0-1問題)：則設(shè)其中，n為圖的頂點(diǎn)數(shù)。MCP數(shù)學(xué)描述Company Logo由于（1） 如果 是（1）的最優(yōu)解，那么集合C= 是圖G的最大團(tuán)，且MCP數(shù)學(xué)描述Company Logo因此有其中： 圖G的補(bǔ)圖 的鄰接矩陣。MCP等價(jià)于下面的全局二次0-1問題其中：如果 是（2）的最優(yōu)解，那么集合 是圖G的一個(gè)最大團(tuán)，且（2）算法研究進(jìn)展Company Logo神經(jīng)網(wǎng)絡(luò)模擬退火禁忌搜索基于連續(xù)的啟發(fā)式算法遺傳算法19901989198719571993now反作用禁忌搜索算法、簡單啟發(fā)式算法、DLSMC 1957年，Hararv和Ross首次

3、提出求解最大團(tuán)問題的確定性算法 。但隨著研究的深入，遇到的問題復(fù)雜度越來越高(頂點(diǎn)增多和邊密度變大)，確定性算法顯得無能為力，不能有效解決這些NP完全問題，典型地體現(xiàn)是運(yùn)行時(shí)間過長。 在20世紀(jì)80年代末開始采用啟發(fā)式算法求解最大團(tuán)問題，并且取得了令人滿意的效果。在時(shí)間上，由于采用了啟發(fā)式信息，啟發(fā)式算法的運(yùn)算時(shí)間與確定性算法的運(yùn)算時(shí)間之間的比值會(huì)隨著圖的頂點(diǎn)、密度的增加而變得越來越小。唯一的缺點(diǎn)就是不一定能找到最優(yōu)值，有時(shí)只能找到近優(yōu)值。 研究表明，單獨(dú)使用一種啟發(fā)式算法求解最大團(tuán)問題，算法性能并不是很好，因此，需要算法之間互相取長補(bǔ)短，形成新的混合算法來求解最大團(tuán)問題。當(dāng)前求解該問題最好的

4、啟發(fā)式算法有反作用禁忌搜索算法(Reactive Tabu Search)、簡單啟發(fā)式算法(Simple Heuristic Based Genetic Algorithm，HGA)和DLSMC等。MCP啟發(fā)式算法介紹Company Logo 局部搜索啟發(fā)式算法存在一個(gè)問題是：僅能夠找見一個(gè)局部最優(yōu)值。所以為了提高求解的質(zhì)量，該算法和其它算法相混合得到新性能好的算法。假設(shè) 為圖的所有極大團(tuán)的集合，擴(kuò)大 在的搜索區(qū)域，比如，可以在極大團(tuán)S的鄰居中繼續(xù)進(jìn)行搜索，以擴(kuò)大搜索區(qū)域，進(jìn)而提高解的質(zhì)量 。依賴不同的鄰居定義，局部搜索啟發(fā)式算法可以得到不同的解。局部搜索啟發(fā)式算法DLSMC算法plateau

5、 search局部搜索啟發(fā)式和算法迭代改善法相混合得到的，該方法中引入了頂點(diǎn)懲罰函數(shù)，函數(shù)在算法的求解過程中能夠動(dòng)態(tài)改變；在算法執(zhí)行過程中迭代改善法和plateau search算法輪流執(zhí)行來提高解的質(zhì)量。MCP啟發(fā)式算法介紹Company Logo智能搜索算法遺傳算法其他算法禁忌算法模擬退火算法神經(jīng)網(wǎng)絡(luò)MCP啟發(fā)式算法介紹Company Logo 一種基于自然選擇和群體遺傳機(jī)理的搜索算法，它模擬了自然選擇和自然遺傳過程中發(fā)生的復(fù)制、交叉和變異現(xiàn)象，適應(yīng)度函數(shù)起著非常關(guān)鍵的作用。遺傳算法簡單啟發(fā)式算法 HGA 算法由兩部分組成：簡單遺傳算法(SGA)和簡單的貪婪啟發(fā)式局部搜索算法。在基準(zhǔn)圖上對

6、算法HGA的性能進(jìn)行測試，證明了該算法在解的質(zhì)量和計(jì)算速度方面都優(yōu)于基于遺傳算法的其它算法。MCP詳細(xì)算法介紹Company Logo回溯法分支限界法MCP回溯法詳細(xì)介紹Company Logo問題描述 給定無向圖G=(V，E)。如果U V，且對任意u，v U有(u，v) E，則稱U是G的完全子圖。G的完全子圖U是G的團(tuán)當(dāng)且僅當(dāng)U不包含在G的更大的完全子圖中。G的最大團(tuán)是指G中所含頂點(diǎn)數(shù)最多的團(tuán)。 下圖G中，子集1，2是G的大小為2的完全子圖。這個(gè)完全子圖不是團(tuán)，因?yàn)樗籊的更大的完全子圖1，2，5包含。1，2，5是G的最大團(tuán)。1，4，5和2，3，5也是G的最大團(tuán)。 12453MCP回溯法詳細(xì)

7、介紹Company Logo回溯法基本思想 回溯法按照深度優(yōu)先策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。 回溯法搜索解空間樹時(shí)，根節(jié)點(diǎn)首先成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展節(jié)點(diǎn)。在當(dāng)前擴(kuò)展節(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新節(jié)點(diǎn)。這個(gè)新節(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。如果當(dāng)前擴(kuò)展節(jié)點(diǎn)不能再向縱深方向移動(dòng)，則當(dāng)前的擴(kuò)展節(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，往回回溯至最近的一個(gè)活節(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展節(jié)點(diǎn)。 回溯法以這種方式

8、遞歸地在解空間中搜索，直至找到所有要求的解或解空間已無活結(jié)點(diǎn)為止。MCP回溯法詳細(xì)介紹Company Logo算法設(shè)計(jì) 無向圖G的最大團(tuán)問題可以看作是圖G的頂點(diǎn)集V的子集選取問題。因此可以用子集樹表示問題的解空間。設(shè)當(dāng)前擴(kuò)展節(jié)點(diǎn)Z位于解空間樹的第i層。在進(jìn)入左子樹前，必須確認(rèn)從頂點(diǎn)i到已入選的頂點(diǎn)集中每一個(gè)頂點(diǎn)都有邊相連。在進(jìn)入右子樹之前，必須確認(rèn)還有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)。 用鄰接矩陣表示圖G，n為G的頂點(diǎn)數(shù)，cn存儲當(dāng)前團(tuán)的頂點(diǎn)數(shù)，bestn存儲最大團(tuán)的頂點(diǎn)數(shù)。cn+n-i為進(jìn)入右子樹的上界函數(shù)，當(dāng)cn+n-ibestn時(shí)，右子樹中可能含有最優(yōu)解，此時(shí)將右兒

9、子結(jié)點(diǎn)加入到子集樹中并插入到活結(jié)點(diǎn)優(yōu)先隊(duì)列中。優(yōu)先隊(duì)列式分支限界法求最大團(tuán) 終止條件 算法的while循環(huán)的終止條件是遇到子集樹中的一個(gè)葉結(jié)點(diǎn)(即n+1層結(jié)點(diǎn))成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。 對于子集樹中的葉結(jié)點(diǎn)，有upperSizecliqueSize。此時(shí)活結(jié)點(diǎn)優(yōu)先隊(duì)列中剩余結(jié)點(diǎn)的upperSize值均不超過當(dāng)前擴(kuò)展結(jié)點(diǎn)的upperSize值，從而進(jìn)一步搜索不可能得到更大的團(tuán)，此時(shí)算法已找到一個(gè)最優(yōu)解。34343優(yōu)先隊(duì)列式分支限界法求最大團(tuán)示例說明1132224333343XX244444444444RXXXXXX55XXXXXXXXXXXXXXXXXXXXXXXXcliqueSize CSupper

10、Size USBestn BNCS=1 BN=1 US=5 CS=0 BN=1 US=40節(jié)點(diǎn) CS=0 BN=0 US=5CS=2 BN=2 US=5CS=1 BN=2 US=4CS=1BN=2 US=3CS=1 BN=2 US=4CS=0 BN=2 US=312345678910111213141516R1112223CS=2 BN=2 US=41222332CS=2 BN=2 US=43CS=2 BN=2 US=334CS=2 BN=2 US=323CS=1 BN=2 US=33CS=0 BN=2 US=234CS=1BN=2 US=24CS=2 BN=2 US=35CS=3 BN=3 US=3CS=US 出現(xiàn)最大團(tuán) BN=3算法比較MCP分支限界法與回溯法的比較MCP應(yīng)用 最大團(tuán)問題是圖論中的一個(gè)經(jīng)