回溯法試驗(yàn)最大團(tuán)問題

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

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

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

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

5、track(i+1);/回溯到下一層節(jié)點(diǎn)xi=0;cn-;/通過上界函數(shù)判斷是否減去右子樹，上界函數(shù)用于確認(rèn)還有 足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)if(c n+n-i>=best n)/修改一下上界函數(shù)的條件，可以得到xi=0;/相同點(diǎn)數(shù)時(shí)的解Backtrack(i+1);H當(dāng)輸入圖如下時(shí):p-F：算法實(shí)密.實(shí)驗(yàn)囚回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團(tuán)：(1,1,0,1,0>5：(1,0,0,1,i>S： (0,1,1,1,0>任忌鍵維續(xù)-測(cè)試結(jié)果當(dāng)輸入圖如下時(shí):pplease please please i12343445number of nodeinputinput nunbep of edge：8inputedsfe :點(diǎn)繼 (i 1慰娶冃5當(dāng)輸入圖如下時(shí):I E F;算法實(shí)驗(yàn)實(shí)驗(yàn)四回滋法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請(qǐng)按任意鍵繼類-通過三個(gè)實(shí)例圖，我們只是簡(jiǎn)單的將最開始的原始圖進(jìn)行加邊處理，可以實(shí)驗(yàn)分析發(fā)現(xiàn)結(jié)果就會(huì)發(fā)生變化。 最大團(tuán)問題可是比較典型的利用解空間的子集樹進(jìn)行 深度搜索，然后通過上界函數(shù)進(jìn)行剪枝，只是此處的上界函數(shù)比較簡(jiǎn)單，只要判斷是否還有做夠的頂點(diǎn)能夠構(gòu)成最大團(tuán)即可，相對(duì)于0-1背包問題和最優(yōu)裝載問題來(lái)說還是簡(jiǎn)單一點(diǎn)，其中主要注意的就是要加入現(xiàn)有團(tuán)的頂點(diǎn)必須滿足 和所有的團(tuán)內(nèi)的頂點(diǎn)都有邊相連，這樣才能加入該團(tuán)中，否則就不能加入團(tuán)中。最大團(tuán)問題和圖的 m著色問題用回溯法解很相似，他倆在對(duì)于判斷的時(shí) 候都比較簡(jiǎn)單，但是相比而言，由于最大團(tuán)問題涉及到利用上屆函數(shù)進(jìn)行右子 樹剪枝

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

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

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

11、1);/回溯到下一層節(jié)點(diǎn) xi=O;cn-;/ 通過上界函數(shù)判斷是否減去右子樹， 上界函數(shù)用于確認(rèn)還有足夠多的可選 擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán)if (cn+n-i>=bestn) / 修改一下上界函數(shù)的條件，可以得到xi=0; / 相同點(diǎn)數(shù)時(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<<" 最大團(tuán)的頂點(diǎn)數(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+) / 動(dòng)態(tài)分配內(nèi)存，這里采用了動(dòng)態(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