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

1、現(xiàn)實(shí)世界中的很多問(wèn)題如信號(hào)傳輸，投資方案選擇，編碼錯(cuò)誤診斷等都可以抽象為最大團(tuán)問(wèn)題（MCP，Maximum Clique Problem），此外，最大團(tuán)問(wèn)題在模式識(shí)別，計(jì)算機(jī)視覺(jué)等領(lǐng)域均有應(yīng)用。最大團(tuán)問(wèn)題是組合優(yōu)化問(wèn)題領(lǐng)域中一個(gè)非常經(jīng)典的NP-完全問(wèn)題，研究最大團(tuán)問(wèn)題具有很高的實(shí)踐意義和理論意義。
　　最大團(tuán)問(wèn)題的求解目標(biāo)是在一個(gè)給定的無(wú)向圖中尋找一個(gè)規(guī)模最大的完全子圖，其求解算法可以分為兩類(lèi)：精確算法和啟發(fā)式算法。啟發(fā)式算法是一

2、種非確定性的算法，能夠在較短的時(shí)間內(nèi)找出問(wèn)題的一個(gè)近似解，但是這個(gè)近似解不一定是最優(yōu)解。精確算法則沒(méi)有這個(gè)缺陷，理論上，在時(shí)間足夠長(zhǎng)的前提下，精確算法可以解決任意難度的最大團(tuán)問(wèn)題。其中，最大團(tuán)問(wèn)題的精確算法是本文的主要研究對(duì)象。
　　本文仔細(xì)分析了目前主流的精確算法，如C&P，MCQ，MaxCliqueDyn等。分析結(jié)果指出，最大團(tuán)的精確算法的具有改進(jìn)潛力的方向有三個(gè)：1，改變分支頂點(diǎn)的選擇順序；2，改進(jìn)算法的初始下界；3，改進(jìn)劃

3、分后子圖中的上界估值。本文在這三個(gè)方面分別做了實(shí)驗(yàn)和分析，并且相應(yīng)地提出了一種新的精確算法MMC。MMC算法借鑒了其他算法的優(yōu)勢(shì)，引入ICE策略改進(jìn)初始LB，并且使用LRSP策略執(zhí)行頂點(diǎn)的重排序。
　　測(cè)試DIMACS標(biāo)準(zhǔn)算例表明，算法MMC對(duì)于部分算例如gen400_p0.9_55，gen400_p0.9_65，gen400_p0.9_75其效率有顯著提升，同時(shí)，MMC算法的平均效率也優(yōu)于目前大部分最大團(tuán)精確算法。因此，可以認(rèn)為