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

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

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

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

4、找到的可m著色方案數(shù)sum增1。當(dāng)in時(shí)，當(dāng)前擴(kuò)展結(jié)點(diǎn)Z是解空間樹中的一個(gè)內(nèi)部結(jié)點(diǎn)。該結(jié)點(diǎn)有xi=1,2,m。對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)Z的每一個(gè)兒子結(jié)點(diǎn),由函數(shù) Ok檢查其可行性，并以深度優(yōu)先的方式遞歸地對(duì)可行子樹進(jìn)行搜索，或剪去不可行子樹。5、 實(shí)驗(yàn)結(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著色所有可能的解