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

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

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

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