回溯法試驗最大團問題

1、算法分析與設(shè)計實驗報告匕次附加實驗姓名學(xué)號班級時間上午地點工訓(xùn)樓309實驗名稱回溯法實驗（最大團問題）實驗?zāi)康?. 掌握回溯法求解問題的思想2. 學(xué)會利用其原理求解最大團問題問題描述：給定無向連通圖 G = （V,E，其中V是非空集合，稱為頂點集；E是V中元素構(gòu)成的無序二元組的集合，稱為邊集，無向圖中的邊均是頂點的無序?qū)Γ?無序?qū)ΤＳ脠A括號“（）”表示，如果U?V,且對任意兩個頂點 U, v?U有（u,v） ?E，則稱U是G的完全子圖，G的完全子圖是 G的團當(dāng)前僅當(dāng)U不包含在G 的更大的完全子圖中。G的最大團是指 G中所含頂點數(shù)最多的團。實驗原理G中，所以由于（1,3 ）之間沒有連線，1,2,

2、3）（ 1,5,4）（2,3,4）都是因此（1,2,3）（ 1,5,4）（ 2,3,4）由上圖來看，（1,2,4）中每個頂點之間都相連接，并且都包含在圖（1,2,4）是一個圖 G的一個團，但是（1,2,3,4） 所以沒有保證所有頂點都連接，因此不是團，而（ 三頂點的團，而該圖包含頂點數(shù)最多的團就是三個， 屬于最大團，最大團問題就是求解這樣的問題。程序中采用了一個比較簡單的剪枝策略，即如果剩余未考慮的頂點數(shù)加上團中頂點數(shù)不大于當(dāng)前解的頂點數(shù)，可停止繼續(xù)深度搜索， 否則繼續(xù)深度遞歸當(dāng)搜索到一個葉結(jié)點時，即可停止搜索，此時更新最優(yōu)解和最優(yōu)值。基本解題步驟：（1）針對所給問題，定義問題的解空間；（2）

3、確定易于搜索的解空間結(jié)構(gòu)； 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。(1) 首先設(shè)最大團為一個空團，往其中加入一個頂點；實驗步驟(2) 然后依次考慮每個頂點，查看該頂點加入團之后仍然構(gòu)成一個團，如果 可以，考慮將該頂點加入團或者舍棄兩種情況，如果不行，直接舍棄，然后遞 歸判斷下一頂點；(3) 可采用剪枝策略來避免無效搜索；(4) 為了判斷當(dāng)前頂點加入團之后是否仍是一個團，只需要考慮該頂點和團 中頂點是否都有連接。void Clique:Backtrack(nt i) /計算最大團if(i> n) /到達葉子節(jié)點for(i nt j=1;jv=n ;j+) best

4、xj=xj;best n=cn;cout<<'最大團：("for(i nt i=1;i< n;i+) cout<<bestxi<<"," cout<<bestx n <<")" we ndl;retur n;/檢查當(dāng)前頂點是否與當(dāng)前團連接int ok=1;for(i nt j=1;j<i;j+)關(guān)鍵代碼if(xj&&aij=0) /i與j不連接，即j在團中，但是i,j不連接 ok=0;break; if(ok) /進入左子樹xi=1;cn+;Back

5、track(i+1);/回溯到下一層節(jié)點xi=0;cn-;/通過上界函數(shù)判斷是否減去右子樹，上界函數(shù)用于確認(rèn)還有 足夠多的可選擇頂點使得算法有可能在右子樹中找到更大的團if(c n+n-i>=best n)/修改一下上界函數(shù)的條件，可以得到xi=0;/相同點數(shù)時的解Backtrack(i+1);H當(dāng)輸入圖如下時:p-F：算法實密.實驗囚回j®SM axCliq ueDe bu giMa xCl iq ue, exeplease please Lp lease kinput input Imput edge:number of node:G number of edge：?245

