回溯法實驗圖的m著色問題

1、算法分析與設(shè)計實驗報告第 六 次附加實驗姓名學號班級時間12.26上午地點工訓樓309 實驗名稱回溯法實驗(圖的m著色問題)實驗?zāi)康?. 掌握回溯法求解問題的思想2. 學會利用其原理求解圖的m著色問題實驗原理問題描述：給定無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。是否有一種著色法使G中每條邊的2個頂點著不同顏色。這個問題是圖的m可著色判定問題。若一個圖最少需要m種顏色才能使圖中每條邊連接的2個頂點著不同顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。基本解題步驟：(1) 針對所給問題，定義問題的解空間；(2) 確定易于搜索的

2、解空間結(jié)構(gòu)；(3) 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。實驗步驟（1）首先將給定的圖利用抽象圖表示出來；（2）判斷該節(jié)點k當前的著色是否符合條件，需要判斷xk與k節(jié)點其他相鄰節(jié)點h的xh是否相等；（3）回溯過程，如果此時的節(jié)點值已經(jīng)大于節(jié)點總數(shù)，代表已經(jīng)著色完成，并且找到了一種可行解，此時可以將可行解數(shù)+1；（4）回溯從最后一個節(jié)點往上回溯，并一層一層更改節(jié)點至其他可用著色，以此來找到所有的填色方案。關(guān)鍵代碼void Color:Backtrack(int t)if(t>n) /到達葉子節(jié)點 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ù)嘗試其他填色的可能解 測試結(jié)果 當輸入圖如下時：12435只要輸入邊即可結(jié)果如下： 當輸入的圖如下時：結(jié)果如下：實驗分析通過兩個實例圖，將m著色問題，進行了演示，可以看到，實際上兩個圖相差很小，可是結(jié)果卻整整翻了一倍，這可以說明在越

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

5、個問題就是繼續(xù)尋找下一層之后有一條語句是使xt=0，這條語句之前一直不能理解是什么意思，后來經(jīng)過一些數(shù)據(jù)的手動測試，發(fā)現(xiàn)這個案例使用回溯法是使用了遞歸的方法，因此當完成葉子節(jié)點層之后，會回溯到其上一層，又重新更改其到另一種色號，在回溯葉子節(jié)點層，當這一層的所有顏色都嘗試過之后，又會使再上一層的改變色號，再更改下兩層色號，這樣做的目的是因為回溯法可以找到所有的可行解，這樣就通過回溯找到了所有的可行解。這個實驗的完成是我更加熟悉了回溯法的原理和思想。實驗得分助教簽名附錄：完整代碼（回溯法）/圖的m著色問題 回溯法求解#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, /圖的頂點個數(shù) m, /可用顏色數(shù)*a, /圖的鄰接矩陣*x; /當前解 long sum; /當前已找到的可m著色的方案數(shù) ;bool Color:ok(int k) /檢查顏色可用性 for(int j=1;j<=n;j+) if(akj=1)&&(xj=xk) /兩個點之間有約束且顏色相同 return false;return true;void Color:B

7、acktrack(int t)if(t>n) /到達葉子節(jié)點 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<<"頂點： "for(int i=1;i<=n;i+) /用于輸出結(jié)果 cout<<i<<" " ; cout<<endl;X.Backtrack(1); /從頂點1開始回溯delete p;cout<<"解法個數(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+) /利用抽象圖實現(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