最大團(tuán)問題精確算法研究.pdf

1、在無向圖G=(V，E)中，團(tuán)（ clique)指圖 G的一個完全子圖，在這個子圖中的任意兩個頂點(diǎn)之間都有邊連接。最大團(tuán)問題（Maximum Clique Problem)指在給定的圖 G中找出包含頂點(diǎn)個數(shù)最多的一個團(tuán)。最大團(tuán)問題是經(jīng)典的N P難度問題，其對應(yīng)的判定問題：給定無向圖G和整數(shù) A;，判斷圖 G中是否存在大小為A:的團(tuán)，是 N P完全間題。最大團(tuán)問題在故障診斷、生物信息學(xué)、編碼理論、計算機(jī)視覺、組合拍賣、經(jīng)濟(jì)學(xué)分析、社會網(wǎng)絡(luò)分

2、析等實際問題中存在著廣泛的應(yīng)用，與最大獨(dú)立集、最小頂點(diǎn)覆蓋、圖染色等其它經(jīng)典的NP難度問題也密切相關(guān)。研究最大團(tuán)問題的求解算法具有重要的理論意義和應(yīng)用價值。
　　當(dāng)前求解最大團(tuán)問題的算法主要分為兩類：啟發(fā)式算法和精確算法。啟發(fā)式算法通常能在較短的時間內(nèi)給出質(zhì)量相對較高的解，但無法保證解的最優(yōu)性。精確算法通過系統(tǒng)搜索問題的整個解空間，從而保證最終得到的解為全局最優(yōu)解。盡管從理論分析上看，現(xiàn)有的最大團(tuán)精確算法在最壞情況下的時間復(fù)雜度無

3、一例外都是指數(shù)級的，但近年來的研究進(jìn)步使得精確算法的實際求解能力得到顯著提升。
　　本文研究基于分支定界方案的最大團(tuán)精確算法。論文工作緊緊圍繞分支與定界這兩個決定算法性能的關(guān)鍵策略展開。具體工作體現(xiàn)在以下四個方面：
　　(一）在標(biāo)準(zhǔn) MaxSAT推理的基礎(chǔ)上，提出了更加高效的漸進(jìn)MaxSAT推理技術(shù)用于減少分支頂點(diǎn)數(shù)量。對圖進(jìn)行近似頂點(diǎn)染色是估計最大團(tuán)上界的經(jīng)典方法。但近似染色數(shù)上界與最大團(tuán)的實際值之間往往存在較大差距。標(biāo)準(zhǔn)

4、 MaxSAT推理將頂點(diǎn)的染色結(jié)果編碼成MaxSAT公式，利用 MaxSAT推理技術(shù)來計算更加精確的上界。盡管標(biāo)準(zhǔn)MaxSAT推理能顯著減少搜索樹大小，但對搜索樹的剪枝作用仍存在“全或無”的顯著特征。本文從設(shè)計思路上將MaxSAT推理的目標(biāo)從改進(jìn)上界估計轉(zhuǎn)變?yōu)闇p少分支頂點(diǎn)數(shù)量，提出了漸進(jìn)MaxSAT推理技術(shù)。實驗表明，漸進(jìn) MaxSAT推理在減少分支數(shù)量方面總是能產(chǎn)生積極效果，與傳統(tǒng)的MaxSAT推理技術(shù)相比效率更高。
　　(二）

5、研究了動態(tài)順序和靜態(tài)順序兩種分支順序策略，提出了混合分支順序策略。結(jié)合漸進(jìn)MaxSAT推理技術(shù)，本文設(shè)計了基于動態(tài)分支順序的DoMC算法和基于靜態(tài)分支順序的 SoMC算法。SoMC算法在保持靜態(tài)分支順序的前提下最小化分支頂點(diǎn)集，而 DoMC允許分支順序動態(tài)變化以使分支頂點(diǎn)集最小化。實驗表明二者在性能上相互補(bǔ)充。基于動態(tài)順序與靜態(tài)順序性能互補(bǔ)的觀察，本文提出了混合分支順序策略，設(shè)計了混合分支順序算法MoMC。實驗結(jié)果表明， DoMC、 S

6、oMC和 MoMC三個算法的總體性能顯著地超越當(dāng)前國際上最好的精確算法。
　　(三）針對大量存在的真實世界稀疏大圖，設(shè)計了簡單高效的預(yù)處理程序。該預(yù)處理程序在單一的過程中高效地完成初始頂點(diǎn)順序計算、初始團(tuán)尋找、圖規(guī)?；喌热楊A(yù)處理任務(wù)。結(jié)合該預(yù)處理程序和漸進(jìn)MaxSAT推理技術(shù)，設(shè)計了針對稀疏大圖的精確算法LMC。實驗表明， LM C能夠快速求解頂點(diǎn)規(guī)模達(dá)到千萬級的真實世界大圖，其性能明顯超越了目前國際上最好的大圖精確算法PM

7、C和 BBMCSP。LMC算法的優(yōu)異表現(xiàn)也駁斥了文獻(xiàn)中關(guān)于MaxSAT推理等高級技術(shù)并不適用于大稀疏圖求解的觀點(diǎn)。
　　(四）針對最大團(tuán)問題的變型一加權(quán)最大團(tuán)問題，設(shè)計了精確算法WLMC。由于頂點(diǎn)之間存在權(quán)重差異，加權(quán)圖中的頂點(diǎn)關(guān)系更加復(fù)雜，使得加權(quán)最大團(tuán)問題的求解難度要顯著地高于非加權(quán)的經(jīng)典最大團(tuán)問題。為簡化頂點(diǎn)之間的復(fù)雜關(guān)系，本文提出了由沖突驅(qū)動的兩個頂點(diǎn)權(quán)重切分規(guī)則：顯式?jīng)_突切分和隱式?jīng)_突切分，并從圖概念的視角直觀地闡述了基

8、于沖突獨(dú)立集探測的上界估計。大量真實世界圖集上的實驗結(jié)果表明， W LMC算法的整體性能表現(xiàn)顯著地超越了當(dāng)前最好的精確算法和啟發(fā)式算法，有力地駁斥了精確算法對解決大規(guī)模圖能力不足的主流觀點(diǎn)。
　　傳統(tǒng)的最大團(tuán)分支定界算法集中關(guān)注如何改進(jìn)上界估計，本文在算法設(shè)計思路上集中關(guān)注如何減少分支數(shù)量。這一設(shè)計思路的轉(zhuǎn)變使得對MaxSAT推理和頂點(diǎn)權(quán)重切分等技術(shù)的運(yùn)用效率更高。該設(shè)計思路也有望用于改進(jìn)其它基于分支定界的組合優(yōu)化問題算法設(shè)計。針