回溯法實驗(最大團問題)

算法剖析與設(shè)計實驗報告第七次附帶實驗姓名時間

12。26上午

學(xué)號地址

班級工訓(xùn)樓

309實驗名稱

回溯法實驗

(最大團問題）掌握回溯法求解問題的思想實驗?zāi)康膶W(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)U不包括在G的更大的完好子圖中。G的最大團是指G中所含極點數(shù)最多的團.12354實驗原理由上圖來看，（1，2，4）中每個極點之間都相連結(jié)，而且都包括在圖G中,所以（1，2，4）是一個圖G的一個團,但是（1，2，3，4）因為（1,3)之間沒有連線，所以沒有保證全部極點都連結(jié),所以不是團，而（1,2，3)（1,5，4）（2，3，4)都是三極點的團,而該圖包括極點數(shù)最多的團就是三個，所以（1，2,3）（1，5，4）（2,3，4）屬于最大團,最大團問題就是求解這樣的問題.程序中采納了一個比較簡單的剪枝策略，即假如節(jié)余未考慮的極點數(shù)加上團中極點數(shù)不大于目前解的極點數(shù)，可停止持續(xù)深度搜尋，不然持續(xù)深度遞歸當(dāng)搜尋到一個葉結(jié)點時，即可停止搜尋，此時更新最優(yōu)解和最優(yōu)值.基本解題步驟：針對所給問題,定義問題的解空間;確立易于搜尋的解空間構(gòu)造；以深度優(yōu)先方式搜尋解空間，并在搜尋過程頂用剪枝函數(shù)防止無效搜尋.實驗步驟

(1）第一設(shè)最大團為一個空團，往此中加入一個極點；（2）而后挨次考慮每個極點，查察該極點加入團以后仍舊組成一個團以，考慮將該極點加入團或許舍棄兩種狀況，假如不可以，直接舍棄判斷下一極點；（3）可采納剪枝策略來防止無效搜尋;

,假如可,而后遞歸(4)為了判斷目前極點加入團以后能否還是一個團，只需要考慮該極點和團中極點能否都有連結(jié).voidClique：：Backtrack（inti){//計算最大團if(i〉n）//抵達葉子節(jié)點｛for（intj=1；j〈=n；j++）bestx[j]=x[j］；bestn=cn;cout〈<”最大團：（”;for(inti=1;i〈n;i++)cout〈<bestx［icout〈〈bestx[n]

］<〈”,"；〈〈")”<<endl；return

；}檢查目前極點能否與目前團連結(jié)intok=1;重點代碼

