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

算法剖析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第七次附帶實(shí)驗(yàn)姓名時(shí)間

12。26上午

學(xué)號(hào)地址

班級(jí)工訓(xùn)樓

309實(shí)驗(yàn)名稱

回溯法實(shí)驗(yàn)

(最大團(tuán)問(wèn)題）掌握回溯法求解問(wèn)題的思想實(shí)驗(yàn)?zāi)康膶W(xué)會(huì)利用其原理求解最大團(tuán)問(wèn)題問(wèn)題描繪:給定無(wú)向連通圖G=(V,E），此中V是非空會(huì)合,稱為極點(diǎn)集;E是V中元素構(gòu)成的無(wú)序二元組的會(huì)合，稱為邊集，無(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)U不包括在G的更大的完好子圖中。G的最大團(tuán)是指G中所含極點(diǎn)數(shù)最多的團(tuán).12354實(shí)驗(yàn)原理由上圖來(lái)看，（1，2，4）中每個(gè)極點(diǎn)之間都相連結(jié)，而且都包括在圖G中,所以（1，2，4）是一個(gè)圖G的一個(gè)團(tuán),但是（1，2，3，4）因?yàn)椋?,3)之間沒(méi)有連線，所以沒(méi)有保證全部極點(diǎn)都連結(jié),所以不是團(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)單的剪枝策略，即假如節(jié)余未考慮的極點(diǎn)數(shù)加上團(tuán)中極點(diǎn)數(shù)不大于目前解的極點(diǎn)數(shù)，可停止持續(xù)深度搜尋，不然持續(xù)深度遞歸當(dāng)搜尋到一個(gè)葉結(jié)點(diǎn)時(shí)，即可停止搜尋，此時(shí)更新最優(yōu)解和最優(yōu)值.基本解題步驟：針對(duì)所給問(wèn)題,定義問(wèn)題的解空間;確立易于搜尋的解空間構(gòu)造；以深度優(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è)團(tuán)以，考慮將該極點(diǎn)加入團(tuán)或許舍棄兩種狀況，假如不可以，直接舍棄判斷下一極點(diǎn)；（3）可采納剪枝策略來(lái)防止無(wú)效搜尋;

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

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

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

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

不連結(jié),即j

在團(tuán)中，但是

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

x［i

］=0;

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

,能夠獲得Backtrack(i+1

）;｝｝當(dāng)輸入圖以下時(shí)：12354測(cè)試結(jié)果當(dāng)輸入圖以下時(shí):12354當(dāng)輸入圖以下時(shí)：12354經(jīng)過(guò)三個(gè)實(shí)例圖，我們不過(guò)簡(jiǎn)單的將最開(kāi)始的原始圖進(jìn)行加邊辦理,能夠發(fā)現(xiàn)結(jié)果就會(huì)發(fā)生變化。最大團(tuán)問(wèn)題但是比較典型的利用解空間的子集樹(shù)進(jìn)行實(shí)驗(yàn)剖析深度搜尋，而后經(jīng)過(guò)上界函數(shù)進(jìn)行剪枝,不過(guò)此處的上界函數(shù)比較簡(jiǎn)單，只需判斷能否還有做夠的極點(diǎn)能夠組成最大團(tuán)即可,相關(guān)于0-1背包問(wèn)題和最優(yōu)裝載問(wèn)題來(lái)說(shuō)還是簡(jiǎn)單調(diào)點(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)題用回溯法解很相像,他倆在關(guān)于判斷的時(shí)候都比較簡(jiǎn)單,但是對(duì)比而言，因?yàn)樽畲髨F(tuán)問(wèn)題波及到利用上屆函數(shù)進(jìn)行右子樹(shù)剪枝，所以對(duì)比較而言復(fù)雜一點(diǎn)，最大團(tuán)問(wèn)題的上屆函數(shù)和好多問(wèn)題比方最優(yōu)裝載問(wèn)題的上屆函數(shù)原理是相同的,就是判斷右子樹(shù)目前節(jié)點(diǎn)最好的可能能否能夠比目前最優(yōu)解要好，假如目前節(jié)點(diǎn)的最好狀況都不可以超出目前最優(yōu)解，么說(shuō)明最優(yōu)解絕對(duì)不會(huì)有該節(jié)點(diǎn),所以能夠?qū)⒃摴?jié)點(diǎn)所在的右子樹(shù)剪掉，這樣就減少了算法的查找和回溯的時(shí)間。這里要提一點(diǎn)的是在進(jìn)行右子樹(shù)剪枝的時(shí)候使用了大于等于，假如不過(guò)大于的話就沒(méi)有方法找到極點(diǎn)數(shù)相同的其余最優(yōu)解了，相同找到葉子節(jié)點(diǎn)時(shí)則證明獲得一個(gè)最優(yōu)解,將其輸出即可

那實(shí)驗(yàn)得分

助教署名附錄:完好代碼

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

x［i

］=0；

//改正一下上界函數(shù)的條件，能夠獲得//相同點(diǎn)數(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〈〈”最大團(tuán)的極點(diǎn)數(shù):”<<Y。bestn<〈endl；}intmain（）｛intn；cout〈<”pleaseinputnumberofnodecin>〉n;

：”；//int

a［n+1][n+1

］；//

因?yàn)槎x的是

int

＊*a，且采納的是二維數(shù)組傳參,所以int＊＊a=newint＊［n+1］；//兩種解決方法,一是給定第二維的大小，二是經(jīng)過(guò)for（inti=0；i〈=n;i++）//動(dòng)向分派內(nèi)存,這里采納了動(dòng)向內(nèi)存分派解決問(wèn)題［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〉〉