回溯法實(shí)驗(yàn)(最大團(tuán)問(wèn)題)

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

2、相連接，并且都包含在圖G中，所以（1,2,4）是一個(gè)圖G的一個(gè)團(tuán)，但是（1,2,3,4）由于（1,3）之間沒(méi)有連線，所以沒(méi)有保證所有頂點(diǎn)都連接，因此不是團(tuán)，而（1,2,3）（1,5,4）（2,3,4）都是三頂點(diǎn)的團(tuán)，而該圖包含頂點(diǎn)數(shù)最多的團(tuán)就是三個(gè)，因此（1,2,3）（1,5,4）（2,3,4）屬于最大團(tuán)，最大團(tuán)問(wèn)題就是求解這樣的問(wè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ì)所給問(wèn)題，定義問(wèn)題的解空間；(2) 確定易于

3、搜索的解空間結(jié)構(gòu)；(3) 以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。實(shí)驗(yàn)步驟（1）首先設(shè)最大團(tuán)為一個(gè)空?qǐng)F(tuán)，往其中加入一個(gè)頂點(diǎ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)是否都有連接。關(guān)鍵代碼void Clique:Backtrack(int i) /計(jì)算最大團(tuán) if(i>n) /到達(dá)葉子節(jié)點(diǎn) for(int j=1;j<=n;j+) bestx

4、j=xj;bestn=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=0) /i與j不連接,即j在團(tuán)中,但是i,j不連接 ok=0;break; if(ok) /進(jìn)入左子樹 xi=1; cn+; Bac

5、ktrack(i+1); /回溯到下一層節(jié)點(diǎn) xi=0; cn-; /通過(guò)上界函數(shù)判斷是否減去右子樹，上界函數(shù)用于確認(rèn)還有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán) if(cn+n-i>=bestn) /修改一下上界函數(shù)的條件，可以得到 xi=0; /相同點(diǎn)數(shù)時(shí)的解 Backtrack(i+1); 測(cè)試結(jié)果 當(dāng)輸入圖如下時(shí)：12345 當(dāng)輸入圖如下時(shí)：12345當(dāng)輸入圖如下時(shí)：12345實(shí)驗(yàn)分析通過(guò)三個(gè)實(shí)例圖，我們只是簡(jiǎn)單的將最開始的原始圖進(jìn)行加邊處理，可以發(fā)現(xiàn)結(jié)果就會(huì)發(fā)生變化。最大團(tuán)問(wèn)題可是比較典型的利用解空間的子集樹進(jìn)行深度搜索，然后通過(guò)上界函數(shù)進(jìn)行剪枝，只是此處的上界函

6、數(shù)比較簡(jiǎn)單，只要判斷是否還有做夠的頂點(diǎn)能夠構(gòu)成最大團(tuán)即可，相對(duì)于0-1背包問(wèn)題和最優(yōu)裝載問(wèn)題來(lái)說(shuō)還是簡(jiǎn)單一點(diǎn)，其中主要注意的就是要加入現(xiàn)有團(tuán)的頂點(diǎn)必須滿足和所有的團(tuán)內(nèi)的頂點(diǎn)都有邊相連，這樣才能加入該團(tuán)中，否則就不能加入團(tuán)中。實(shí)驗(yàn)心得最大團(tuán)問(wèn)題和圖的m著色問(wèn)題用回溯法解很相似，他倆在對(duì)于判斷的時(shí)候都比較簡(jiǎn)單，但是相比而言，由于最大團(tuán)問(wèn)題涉及到利用上屆函數(shù)進(jìn)行右子樹剪枝，所以相比較而言復(fù)雜一點(diǎn)，最大團(tuán)問(wèn)題的上屆函數(shù)和很多問(wèn)題比如最優(yōu)裝載問(wèn)題的上屆函數(shù)原理是相同的，就是判斷右子樹當(dāng)前節(jié)點(diǎn)最好的可能是否能夠比當(dāng)前最優(yōu)解要好，如果當(dāng)前節(jié)點(diǎn)的最好情況都不能超過(guò)當(dāng)前最優(yōu)解，那么說(shuō)明最優(yōu)解絕對(duì)不會(huì)有該節(jié)點(diǎn)，因

7、此可以將該節(jié)點(diǎn)所在的右子樹剪掉，這樣就減少了算法的查找和回溯的時(shí)間。這里要提一點(diǎn)的是在進(jìn)行右子樹剪枝的時(shí)候使用了大于等于，如果只是大于的話就沒(méi)有辦法找到頂點(diǎn)數(shù)相同的其他最優(yōu)解了，同樣找到葉子節(jié)點(diǎn)時(shí)則證明得到一個(gè)最優(yōu)解，將其輸出即可實(shí)驗(yàn)得分助教簽名附錄：完整代碼（回溯法）/最大團(tuán)問(wèn)題 回溯法求解#include<iostream>using namespace std;class Cliquefriend void MaxClique(int *,int *,int );private:void Backtrack(int i);int *a; /圖的鄰接矩陣int n; /圖的頂點(diǎn)

8、數(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:Backtrack(int i) /計(jì)算最大團(tuán) if(i>n) /到達(dá)葉子節(jié)點(diǎn) for(int j=1;j<=n;j+) bestxj=xj;bestn=cn;cout<<"最大團(tuán)：（" for(int i=1;i<n;i+) cout<<bestxi<<"," cout<<bestxn<<")"<

9、<endl; return; /檢查當(dāng)前頂點(diǎn)是否與當(dāng)前團(tuán)連接int ok=1;for(int j=1;j<i;j+) if(xj&&aij=0) /i與j不連接,即j在團(tuán)中,但是i,j不連接 ok=0;break; if(ok) /進(jìn)入左子樹 xi=1; cn+; Backtrack(i+1); /回溯到下一層節(jié)點(diǎn) xi=0; cn-; /通過(guò)上界函數(shù)判斷是否減去右子樹，上界函數(shù)用于確認(rèn)還有足夠多的可選擇頂點(diǎn)使得算法有可能在右子樹中找到更大的團(tuán) if(cn+n-i>=bestn) /修改一下上界函數(shù)的條件，可以得到 xi=0; /相同點(diǎn)數(shù)時(shí)的解 Backtra

10、ck(i+1); void MaxClique(int *a,int *v,int n) /初始化Y Clique Y; Y.x=new intn+1; Y.a=a; Y.n=n; Y.cn=0; Y.bestn=0; Y.bestx=v; Y.Backtrack(1); delete Y.x; cout<<"最大團(tuán)的頂點(diǎn)數(shù)："<<Y.bestn<<endl;int main()int n;cout<<"please input number of node:"cin>>n; /int an+1n+1; /由于定義的是int *a，且采用的是二維數(shù)組傳參，因此 int *a=new int *n+1; /兩種解決方法，一是給定第二維的大小，二是通過(guò) for(int i=0;i<=n;i+) /動(dòng)態(tài)分配內(nèi)存，這里采用了動(dòng)態(tài)內(nèi)存分配解決問(wèn)題 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;cout<<"pl