用回溯法求解圖的m著色問題

1、 實驗二 用回溯法求解圖的m著色問題1、 實驗?zāi)康?1、掌握回溯法求解問題的一般特征和步驟 2、使用回溯法編程求解圖的m著色問題。2、 實驗原理回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的的搜索算法?；厮莘ㄔ诎瑔栴}的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點出發(fā)搜索解空間樹。算法搜索至解空間樹的任何一個結(jié)點時，總是先判斷該結(jié)點是否肯定不包含問題的解，如果肯定不包含，則跳過對以該結(jié)點為根的子樹搜索。否則，進入該子樹，繼續(xù)按深度優(yōu)先的策略進行搜索?；厮莘ㄔ谟脕砬髥栴}的所有解時，要回溯到根，且根結(jié)點的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可結(jié)束。回溯法

2、從開始結(jié)點(根結(jié)點)出發(fā)，以深度優(yōu)先搜索的方式搜索整個解空間。這個開始結(jié)點就成為一個活結(jié)點，同時也成為當(dāng)前的擴展結(jié)點。在當(dāng)前的擴展結(jié)點處，搜索向縱深方向移至一個新結(jié)點。這個新結(jié)點就成為一個新的活結(jié)點，并成為當(dāng)前擴展結(jié)點。如果在當(dāng)前的擴展結(jié)點處不能再向縱深方向移動，則當(dāng)前的擴展結(jié)點就成為死結(jié)點。此時，應(yīng)往回移動(回溯)至最近的一個活結(jié)點處，并使這個活結(jié)點成為當(dāng)前的擴展結(jié)點?；厮莘匆赃@種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點時為止。3、 問題描述給定一個無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。若一個圖最少需要m種顏色才能使圖中

3、任何一條邊連接的2個頂點著有不同的顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。設(shè)計一個算法，找出用m種顏色對一個圖進行著色的不同方案。四、算法設(shè)計與分析用鄰接矩陣a來表示一個無向連通圖G=(V,E)。用整數(shù)1,2,m來表示m種不同的顏色。xi表示頂點i所著的顏色來，則問題的解向量可以表示為n元組x1:n。問題的解空間可表示一棵高度為n+1的完全m叉樹。解空間樹的第i層中每一結(jié)點都有m個兒子，每個兒子相應(yīng)于xi的m個可能的著色之一，第n+1層結(jié)點均為葉結(jié)點。在回溯算法Backtrack中，當(dāng)in時，表示算法已搜索至一個葉結(jié)點，得到一個新的m著色方案，因此當(dāng)前已

4、找到的可m著色方案數(shù)sum增1。當(dāng)in時，當(dāng)前擴展結(jié)點Z是解空間樹中的一個內(nèi)部結(jié)點。該結(jié)點有xi=1,2,m。對當(dāng)前擴展結(jié)點Z的每一個兒子結(jié)點,由函數(shù) Ok檢查其可行性，并以深度優(yōu)先的方式遞歸地對可行子樹進行搜索，或剪去不可行子樹。5、 實驗結(jié)果 源程序：#includeusing namespace std;int color100,sum;bool ok(int k,int c100100) for(int i=1;in) for(int i=1;i=n;i+) coutcolori ; coutendl; sum+; else for(int i=1;i=m;i+) colork=i; if(ok(k,c) backtrack(k+1,n,m,c); colork=0; int main() int i,j,n,m; int c100100; coutn; cinm; cout輸入無向圖的鄰接矩陣:n; for(i=1;i=n;i+) for(j=1;jcij; cout著色所有可能的解