最大团
最大團問題
目錄
編輯本段概述
最大團問題（Maximum Clique Problem, MCP）是圖論中一個經典的組合優化問題，也是一類NP完全問題，在國際上已有廣泛的研究，而國內對MCP問題的研究則還處于起步階段，因此，研究最大團問題具有較高的理論價值和現實意義。 最大團問題又稱為最大獨立集問題（Maximum Independent Set Problem）。目前，求解MCP問題的算法主要分為兩類：確定性算法和啟發式算法。確定性算法有回溯法、分支限界法等，啟發式算法蟻群算法、順序貪婪算法、DLS-MC算法和智能搜索算法等。編輯本段問題描述
給定無向圖G=(V,E)，其中V是非空集合，稱為頂點集；E是V中元素構成的無序二元組的集合，稱為邊集，無向圖中的邊均是頂點的無序對，無序對常用圓括號“( )”表示。如果U∈V，且對任意兩個頂點u，v∈U有(u,v)∈E，則稱U是G的完全子圖。G的完全子圖U是G的團當且僅當U不包含在G的更大的完全子圖中。G的最大團是指G中所含頂點數最多的團。 如果U∈V且對任意u，v∈U有(u,v)不屬于E，則稱U是G的空子圖。G的空子圖U是G的獨立集當且僅當U不包含在G的更大的空子圖中。G的最大獨立集是G中所含頂點數最多的獨立集。 對于任一無向圖G=(V,E)，其補圖G'=(V',E')定義為：V'=V，且(u,v)∈E'當且僅當(u,v)?E。 如果U是G的完全子圖，則它也是G'的空子圖，反之亦然。因此，G的團與G'的獨立集之間存在一一對應的關系。特殊地，U是G的最大團當且僅當U是G'的最大獨立集。編輯本段應用背景
MCP問題是現實世界中一類真實問題，在市場分析、方案選擇、信號傳輸、計算機視覺、故障診斷等領域具有非常廣泛的應用。自1957年Hararv和Ross首次提出求解最大團問題的確定性算法以來，研究者們已提出了多種確定性算法來求解最大團問題。但隨著問題規模的增大（頂點增多和邊密度變大），求解問題的時間復雜度越來越高，確定性算法顯得無能為力，不能有效解決這些NP完全問題。 20世紀80年代末，研究者們開始嘗試采用啟發式算法求解最大團問題，提出了各種各樣的啟發式算法，如順序貪婪啟發式算法、遺傳算法、模擬退火算法、禁忌搜索算法、神經網絡算法等，并且取得了令人滿意的效果。在時間上，由于采用了啟發式信息，啟發式算法的運算時間與確定性算法的運算時間之間的比值會隨著圖的頂點、邊密度的增加而變得越來越小。唯一的缺點就是不一定能找到最優值，有時只能找到近優值。 近年來研究表明，單獨使用一種啟發式算法求解最大團問題，算法性能往往并不是很好，因此，常借鑒算法之間優勢互補策略，形成新的混合啟發式算法來求解最大團問題。當前求解該問題最好的啟發式算法有反作用禁忌搜索（Reactive Tabu Search, RTS）算法、基于遺傳算法的簡單啟發式算法（Simple Heuristic Based Genetic Algorithm, HGA）、DLS-MC算法等。編輯本段常用算法
順序貪婪啟發式算法
順序貪婪啟發式算法是最早的求解最大團的啟發式算法。這類算法通過給一個團重復進行加點操作得到一個極大團或者對一組并不是團的子圖重復進行刪除頂點操作以得到一個團。1987年，Kopf和Ruhe把這類型算法分為Best in和Worst out兩類。 (1)Best in方法的基本思路：由一個團出發，和這個團中頂點相連的頂點組成候選集；然后以一定的啟發式信息，從中選擇頂點加入團中，以后反復進行，直到最后得到一個極大團。 (2)Worst out方法的基本思路：從整個頂點集開始，然后按一定的啟發式信息，從中反復進行刪除頂點操作，直到最后得到一個團。 順序貪婪啟發式算法有很大不足，該算法一旦找見一個極大團，搜索就停止，因此找到最大團的概率相對較低。局部搜索啟發式算法
假設SG為圖的所有極大團的集合，由于順序貪婪啟發式算法僅能找見SG中的一個極大團，因此，為了提高解的質量，應當擴大在SG的搜索區域，比如，可以在極大團S的鄰居中繼續進行搜索，以擴大搜索區域，進而提高解的質量。 在局部搜索啟發式算法中，如果搜索S的鄰居越多，提高解的質量的機會就越大。依賴不同的鄰居定義，局部搜索啟發式算法可以得到不同的解。在局部搜索啟發式算法中，比較有名的算法是K-interchange啟發式算法，它是一種基于K-neighbor鄰居實現的，在解集S的K鄰居中進行局部搜索的方法。 分析可知，局部搜索啟發式算法存在一個問題，即僅能夠找見一個局部最優值。所以為了提高求解的質量，常把該算法和其它算法相混合，從而得到求解MCP問題的新的算法。 WaynePullan和HolgerH．Hoos基于這一思想提出了求解最大團問題的DLS-MC算法，該算法是plateau search局部搜索啟發式和算法迭代改善法相混合得到的，算法性能非常好，在該方法中引入了頂點懲罰函數，該函數在算法的求解過程中能夠動態改變；在算法執行過程中迭代改善法和plateau search算法輪流執行來提高解的質量。在基準圖上對該算法進行了測試，性能非常好。智能搜索啟發式算法
智能搜索算法主要有遺傳算法、禁忌算法、模擬退火算法、神經網絡等。遺傳算法
遺傳算法（Genetic Algorithm, GA）是一種基于自然選擇和群體遺傳機理的搜索算法，它模擬了自然選擇和自然遺傳過程中發生的復制、交叉和變異現象。 1993年，Carter和Park首次提出使用遺傳算法求解最大團問題，但由于所求解的質量差，計算復雜度高，因此，他們認為遺傳算法并不適合求解最大團問題。與此同時，Bäck和Khuri致力于最大獨立集問題的求解，卻得到了完全相反的結論，通過選用合適的適應度函數，取得了很好的效果。因此在使用GA來解決最大團問題時，適應度函數起著非常關鍵的作用。此后，基于遺傳算法求解最大團問題的方法逐漸增多，但在提高解的質量，降低算法復雜度上方面卻沒有大幅度的提高。 l998年，Marchiori提出了一種基于遺傳算法的簡單啟發式算法（simple heuristic based genetic algorithm, HGA)。算法由兩部分組成：簡單遺傳算法（simple genetic algorithm, SGA）和簡單的貪婪啟發式局部搜索算法（simple greedy heuristic local search algorithm,SGHLSA）。在基準圖上對算法HGA的性能進行測試，證明了該算法在解的質量和計算速度方面都優于基于遺傳算法的其它算法。 因此，單純使用遺傳算法（改動變異、雜交、選擇等算子）求解最大團問題時，算法的性能是比較差；要提高算法性能，遺傳算法最好能和局部搜索算法相結合。模擬退火算法
模擬退火（Simulated Annealing, SA）算法是N. Metropolis在1953年提出的一種基于物質退火過程的隨機搜索算法，是一種迭代求解的啟發式隨機搜索算法。首先在高溫下較快地進行搜索，使系統進入“熱平衡”狀態，大致地找到系統的低能區域。隨著溫度的逐漸降低，搜索精度不斷提高，可逐漸準確地找到最低能量的基態。作為局部搜索算法的擴展，當鄰域的一次操作使當前解的質量提高時，接受這個改進解作為新的當前解；反之，以一定的概率接受相對質量比較差的解作為新的當前解。 Aarts和Korst提出使用模擬退火算法來解決獨立集問題，建議在算法設計時引入懲罰函數，但卻沒有提供任何的實驗結果。問題的解空間S是圖G的全部可能的子圖，并不要求是獨立集，對于任一子圖G*，成本函數為f(V')=|V'|-k|E'|，其中V'是圖G*的頂點集，E'是圖G*的邊集，k是權因子（k>1）。選擇鄰居時，費用值大的將被選中，因此求解最大獨立集問題也就是最大化成本函數問題。 Homer和Peinado把模擬退火算法和Johnson的貪婪啟發式算法、Boppan的隨機化算法、Halldorsson的子圖排除法3種啟發式算法進行比較，結果比這3種算法要好很多?？傊?#xff0c;模擬退火算法在處理最大團問題上是一個非常好的算法。禁忌算法
禁忌算法（Tabu Algorithm）是一種改進的局部搜索算法。該算法為了避免在搜索過程中出現死循環和開發新的搜索區域，采用了一種基于禁止的策略。 1989年，Friden提出了基于禁忌搜索的求解最大獨立集的啟發式算法，獨立集的大小固定，該算法的目標是最小化當前子集（解）頂點之間的邊數。使用3個禁忌表：其中，一個禁忌表用來存放上一代的解，另外兩個分別存放剛進入解頂點和剛被刪去的頂點。 基于禁忌算法求解最大團問題具有代表性的是Batti和Protasi提出的反作用局部搜索（Reaction Local Search, RLS）算法，通過引入局部搜索算法，擴展了禁忌搜索的框架。與一般禁忌搜索算法相比，該算法的特點是：在執行過程中，根據所得到的解的情況形成一種內部反饋機制以控制調整算法的控制參數，所以該算法的控制參數是動態變化的；比如，禁止表長度參數是動態變化的，因此禁忌表長度是動態變化的。他們在DIMACS的基準圖上對算法性能進行測試，取得非常好的效果。神經網絡算法
人工神經網絡指為了模擬生物大腦的結構和功能而構成的一種大型的、分布式系統，它有很強的自組織性、自適應性和學習能力。 20個世紀80年代末期，Ballard、Godbeerl、Ramanujam和Sadayappan等都嘗試對最大團和相關問題按人工神經網絡進行編碼，進而求解該問題。然而，這些研究只提供了很少的實驗結果。 Grossman提出一種離散的/確定性的Hopfield模型來求解最大團。這個模型有一個用來決定網絡是否處于穩定態的臨界值參數。Grossman建議在這個參數上使用退火策略，并且使用自適應機制選擇網絡的初始狀態和臨界值。在DIMACS基準圖上測試，得到比較好的結果，但與性能好的啟發式算法相比，其結果較差，比如結果要差于模擬退火算法。1995年Jagota對Hopfield模型進行了多處修改來近似求解最大團問題，其中有的是離散化的，有的是連續的；雖然有了一定改進，但是性能并沒有顯著提高。隨后，仍然有好多研究者使用Hopfield神經網絡來求解最大團問題，但是與其它智能搜索算法相比，效果比較差。 研究表明：(1) 前3種智能搜索算法適合求解MCP，而通過神經網絡算法求解MCP時的性能比較差；(2) 單獨使用智能搜索算法來求解MCP，算法性能并不好，因此，常和局部搜索算法相結合形成新的混合算法，比如：禁忌算法與局部搜索算法相混合形成的反作用禁忌搜索算法，遺傳算法與局部搜索算法相混合形成的簡單啟發式算法等。改進蟻群算法-AntMCP
蟻群算法是由Dorigo M.等人依據模仿真實的蟻群行為而提出的一種模擬進化算法。螞蟻之間是通過一種稱為信息素（Pheromone）的物質傳遞信息的，螞蟻能夠在經過的路徑上留下該種物質，而且能夠感知這種物質的存在及其強度，并以此來指導自己的運動方向。因此，由大量螞蟻組成的集體行為便表現出一種信息正反饋現象：某一條路徑上走過的螞蟻越多，該路徑上留下的信息素就越多，則后來者選擇該路徑的概率就越大。螞蟻之間就是通過這種信息素的交流，搜索到一條從蟻巢到食物源的最短路徑。 2003年，Fenet和Solnon提出了求解最大團問題的蟻群算法AntClique，該算法仍然將信息素留在邊上，信息素tij是指把結點i和結點j分配到同一個團中的期望。由于沒有使用局部啟發信息，這使得迭代初期各候選頂點的選擇概率幾乎相等，這樣算法在迭代初期有一定的盲目性，往往需要更多的迭代次數才能得到最優解。針對這些不足及最大團問題的特點，曾艷于2010年提出了改進的蟻群算法-AntMCP。 算法偽代碼描述如下： Procedure Vertex_AntClique Initialize //初始化信息素和局部啟發信息 Repeat For k in 1...nbAnts do: Choose randomly a first vertex v f∈V Ck←{v f } Candidate ¬{v i |(v f,v i) ∈E} While Candidate≠0 do Choose a vertex v i∈Candidate withprobability p(v i); Ck←Ck∪{v i} Candidate ←Candidate ∩{v j |(vi,v j) ∈E} End of while Endof for Updatepheromone w.r.t {C1,…,CnbAnts} Until max cyclesreached or optimal solution found End of procedure 在AntMCP中，增加了局部啟發信息；信息素t和啟發信息h不是留在邊上，而是留在頂點上。這樣，變量t和h由二維降為一維，既可節省存儲空間，又可提高運行速度，大量實驗表明，該算法運算速度更快，效率更高。其它啟發式算法
除上述幾種啟發式算法外，目前研究者們還提出了一些新的算法。當圖的頂點數不大于閾值M時，稱此圖為低度圖，求解低度圖的最大團問題的時間復雜度為O(d)，基于這一思想，王青松和范鐵生提出了一種求解低度圖的最大團的確定性算法。在該算法中，通過對圖按頂點逐步分解實現分別計算，較好地解決了低度圖的最大團問題，算法的時間復雜度為O(d*n^3)。針對遺傳算法在最大團求解中保持群體多樣性能力不足、早熟、耗時長、成功率高等缺陷，依據均勻設計抽樣理論對交叉操作進行重新設計，結合免疫機理定義染色體濃度設計克隆選擇策略，周本達、岳芹等提出了一種求解最大團問題的均價設計抽樣免疫遺傳算法。仿真算例表明，該算法在解的質量、收斂速度等各項指標上均有提高，與DLS-MC、QUALEX等經典搜索算法相比，對部分算例能得到更好解。吳冬輝和馬良提出了基于遺傳算法的最大團問題求解算法，通過引入概率模型指導變異產生新的個體，并結合啟發式局部算法搜索最大團。實例結果驗證了該算法的有效性。針對求解最大團問題的分層的邊權網絡（Hierarchical Edge-Weight Network,HEWN）算法，郭長庚和潘曉偉設計了一個實現HEWN算法的數據結構，指出在HEWN算法中HEWN算法的存儲宜采用鄰接多重表和二叉表相結合的鏈表表示法，并進行了時間復雜度分析，得出HEWN算法的時間復雜度是指數級而不是O(n^8.5)。針對基于適應值的選擇交叉機制在優化具有欺騙性的最大團問題中性能退化的問題，張雁、黨群等提出了一種新的基于匹配教程的Memetic算法。算法中提出交叉匹配度的概念，用來估計兩個體交叉所能獲得的最佳適應值。通過匹配度的計算對交叉方向的選擇進行控制，保證了交叉操作以較大的概率生成新的優良模式。測試結果表明，該算法優于目前在最大團問題求解中性能最好的多階段動態局部搜索算法。DNA計算是應用分子生物技術進行計算的新方法，具有高度并行性、大容量、低能耗等特點。針對這一特點，李濤提出了用DNA算法求解最大團問題，開創了以生物技術為工具解決復雜問題的新紀元，為解決NP完全問題開辟了一條新途徑?；趯φ迟N模型的組成、基本實驗及其生化實現過程的分析，根據最大團問題的需求，周康、劉朔等在粘貼模型中，提出了基于電泳技術和分離實驗的DNA序列檢測方法?；诜蛛x實驗提出了一種求解最大團問題的DNA算法，并給出了其生化實現過程。為了提高交叉熵算法求解最大團問題的性能，呂強、柏戰華等提出了一種領導者-跟隨者協作求解的并行策略來實現交叉熵算法，從而達到減少計算時間和保障解的質量兩者的平衡。算法中領導者活躍在并行處理器之間采集數據，并根據當前獲得信息對跟隨者作出決策；受控的跟隨者則主要根據領導者的決策信息自適應地調整搜索空間，完成各自的集團產生任務。實驗結果表明該算法較基于種群的啟發式算法有一定的性能改善。回溯法
回溯法（BacktrackingAlgorithm, BA）有“通用的解題法”之稱，用它可以系統地搜索一個問題的所有解或任一解，是一個既帶有系統性又帶有跳躍性的搜索算法。在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按照深度優先的策略進行搜索。BA在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而BA在用來求問題的任一解時，只要搜索到問題的一個解即可結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用于解一些組合數較大的問題。 回溯法搜索解空間樹時，根節點首先成為一個活結點，同時也成為當前的擴展節點。在當前擴展節點處，搜索向縱深方向移至一個新節點。這個新節點就成為一個新的活結點，并成為當前擴展節點。如果當前擴展節點不能再向縱深方向移動，則當前的擴展節點就成為死結點。此時，往回回溯至最近的一個活節點處，并使這個活結點成為當前的擴展節點。 回溯法以這種方式遞歸地在解空間中搜索，直至找到所有要求的解或解空間已無活結點為止。 搜索：回溯法從根結點出發，按深度優先策略遍歷解空間樹，搜索滿足約束條件的解。 剪枝：在搜索至樹中任一結點時，先判斷該結點對應的部分解是否滿足約束條件，或者是否超出目標函數的界；也即判斷該結點是否包含問題的解，如果肯定不包含，則跳過對以該結點為根的子樹的搜索，即剪枝（Pruning）；否則，進入以該結點為根的子樹，繼續按照深度優先的策略搜索。 一般來講，回溯法求解問題的基本步驟如下： (1)針對所給問題，定義問題的解空間；確定易于搜索的解空間結構；以深度優先方式搜索解空間，并在搜索過程中利用Pruning函數剪去無效的搜索。 (2)無向圖G的最大團問題可以看作是圖G的頂點集V的子集選取問題。因此可以用子集樹表示問題的解空間。設當前擴展節點Z位于解空間樹的第i層。在進入左子樹前，必須確認從頂點i到已入選的頂點集中每一個頂點都有邊相連。在進入右子樹之前，必須確認還有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。 (3)用鄰接矩陣表示圖G，n為G的頂點數，cn存儲當前團的頂點數，bestn存儲最大團的頂點數。cn+n-i為進入右子樹的上界函數，當cn+n-i<bestn時，不能在右子樹中找到更大的團，利用剪枝函數可將Z的右結點剪去。 實例分析圖1
如圖1所示，給定無向圖G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。根據MCP定義，子集{1,2}是圖G的一個大小為2的完全子圖，但不是一個團，因為它包含于G的更大的完全子圖{1,2,5}之中。{1,2,5}是G的一個最大團。{1,4,5}和{2,3,5}也是G的最大團。圖2是無向圖G的補圖G'。根據最大獨立集定義，{2,4}是G的一個空子圖，同時也是G的一個最大獨立集。雖然{1,2}也是G'的空子圖，但它不是G'的獨立集，因為它包含在G'的空子圖{1,2,5}中。{1,2,5}是G'的最大獨立集。{1,4,5}和{2,3,5}也是G'的最大圖2
獨立集。以圖1為例，利用回溯法搜索其空間樹，具體搜索過程（見圖3所示）如下：假設我們按照1®2®3®4®5的順序深度搜索。開始時，根結點R是唯一活結點，也是當前擴展結點，位于第1層，此時當前團的頂點數cn=0，最大團的頂點數bestn=0。在這個擴展結點處，我們假定R和第二層的頂點1之間有邊相連，則沿縱深方向移至頂點1處。此時結點R和頂點1都是活結點，頂點1成為當前的擴展結點。此時當前團的頂點數cn=1，最大團的頂點數bestn=0。繼續深度搜索至第3層頂點2處，此時頂點1和2有邊相連，都是活結點，頂點2成為當前擴展結點。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜索至第4層頂點3處，由于頂點3和2有邊相連但與頂點1無邊相連，則利用剪枝函數剪去該枝，此時由于cn+n-i=2+5-4=3>bestn=0，則回溯到結點2處進入右子樹，開始搜索。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜索至第5層頂點4處，由于頂點3和4無邊相連，剪去該枝，回溯到結點3處進入右子樹，此時當前團的頂點數cn=2，最大團的頂點數bestn=0。繼續深度搜索至第6層頂點5處，由于頂點5和4有邊相連，且與頂點1和2都有邊相連，則進入左子樹搜索。由于結點5是一個葉結點，故我們得到一個可行解，此時當前團的頂點數cn=3，最大團的頂點數bestn=3。vi的取值由頂點1至頂點5所唯一確定，即v=(1, 2, 5)。此時頂點5已不能再縱深擴展，成為死結點，我們返回到結點4處。由于此時cn+n-i=3+5-6=2<bestn=3，不能在右子樹中找到更大的團，利用剪枝函數可將結點4的右結點剪去。以此回溯，直至根結點R再次成為當前的擴展結點，沿著右子樹的縱深方向移動，直至遍歷整個解空間。最后得到圖1的按照1®2®3®4®5的順序深度搜索的最大團為U={1,2,5}。當然{1,4,5}和{2,3,5}也是其最大團。圖3
C++ 代碼 //MaxClique.cpp : 定義控制臺應用程序的入口點。 /* 回溯法求解最大團問題 */ #include <fstream> #include <iostream> #include <stdlib.h> #include <conio.h> using namespace std; #define MAX_v 50 //定義一個最大頂點個數 typedef struct{ int a[MAX_v][MAX_v]; //無向圖G的鄰接矩陣 int v; //無向圖G的頂點 int e; //無向圖G的邊 int x[50]; //頂點與當前團的連接，x[i]=1 表示有連接 int bestx[50]; //當前最優解 int cnum; //當前團的頂點數目 int bestn; //最大團的頂點數目 }MCP; void Creat(MCP &G); void Backtrack(MCP &G,int i); void Creat(MCP &G){ int i,j; ifstream fin("data.txt"); if (!fin) { cout<<"不能打開文件:"<<"data.txt"<<endl; exit(1); } fin>>G.v; for (int i=1;i<=G.v;i++) for (int j=1;j<=G.v;j++) fin>>G.a[i][j]; for(i=1;i<=G.v;i++) //初始化 { G.bestx[i]=0; G.x[i]=0; G.bestn=0; G.cnum=0; } cout<<"————————————————"<<endl; cout<<"———回溯法求解最大團問題———"<<endl; cout<<"————————————————"<<endl; cout<<"輸入初始化無向圖矩陣為:"<<endl; //初始化 for(i=1;i<=G.v;i++) { for(j=1;j<=G.v;j++) cout<<G.a[i][j]<<" "; cout<<endl; } } void Backtrack(MCP &G,int i){ if (i>G.v){ for (int j=1; j<=G.v; j++) G.bestx[j] = G.x[j]; G.bestn =G.cnum; return ; } //檢查頂點i與當前團的連接 int OK = 1; for (int j=1; j<=i ; j++) if (G.x[j]&& G.a[i][j]==0){ //i不與j相連 OK = 0; break; } if (OK) { G.x[i] = 1;//把i加入團 G.cnum++; Backtrack(G,i+1); G.x[i]=0; G.cnum-- ; } if (G.cnum+G.v- i>G.bestn){ G.x[i] = 0; Backtrack(G,i+1); } } int main(){ MCP G; Creat(G); Backtrack(G,1); cout<<"最大團包含的頂點數為:"<<G.bestn<<endl; cout<<"最大團方案為:( "; for (int i=1;i<=G.v;i++) if(G.bestx[i]==1){ cout<<i<<" "; } cout<<")"<<endl; getch(); }分支限界法
分支限界（Brandand Bound）法類似于回溯法，也是一種在問題的解空間樹上搜索問題的解的算法。 分支限界法常以廣度優先或最小耗費（最大效益）優先的方式搜索解空間樹。在分支限界法中，每一個活結點只有一次機會成為擴展結點。一旦活結點成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，舍棄那些導致不可行解或導致非最優解的兒子結點，將其余兒子結點加入活結點表中。此后，從活結點表中取下一個結點成為當前擴展結點，并重復上述結點擴展過程，直至找到所需的解或活結點表為空時為止。 具體來講，分支限界法由“分支”策略和“限界”策略兩部分組成?！胺种А斌w現在對問題空間是按廣度優先搜索；“限界”策略是為了加速搜索速度而采用啟發式剪枝的策略。分支搜索法采用廣度優先的策略，依次生成E結點所有分支（即所有的子結點）。在生成的結點中，將采用更有效的約束函數（限界函數）控制搜索路徑，去除那些不滿足約束條件（即不可能導出最優解）的結點，使之能更好地朝著狀態空間樹上有最優解的分支推進。 根據從活結點表中選擇下一個擴展結點的方式的不同，分支限界法主要分為以下兩類： 1.隊列式（FIFO）分支限界法 隊列式分支限界法將活結點表組織成一個隊列，并按隊列的FIFO原則選取下一個結點成為當前擴展結點。具體流程為： A.初始化，根結點是唯一的活結點，根結點入隊。 B.從活結點隊中取出根結點后，作為當前E結點。對當前E結點，先從左到右地產生它的所有兒子，用約束條件檢查，把所有滿足約束函數的兒子加入活結點隊列中。 C.重復上述過程：再從活結點表中取出隊首結點（隊中最先進來的結點）為當前E結點，……；直到找到一個解或活結點隊列為空為止。 2.優先隊列式分支限界法 優先隊列式分支限界法將活結點表組織成一個優先隊列，并按優先隊列中規定的結點優先級選取優先級最高的下一個結點成為當前擴展結點。具體流程為：對每一活結點計算一個優先級，并根據這些優先級，從當前活結點表中優先選擇一個優先級最高（最有利）的結點作為擴展結點，使搜索朝著解空間樹上有最優解的分支推進，以便盡快地找出一個最優解。 C++ 代碼 //MaxClique_BB.cpp : 定義控制臺應用程序的入口點。 /* 分支限界法求解最大團問題 */ #include <fstream> #include <iostream> #include <queue> #include <conio.h> using namespace std; typedef struct{ int v; //無向圖G的頂點 int e; //無向圖G的邊 int a[50][50]; //定義圖G的鄰接矩陣 int bestx[50]; //最優解 }MCP; void Creat(MCP &G){ int i,j; ifstream fin("data.txt"); if(!fin) { cout<<"不能打開文件:"<<"data.txt"<<endl; exit(1); } fin>>G.v; for(int i=1;i<=G.v;i++) for(int j=1;j<=G.v;j++) fin>>G.a[i][j]; for(i=1;i<=G.v;i++) //初始化 { G.bestx[i]=0; } cout<<"————————————————————————"<<endl; cout<<"———優先隊列式分支限界法求解最大團問題———"<<endl; cout<<"————————————————————————"<<endl; cout<<"輸入初始化無向圖矩陣為:"<<endl; //初始化 for(i=1;i<=G.v;i++) { for(j=1;j<=G.v;j++) cout<<G.a[i][j]<<" "; cout<<endl; } } struct BBNode { BBNode *parent; //指向父結點的指針 bool LChild; //左兒子結點標志 }; struct CliqueNode //定義優先隊列類型為CliqueNode { int cnum; //當前團的頂點數 int un; //當前團最大頂點數的上界 int level; //結點在子集空間樹種所處的層次 BBNode *p; //指向活結點在子集樹中相應結點的指針 bool operator<(const CliqueNode &b) const //<號重載建立大根堆 { if (b.un>un) return true; if (b.un==un&& b.cnum>cnum) return true; else return false; } }; void BBMaxClique(MCP&G) { BBNode *E=new(BBNode); //定義B代表記錄的隊列情況 //初始化 int j,i=1; int cnum=0,bestn=0; int OK=1; priority_queue<CliqueNode> Q; //定義優先隊列Q E->LChild=false; //初始化 E->parent=NULL; while(i!=G.v+1)//非葉結點 { //檢查頂點i與當前團中其它頂點之間是否有邊相連 OK=1; BBNode *B=E; //把當前點的數據給B，B為中間變量 for(j=i-1;j>0;B=B->parent,j--) if(B->LChild&& G.a[i][j]==0) //如果不滿足就停止 { OK=0; break; } if(OK) //滿足條件，即左兒子結點為可行結點 { CliqueNode *D=new(CliqueNode); //定義一個節點D D->p=new(BBNode); if(cnum+1>bestn)bestn=cnum+1; D->cnum=cnum+1; D->level=i+1; D->p->LChild=true; D->p->parent=E; D->un=cnum+1+G.v-i; Q.push(*D); //進隊列 } if(cnum+G.v-i>bestn) //不滿足條件但是還是可能有最優解 { CliqueNode *D=new(CliqueNode); //定義一個節點D D->p=new(BBNode); D->cnum=cnum; D->level=i+1; D->p->LChild=false; D->p->parent=E; D->un=cnum+G.v-i; Q.push(*D); //進隊列 } CliqueNode N; N=Q.top(); //取隊頂元素，最大堆 Q.pop(); //刪除隊頂元素 E=N.p; //記錄當前團的信息 cnum=N.cnum; //記錄當前團的頂點數 i=N.level; //所在的層次 } for(j=G.v;j>0;j--) //保存最優解 { G.bestx[j]=E->LChild; E=E->parent; bestn=cnum; } } int main(){ MCP G; Creat(G); BBMaxClique(G); cout<<"最大團方案為:("; for(int i=G.v;i>0;i--) if (G.bestx[i]==1){ cout<<i<<" "; } cout<<")"<<endl; getch(); } [1]poj1129_四色問題
題意：染色問題，圖中之間有邊的兩個區域不能染成相同的顏色。求將圖中每個區域全部染色后需要最少的顏色。
分析：參考染色定理得，無論圖中有多少區域，最多需要4個區域。因此遍歷這四種情況即可.
代碼：
另一種方法是最大團，我用最大團做完之后發現，其實這個題用最大團的解法是錯誤的。比如：
5
A:BE
B:AC
C:BD
D:CE
E:AD
這組數據用最大團做，ans=2,但是這個題的答案應該是3.可見這個題的數據有問題，最大團的代碼見下、
View Code 1 #include <iostream> 2 #include <stdio.h> 3 #include <memory.h> 4 using namespace std; 5 //148K 0MS 6 7 const int maxnum=27; 8 bool array[maxnum][maxnum]; 9 int use[maxnum]; 10 int num,cn,bestn; 11 12 13 void dfs(int i) 14 { 15 if(i>num) 16 { 17 bestn=cn; 18 return ; 19 } 20 bool flag=true; 21 int j; 22 for(j=1;j<i;j++) 23 if(use[j] && !array[j][i]) 24 { 25 flag=false; 26 break; 27 } 28 if(flag) 29 { 30 cn++; 31 use[i]=true; 32 dfs(i+1); 33 cn--; 34 use[i]=false; 35 } 36 if(cn+num-i>bestn) 37 { 38 use[i]=false; 39 dfs(i+1); 40 } 41 } 42 43 int main() 44 { 45 int i; 46 char ch,tch; 47 while(scanf("%d",&num)&& num!=0) 48 { 49 memset(array,false,sizeof(array)); 50 memset(use,false,sizeof(use)); 51 cn=0; 52 bestn=0; 53 getchar(); 54 for(i=0;i<num;i++) 55 { 56 scanf("%c%c",&ch,&tch); 57 int a=ch-'A'+1; 58 while(scanf("%c",&ch) && ch!='\n') 59 { 60 int b=ch-'A'+1; 61 array[a][b]=true; 62 array[b][a]=true; 63 } 64 } 65 dfs(1); 66 if(bestn==1) 67 printf("1 channel needed.\n"); 68 else 69 printf("%d channels needed.\n",bestn); 70 } 71 return 0; 72 } 73 /* 74 6 75 A:BEF 76 B:AC 77 C:BD 78 D:CEF 79 E:ADF 80 F:ADE 81 */tju oj 1077
poj3692_最大團_二分圖
題意：已知班級有g個女孩和b個男孩，所有女生之間都相互認識，所有男生之間也相互認識，給出m對關系表示哪個女孩與哪個男孩認識?，F在要選擇一些學生來組成一個團，使得里面所有人都認識，求此團最大人數。
思路：最大團問題。
定理：
原圖的最大團=補圖的最大獨立集
原圖的最大獨立集=補圖的最大團。
由于這個題的補圖顯然是一個二分圖，而二分圖的補圖的最大獨立集可以由匈牙利算法求的，所以該題的最大團問題可以轉化成補圖的最大獨立集來做。
代碼：
View Code 1 #include <iostream> 2 #include <stdio.h> 3 #include <memory.h> 4 using namespace std; 5 const int maxnum=201; 6 bool array[maxnum][maxnum]; 7 bool use[maxnum]; 8 int res[maxnum]; 9 int b,g,m; 10 11 bool find(int i) 12 { 13 int j; 14 for(j=1;j<=b;j++) 15 { 16 if(!use[j] && array[i][j]) 17 { 18 use[j]=true; 19 if(res[j]==0 || find(res[j])) 20 { 21 res[j]=i; 22 return true; 23 } 24 } 25 } 26 return false; 27 } 28 29 int main() 30 { 31 int p,q; 32 int i,ans; 33 int k=0; 34 while(scanf("%d%d%d",&g,&b,&m)!=EOF) 35 { 36 if(g==0 && b==0 && m==0) 37 break; 38 memset(array,true,sizeof(array)); 39 memset(res,0,sizeof(res)); 40 for(i=0;i<m;i++) 41 { 42 scanf("%d%d",&p,&q); 43 array[p][q]=false; //補圖 44 } 45 ans=0; 46 for(i=1;i<=g;i++) 47 { 48 memset(use,false,sizeof(use)); 49 if(find(i)) 50 ans++; 51 } 52 k++; 53 printf("Case %d: %d\n",k,b+g-ans); 54 } 55 return 0; 56 }poj1419_染色_最大獨立集_最大團
題意：
經典的圖的染色問題，求對于給定的無向圖中，給每個結點染兩種不同顏色（黑色和白色）的一種且相鄰結點的顏色不同，求染成黑色的最多結點數。
分析：
這個題求的圖的最大獨立集，最大獨立集即為黑色節點的個數。
由于原圖的最大獨立集=補圖的最大團。
而這個題是普通圖，所以用回溯法來做，時間復雜度O(n*2^n)
代碼：
View Code 1 #include <iostream> 2 #include <memory.h> 3 #include <stdio.h> 4 using namespace std; 5 6 const int maxnum=101; 7 bool array[maxnum][maxnum]; 8 bool use[maxnum]; //進入團的標號 9 bool bestx[maxnum]; 10 int cn,bestn,p,e; 11 12 void dfs(int i) 13 { 14 int j; 15 bool flag; 16 17 if(i>p) 18 { 19 bestn=cn; //cn的值是遞增的 20 // printf("%d\n",bestn); 21 // for(j=1;j<=p;j++) 22 // if(use[j]) 23 // printf("%d ",j); 24 // printf("\n"); 在這里輸出不一定是最大團 25 for(j=1;j<=p;j++) //而是應該賦值給另外一個數組， 26 bestx[j]=use[j]; 27 return ; 28 } 29 30 flag=true; 31 for(j=1;j<i;j++) 32 if(use[j]&&!array[j][i]) 33 { 34 flag=false; 35 break; 36 } 37 if(flag) 38 { 39 cn++; 40 use[i]=true; 41 dfs(i+1); 42 cn--; 43 } 44 if(cn+p-i>bestn) //剪枝 45 { 46 use[i]=false; 47 dfs(i+1); 48 } 49 } 50 51 int main() 52 { 53 int num,i,u,v; 54 scanf("%d",&num); 55 while(num--) 56 { 57 memset(array,true,sizeof(array)); 58 memset(use,false,sizeof(use)); 59 memset(bestx,false,sizeof(bestx)); 60 scanf("%d%d",&p,&e); 61 for(i=0;i<e;i++) 62 { 63 scanf("%d%d",&u,&v); 64 array[u][v]=false; 65 array[v][u]=false; 66 } 67 68 cn=bestn=0; 69 dfs(1); 70 printf("%d\n",bestn); 71 for (i=1; i<=p; i++) 72 if(bestx[i]) 73 printf("%d ",i); 74 printf("\n"); 75 } 76 77 return 0; 78 } 79 80 /* 81 1 82 5 7 83 1 2 84 1 4 85 1 5 86 2 3 87 2 5 88 3 5 89 4 5 90 */最大團
問題描述：團就是最大完全子圖。
給定無向圖G=(V,E)。如果UV，且對任意u，vU 有(u，v) E，則稱U 是G 的完全子圖。
G 的完全子圖U是G的團當且僅當U不包含在G 的更大的完全子圖中，即U就是最大完全子圖。
G 的最大團是指G中所含頂點數最多的團。
例如：
(a) (b) (c) (d)
圖a是一個無向圖，圖b、c、d都是圖a的團，且都是最大團。
求最大團的思路：
首先設最大團為一個空團，往其中加入一個頂點，然后依次考慮每個頂點，查看該頂點加入團之后仍然構成一個團，如果可以，考慮將該頂點加入團或者舍棄兩種情況，如果不行，直接舍棄，然后遞歸判斷下一頂點。對于無連接或者直接舍棄兩種情況，在遞歸前，可采用剪枝策略來避免無效搜索。
為了判斷當前頂點加入團之后是否仍是一個團，只需要考慮該頂點和團中頂點是否都有連接。
程序中采用了一個比較簡單的剪枝策略，即如果剩余未考慮的頂點數加上團中頂點數不大于當前解的頂點數，可停止繼續深度搜索，否則繼續深度遞歸
當搜索到一個葉結點時，即可停止搜索，此時更新最優解和最優值。
以下是轉載的某篇論文的，百度文庫的
http://wenku.baidu.com/view/1bd93526a5e9856a561260e2.html
3.6 回溯法
3.6.1 算法基本思想
回溯法（Backtracking Algorithm, BA）有“通用的解題法”之稱，用它可以系統地搜索一個問題的所有解或任一解，是一個既帶有系統性又帶有跳躍性的搜索算法。在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按照深度優先的策略進行搜索。BA在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而BA在用來求問題的任一解時，只要搜索到問題的一個解即可結束。這種以深度優先的方式系統地搜索問題的解的算法稱為回溯法，它適用于解一些組合數較大的問題。
回溯法搜索解空間樹時，根節點首先成為一個活結點，同時也成為當前的擴展節點。在當前擴展節點處，搜索向縱深方向移至一個新節點。這個新節點就成為一個新的活結點，并成為當前擴展節點。如果當前擴展節點不能再向縱深方向移動，則當前的擴展節點就成為死結點。此時，往回回溯至最近的一個活節點處，并使這個活結點成為當前的擴展節點。
回溯法以這種方式遞歸地在解空間中搜索，直至找到所有要求的解或解空間已無活結點為止。
3.6.2 算法設計思想
搜索：回溯法從根結點出發，按深度優先策略遍歷解空間樹，搜索滿足約束條件的解。
剪枝：在搜索至樹中任一結點時，先判斷該結點對應的部分解是否滿足約束條件，或者是否超出目標函數的界；也即判斷該結點是否包含問題的解，如果肯定不包含，則跳過對以該結點為根的子樹的搜索，即剪枝（Pruning）；否則，進入以該結點為根的子樹，繼續按照深度優先的策略搜索。
一般來講，回溯法求解問題的基本步驟如下：
(1) 針對所給問題，定義問題的解空間；
(2) 確定易于搜索的解空間結構；
(3) 以深度優先方式搜索解空間，并在搜索過程中利用Pruning函數剪去無效的搜索。
無向圖G的最大團問題可以看作是圖G的頂點集V的子集選取問題。因此可以用子集樹表示問題的解空間。設當前擴展節點Z位于解空間樹的第i層。在進入左子樹前，必須確認從頂點i到已入選的頂點集中每一個頂點都有邊相連。在進入右子樹之前，必須確認還有足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團。
用鄰接矩陣表示圖G，n為G的頂點數，cn存儲當前團的頂點數，bestn存儲最大團的頂點數。cn+n-i為進入右子樹的上界函數，當cn+n-i<bestn時，不能在右子樹中找到更大的團，利用剪枝函數可將Z的右結點剪去。
3.6.3 實例分析
如圖1所示，給定無向圖G={V, E}，其中V ={1,2,3,4,5}，E={(1,2), (1,4), (1,5), (2,3), (2,5), (3,5), (4,5)}。根據MCP定義，子集{1,2}是圖G的一個大小為2的完全子圖，但不是一個團，因為它包含于G的更大的完全子圖{1,2,5}之中。{1,2,5}是G的一個最大團。{1,4,5}和{2,3,5}也是G的最大團。
圖2是無向圖G的補圖G'。根據最大獨立集定義，{2,4}是G的一個空子圖，同時也是G的一個最大獨立集。雖然{1,2}也是G'的空子圖，但它不是G'的獨立集，因為它包含在G'的空子圖{1,2,5}中。{1,2,5}是G'的最大獨立集。{1,4,5}和{2,3,5}也是G'的最大獨立集。
以圖1為例，利用回溯法搜索其空間樹，具體搜索過程（見圖3所示）如下：假設我們按照1?2?3?4?5的順序深度搜索。開始時，根結點R是唯一活結點，也是當前擴展結點，位于第1層，此時當前團的頂點數cn=0，最大團的頂點數bestn=0。在這個擴展結點處，我們假定R和第二層的頂點1之間有邊相連，則沿縱深方向移至頂點1處。此時結點R和頂點1都是活結點，頂點1成為當前的擴展結點。此時當前團的頂點數cn=1，最大團的頂點數bestn=0。繼續深度搜索至第3層頂點2處，此時頂點1和2有邊相連，都是活結點，頂點2成為當前擴展結點。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜索至第4層頂點3處，由于頂點3和2有邊相連但與頂點1無邊相連，則利用剪枝函數剪去該枝，此時由于cn+n-i=2+5-4=3>bestn=0，則回溯到結點2處進入右子樹，開始搜索。此時當前團的頂點數cn=2，最大團的頂點數bestn=0。再深度搜索至第5層頂點4處，由于頂點3和4無邊相連，剪去該枝，回溯到結點3處進入右子樹，此時當前團的頂點數cn=2，最大團的頂點數bestn=0。繼續深度搜索至第6層頂點5處，由于頂點5和4有邊相連，且與頂點1和2都有邊相連，則進入左子樹搜索。由于結點5是一個葉結點，故我們得到一個可行解，此時當前團的頂點數cn=3，最大團的頂點數bestn=3。vi的取值由頂點1至頂點5所唯一確定，即v=(1, 2, 5)。此時頂點5已不能再縱深擴展，成為死結點，我們返回到結點4處。由于此時cn+n-i=3+5-6=2<bestn=3，不能在右子樹中找到更大的團，利用剪枝函數可將結點4的右結點剪去。以此回溯，直至根結點R再次成為當前的擴展結點，沿著右子樹的縱深方向移動，直至遍歷整個解空間。最后得到圖1的按照1?2?3?4?5的順序深度搜索的最大團為U={1,2,5}。當然{1,4,5}和{2,3,5}也是其最大團。
代碼：
View Code 1 #include <iostream> 2 #include <memory.h> 3 #include <stdio.h> 4 using namespace std; 5 6 const int maxnum=101; 7 bool array[maxnum][maxnum]; 8 bool use[maxnum]; //進入團的標號 9 int cn,bestn,p,e; 10 11 void dfs(int i) 12 { 13 int j; 14 bool flag; 15 16 if(i>p) 17 { 18 bestn=cn; 19 printf("%d\n",bestn); 20 for(j=1;j<=p;j++) 21 if(use[j]) 22 printf("%d ",j); 23 printf("\n"); 24 return ; 25 } 26 27 flag=true; 28 for(j=1;j<i;j++) 29 if(use[j]&&!array[j][i]) 30 { 31 flag=false; 32 break; 33 } 34 if(flag) 35 { 36 cn++; 37 use[i]=true; 38 dfs(i+1); 39 cn--; 40 } 41 if(cn+p-i>bestn) //剪枝 42 { 43 use[i]=false; 44 dfs(i+1); 45 } 46 } 47 48 int main() 49 { 50 int num,i,u,v; 51 scanf("%d",&num); 52 while(num--) 53 { 54 memset(array,false,sizeof(array)); 55 memset(use,false,sizeof(use)); 56 scanf("%d%d",&p,&e); 57 for(i=0;i<e;i++) 58 { 59 scanf("%d%d",&u,&v); 60 array[u][v]=true; 61 array[v][u]=true; 62 } 63 64 cn=bestn=0; 65 dfs(1); 66 //printf("%d\n",bestn); 67 } 68 69 return 0; 70 } 71 72 /* 73 1 74 5 7 75 1 2 76 1 4 77 1 5 78 2 3 79 2 5 80 3 5 81 4 5 82 */總結
- 上一篇： 删除打开方式中的选项
- 下一篇： 分享一个下载无损音乐的网站，且用且珍惜！