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

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

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

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

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

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

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

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

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