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

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

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

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