關(guān)于最大團(tuán)問題的分支搜索算法的優(yōu)化.pdf

1、最大團(tuán)問題是圖論中的經(jīng)典組合優(yōu)化問題，雖然描述簡單，但是非常復(fù)雜難解，屬于一類NP-完全問題。最大團(tuán)問題與圖論中許多經(jīng)典問題有十分密切的關(guān)系，可以在多項式時間內(nèi)轉(zhuǎn)換成最大獨立集問題、最小頂點覆蓋問題、最小著色問題、背包問題以及貨郎擔(dān)問題等經(jīng)典問題。最大團(tuán)問題的研究對于解決圖論中的眾多問題有著重要意義。作為圖論中經(jīng)典的組合優(yōu)化問題，最大團(tuán)問題與人們的現(xiàn)實生活關(guān)系十分密切，在實踐生活中廣泛應(yīng)用于人員活動的安排、市場分析方案的選擇，機(jī)器故障的

2、診斷以及信號傳輸?shù)仍S多應(yīng)用領(lǐng)域。因此，最大團(tuán)問題的研究有著巨大的實際應(yīng)用價值。最大團(tuán)的問題的算法分為確定性算法和非確定性算法兩類。確定性算法要求程序在有效的時間內(nèi)給出最大團(tuán)問題的最優(yōu)解，而非確定性的算法并不保證最終程序給出的是最優(yōu)解。最大團(tuán)問題是NP-完全問題，當(dāng)無向圖規(guī)模較大時在有效時間內(nèi)可能無法計算出最優(yōu)解，非確定性算法可以在有限時間內(nèi)給出無向圖的最大團(tuán)問題最優(yōu)解的一個近似解。
　　本文首先對最大團(tuán)問題的應(yīng)用背景進(jìn)行了簡單的介

3、紹。描述了當(dāng)前對于無向圖中查找最大團(tuán)問題的研究成果，并對當(dāng)前關(guān)于最大團(tuán)問題的主流解法進(jìn)行了論述。對最大團(tuán)問題確定性算法中的分支搜索算法做了詳細(xì)的分析和研究。關(guān)于分支搜索算法求解最大團(tuán)問題的關(guān)鍵在于對無向圖的劃分和對劃分后生成的子圖中存在的團(tuán)上界以及下界的估計。無向圖劃分目的是將規(guī)模大的無向圖劃分成盡可能小的子圖，最大化的降低最大團(tuán)問題的規(guī)模。對于劃分子圖的上界估計可以提高剪枝效率，縮小在無向圖中查找最大團(tuán)時的搜索空間，從而提高搜索的速率