回溯法實(shí)驗(yàn)圖的m著色問(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)(圖的m著色問(wèn)題)實(shí)驗(yàn)?zāi)康?. 掌握回溯法求解問(wèn)題的思想2. 學(xué)會(huì)利用其原理求解圖的m著色問(wèn)題實(shí)驗(yàn)原理問(wèn)題描述：給定無(wú)向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色。這個(gè)問(wèn)題是圖的m可著色判定問(wèn)題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m的問(wèn)題稱為圖的m可著色優(yōu)化問(wèn)題?；窘忸}步驟：(1) 針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；(2) 確定易于搜索的

2、解空間結(jié)構(gòu)；(3) 以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。實(shí)驗(yàn)步驟（1）首先將給定的圖利用抽象圖表示出來(lái)；（2）判斷該節(jié)點(diǎn)k當(dāng)前的著色是否符合條件，需要判斷xk與k節(jié)點(diǎn)其他相鄰節(jié)點(diǎn)h的xh是否相等；（3）回溯過(guò)程，如果此時(shí)的節(jié)點(diǎn)值已經(jīng)大于節(jié)點(diǎn)總數(shù)，代表已經(jīng)著色完成，并且找到了一種可行解，此時(shí)可以將可行解數(shù)+1；（4）回溯從最后一個(gè)節(jié)點(diǎn)往上回溯，并一層一層更改節(jié)點(diǎn)至其他可用著色，以此來(lái)找到所有的填色方案。關(guān)鍵代碼void Color:Backtrack(int t)if(t>n) /到達(dá)葉子節(jié)點(diǎn) sum+; /可行解+1 cout<<"著色：

3、 " for(int i=1;i<=n;i+) /輸出可行解方案 cout<<xi<<" " cout<<endl; else for(int i=1;i<=m;i+) xt=i; if(ok(t) Backtrack(t+1);/回溯，繼續(xù)尋找下一層 xt=0;/回到最初狀態(tài)，使x1繼續(xù)嘗試其他填色的可能解 測(cè)試結(jié)果 當(dāng)輸入圖如下時(shí)：12435只要輸入邊即可結(jié)果如下： 當(dāng)輸入的圖如下時(shí)：結(jié)果如下：實(shí)驗(yàn)分析通過(guò)兩個(gè)實(shí)例圖，將m著色問(wèn)題，進(jìn)行了演示，可以看到，實(shí)際上兩個(gè)圖相差很小，可是結(jié)果卻整整翻了一倍，這可以說(shuō)明在越

4、簡(jiǎn)單的圖上，著色問(wèn)題越容易找到解，解的個(gè)數(shù)也就越多。其次在這個(gè)問(wèn)題上我們可以看到它的解空間樹并不是一顆子集樹，而是真?zhèn)€解空間，每一個(gè)結(jié)點(diǎn)都會(huì)將所有的顏色遍歷一遍，從而找到合適的顏色，所以這個(gè)回溯問(wèn)題還是相對(duì)于之前的子集樹和排列樹來(lái)說(shuō)，還是相對(duì)簡(jiǎn)單一點(diǎn)的。實(shí)驗(yàn)心得著色問(wèn)題是最早接觸的回溯法問(wèn)題，一開始起始只知道回溯法就是遇到不能滿足條件的時(shí)候就換一種方法，如果找不到的話就返回到上一個(gè)節(jié)點(diǎn)換一種方式，圖的著色問(wèn)題和其他的著色問(wèn)題很相似，但是更簡(jiǎn)單，因?yàn)樗南拗茥l件只有一個(gè)，即相鄰區(qū)域著色不能相同，當(dāng)轉(zhuǎn)化成抽象圖時(shí)，即兩個(gè)有連線的節(jié)點(diǎn)之間著色不能相同，而且不需要建立一個(gè)子集樹來(lái)進(jìn)行回溯，但是這個(gè)有一

5、個(gè)問(wèn)題就是繼續(xù)尋找下一層之后有一條語(yǔ)句是使xt=0，這條語(yǔ)句之前一直不能理解是什么意思，后來(lái)經(jīng)過(guò)一些數(shù)據(jù)的手動(dòng)測(cè)試，發(fā)現(xiàn)這個(gè)案例使用回溯法是使用了遞歸的方法，因此當(dāng)完成葉子節(jié)點(diǎn)層之后，會(huì)回溯到其上一層，又重新更改其到另一種色號(hào)，在回溯葉子節(jié)點(diǎn)層，當(dāng)這一層的所有顏色都嘗試過(guò)之后，又會(huì)使再上一層的改變色號(hào)，再更改下兩層色號(hào)，這樣做的目的是因?yàn)榛厮莘梢哉业剿械目尚薪?，這樣就通過(guò)回溯找到了所有的可行解。這個(gè)實(shí)驗(yàn)的完成是我更加熟悉了回溯法的原理和思想。實(shí)驗(yàn)得分助教簽名附錄：完整代碼（回溯法）/圖的m著色問(wèn)題 回溯法求解#include<iostream>using namespace s

6、td;class Colorfriend void mColoring(int,int,int *);private:bool ok(int k);void Backtrack(int t);int n, /圖的頂點(diǎn)個(gè)數(shù) m, /可用顏色數(shù)*a, /圖的鄰接矩陣*x; /當(dāng)前解 long sum; /當(dāng)前已找到的可m著色的方案數(shù) ;bool Color:ok(int k) /檢查顏色可用性 for(int j=1;j<=n;j+) if(akj=1)&&(xj=xk) /兩個(gè)點(diǎn)之間有約束且顏色相同 return false;return true;void Color:B

7、acktrack(int t)if(t>n) /到達(dá)葉子節(jié)點(diǎn) sum+; /可行解+1 cout<<"著色： " for(int i=1;i<=n;i+) /輸出可行解方案 cout<<xi<<" " cout<<endl; else for(int i=1;i<=m;i+) xt=i; if(ok(t) Backtrack(t+1);/回溯，繼續(xù)尋找下一層 xt=0;/回到最初狀態(tài)，使x1繼續(xù)嘗試其他填色的可能解 void mColoring(int n,int m,int *a)Col

8、or X;/初始化XX.n=n;X.m=m;X.a=a;X.sum=0;int *p=new intn+1;for(int i=0;i<=n;i+) pi=0;X.x=p;cout<<"頂點(diǎn)： "for(int i=1;i<=n;i+) /用于輸出結(jié)果 cout<<i<<" " ; cout<<endl;X.Backtrack(1); /從頂點(diǎn)1開始回溯delete p;cout<<"解法個(gè)數(shù)："<<X.sum<<endl;int main

9、()int n;int m;cout<<"please input number of node:"cin>>n;cout<<"please input number of color:"cin>>m;int *a=new int*n+1;for(int i=0;i<=n;i+) ai=new intn+1;for(int i=0;i<=n;i+) /利用抽象圖實(shí)現(xiàn)圖的鄰接矩陣 for(int j=0;j<=n;j+) aij=0;int edge; cout<<"please input adjacent edge number:"cin>>edge;int v,w;cout<<"please inout adjacent edge:"<<endl; /只要輸入邊即可for(in