for（intj=1；j〈i;j++）if(x[j］&＆a[i][j]==0）//i與j

不連結(jié),即j

在團中，但是

i，不連結(jié){ok=0；break;}if(ok)//進入左子樹{x[i]=1；cn++；Backtrack（i+1）；//回溯到下一層節(jié)點x[i］=0；cn——;｝經(jīng)過上界函數(shù)判斷能否減去右子樹，上界函數(shù)用于確認還有足夠多的可選擇極點使得算法有可能在右子樹中找到更大的團if（cn+n—i〉=bestn)｛

x［i

］=0;

//改正一下上界函數(shù)的條件//相同點數(shù)時的解

,能夠獲得Backtrack(i+1

）;｝｝當(dāng)輸入圖以下時：12354測試結(jié)果當(dāng)輸入圖以下時:12354當(dāng)輸入圖以下時：12354經(jīng)過三個實例圖，我們不過簡單的將最開始的原始圖進行加邊辦理,能夠發(fā)現(xiàn)結(jié)果就會發(fā)生變化。最大團問題但是比較典型的利用解空間的子集樹進行實驗剖析深度搜尋，而后經(jīng)過上界函數(shù)進行剪枝,不過此處的上界函數(shù)比較簡單，只需判斷能否還有做夠的極點能夠組成最大團即可,相關(guān)于0-1背包問題和最優(yōu)裝載問題來說還是簡單調(diào)點,此中主要注意的就是要加入現(xiàn)有團的極點一定知足和全部的團內(nèi)的極點都有邊相連,這樣才能加入該團中,不然就不可以加入團中.實驗心得

最大團問題和圖的m著色問題用回溯法解很相像,他倆在關(guān)于判斷的時候都比較簡單,但是對比而言，因為最大團問題波及到利用上屆函數(shù)進行右子樹剪枝，所以對比較而言復(fù)雜一點，最大團問題的上屆函數(shù)和好多問題比方最優(yōu)裝載問題的上屆函數(shù)原理是相同的,就是判斷右子樹目前節(jié)點最好的可能能否能夠比目前最優(yōu)解要好，假如目前節(jié)點的最好狀況都不可以超出目前最優(yōu)解，么說明最優(yōu)解絕對不會有該節(jié)點,所以能夠?qū)⒃摴?jié)點所在的右子樹剪掉，這樣就減少了算法的查找和回溯的時間。這里要提一點的是在進行右子樹剪枝的時候使用了大于等于，假如不過大于的話就沒有方法找到極點數(shù)相同的其余最優(yōu)解了，相同找到葉子節(jié)點時則證明獲得一個最優(yōu)解,將其輸出即可

那實驗得分

助教署名附錄:完好代碼

(回溯法）最大團問題回溯法求解＃include<iostream〉usingnamespacestd；classClique{friendvoidMaxClique(int**，int＊，int）；private：voidBacktrack(inti)；int＊＊a；//圖的毗鄰矩陣intn；//圖的極點數(shù)int＊x;//目前解int＊bestx;//目前最優(yōu)解intcn；//目前極點數(shù)intbestn;//目前最大極點數(shù)}；voidClique：：Backtrack（inti）//計算最大團if(i〉n）//抵達葉子節(jié)點｛for(intj=1；j<=n;j++）bestx［j］=x［j］;bestn=cn；cout〈〈”最大團：(”；for（inti=1；i〈n；i++)cout〈〈bestx[i］〈<"，”;cout〈〈bestx［n]〈〈”）”<〈endl;return；｝檢查目前極點能否與目前團連結(jié)intok=1；for(intj=1；j<i;j++)if(x［j]＆&a［i］［j]==0）//i與j不連結(jié)，即j在團中，但是i,j不連結(jié)｛ok=0；break;｝if（ok）//進入左子樹｛x［i］=1；cn++；Backtrack（i+1）；//回溯到下一層節(jié)點x[i]=0;cn—-;｝經(jīng)過上界函數(shù)判斷能否減去右子樹，上界函數(shù)用于確認還有足夠多的可選擇極點使得算法有可能在右子樹中找到更大的團if（cn+n-i〉=bestn){

x［i

］=0；

//改正一下上界函數(shù)的條件，能夠獲得//相同點數(shù)時的解Backtrack(i+1

）；｝}voidMaxClique（int＊＊a,int*v,intn）//初始化YCliqueY;Y.x=newint[n+1］；。a=a；Y。n=n;Y.cn=0;Y。bestn=0；Y。bestx=v；Y.Backtrack（1）；delete［］Y.x;cout〈〈”最大團的極點數(shù):”<<Y。bestn<〈endl；}intmain（）｛intn；cout〈<”pleaseinputnumberofnodecin>〉n;

：”；//int

a［n+1][n+1

］；//

因為定義的是

int

＊*a，且采納的是二維數(shù)組傳參,所以int＊＊a=newint＊［n+1］；//兩種解決方法,一是給定第二維的大小，二是經(jīng)過for（inti=0；i〈=n;i++）//動向分派內(nèi)存,這里采納了動向內(nèi)存分派解決問題［i］=newint［n+1］;for(inti=0；i<n+1；i++)for（intj=0；j<n+1；j++)a［i]［j］=0；intedge；cout<<”pleaseinputnumberofedge:”;cin〉〉