6、3445團：(1,1,0,1,0>5：(1,0,0,1,i>S： (0,1,1,1,0>任忌鍵維續(xù)-測試結(jié)果當(dāng)輸入圖如下時:pplease please please i12343445number of nodeinputinput nunbep of edge：8inputedsfe :點繼 (i 1慰娶冃5當(dāng)輸入圖如下時:I E F;算法實驗實驗四回滋法M axCl i qu eDeb u gM axCii q u e.exeInput nunber of node input nunbei' of edge ：9Ase input edsfe =2I Mr?

7、j_ I d I I請按任意鍵繼類-通過三個實例圖，我們只是簡單的將最開始的原始圖進行加邊處理，可以實驗分析發(fā)現(xiàn)結(jié)果就會發(fā)生變化。 最大團問題可是比較典型的利用解空間的子集樹進行 深度搜索，然后通過上界函數(shù)進行剪枝，只是此處的上界函數(shù)比較簡單，只要判斷是否還有做夠的頂點能夠構(gòu)成最大團即可，相對于0-1背包問題和最優(yōu)裝載問題來說還是簡單一點，其中主要注意的就是要加入現(xiàn)有團的頂點必須滿足 和所有的團內(nèi)的頂點都有邊相連，這樣才能加入該團中，否則就不能加入團中。最大團問題和圖的 m著色問題用回溯法解很相似，他倆在對于判斷的時 候都比較簡單，但是相比而言，由于最大團問題涉及到利用上屆函數(shù)進行右子 樹剪枝

8、，所以相比較而言復(fù)雜一點， 最大團問題的上屆函數(shù)和很多問題比如最 優(yōu)裝載問題的上屆函數(shù)原理是相同的，就是判斷右子樹當(dāng)前節(jié)點最好的可能是實驗心得否能夠比當(dāng)前最優(yōu)解要好，如果當(dāng)前節(jié)點的最好情況都不能超過當(dāng)前最優(yōu)解， 那么說明最優(yōu)解絕對不會有該節(jié)點，因此可以將該節(jié)點所在的右子樹剪掉，這樣就減少了算法的查找和回溯的時間。這里要提一點的是在進行右子樹剪枝的時候使用了大于等于，如果只是大于的話就沒有辦法找到頂點數(shù)相同的其他最 優(yōu)解了，同樣找到葉子節(jié)點時則證明得到一個最優(yōu)解，將其輸出即可實驗得分助教簽名附錄： 完整代碼(回溯法)/ 最大團問題 回溯法求解 #include<iostream>us

9、ing namespacestd;classCliquefriend void MaxClique(int *, int *,int ); private:void Backtrack(int i); int *a; / 圖的鄰接矩陣 int n; / 圖的頂點數(shù) int *x; / 當(dāng)前解 int *bestx; / 當(dāng)前最優(yōu)解 int cn; / 當(dāng)前頂點數(shù) int bestn; / 當(dāng)前最大頂點數(shù);void Clique:Backtracki(nt i) / 計算最大團 if (i>n) / 到達葉子節(jié)點for(int j=1;j<=n;j+) bestxj=xj;bestn

10、=cn; cout<<" 最大團：( " for(int i=1;i<n;i+) cout<<bestxi<<"," ; cout<<bestxn<<")" <<endl;return ;/ 檢查當(dāng)前頂點是否與當(dāng)前團連接int ok=1;for(int j=1;j<i;j+)if(xj&&aij=O) /i與j不連接,即j在團中，但是i,j不連接 ok=O;break;if(ok) /進入左子樹xi=1;cn+;Backtrack(i+

11、1);/回溯到下一層節(jié)點 xi=O;cn-;/ 通過上界函數(shù)判斷是否減去右子樹， 上界函數(shù)用于確認(rèn)還有足夠多的可選 擇頂點使得算法有可能在右子樹中找到更大的團if (cn+n-i>=bestn) / 修改一下上界函數(shù)的條件，可以得到xi=0; / 相同點數(shù)時的解Backtrack(i+1);void MaxClique(int *a, int *v,int n) / 初始化 YClique Y;=new int n+1;=a;=n;=0;=0;=v;(1);delete ;cout<<" 最大團的頂點數(shù)： " <<<<endl;in

12、t main()int n;cout<<"please input number of node:" ;cin>>n;/int an+1n+1; / 由于定義的是 int *a ，且采用的是二維數(shù)組傳參，因此 int *a= new int *n+1; / 兩種解決方法，一是給定第二維的大小，二是通過 for(int i=0;i<=n;i+) / 動態(tài)分配內(nèi)存，這里采用了動態(tài)內(nèi)存分配解決問題 ai=new intn+1;for(int i=0;i<n+1;i+)for (int j=0;j<n+1;j+)aij=0;int edge;cout<<"please input number of edge:"cin>>edge;c