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

《用回溯法求解圖的m著色問題.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

2、都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可結(jié)束?；厮莘◤拈_始結(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é)點?；厮莘匆赃@種工作方式遞歸地在解空間

3、中搜索，直至找到所要求的解或解空間中已無活結(jié)點時為止。三、問題描述給定一個無向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。若一個圖最少需要m種顏色才能使圖中任何一條邊連接的2個頂點著有不同的顏色，則稱這個數(shù)m為該圖的色數(shù)。求一個圖的色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。設(shè)計一個算法，找出用m種顏色對一個圖進行著色的不同方案。四、算法設(shè)計與分析用鄰接矩陣a來表示一個無向連通圖G=(V,E)。用整數(shù)1,2,…,m來表示m種不同的顏色。x[i]表示頂點i所著的顏色來，則

4、問題的解向量可以表示為n元組x[1:n]。問題的解空間可表示一棵高度為n+1的完全m叉樹。解空間樹的第i層中每一結(jié)點都有m個兒子，每個兒子相應(yīng)于x[i]的m個可能的著色之一，第n+1層結(jié)點均為葉結(jié)點。在回溯算法Backtrack中，當(dāng)i>n時，表示算法已搜索至一個葉結(jié)點，得到一個新的m著色方案，因此當(dāng)前已找到的可m著色方案數(shù)sum增1。當(dāng)i≤n時，當(dāng)前擴展結(jié)點Z是解空間樹中的一個內(nèi)部結(jié)點。該結(jié)點有x[i]=1,2,…,m。對當(dāng)前擴展結(jié)點Z的每一個兒子結(jié)點,由函數(shù)Ok檢查其可行性，并以深度優(yōu)先的方

5、式遞歸地對可行子樹進行搜索，或剪去不可行子樹。五、實驗結(jié)果源程序：#includeusingnamespacestd;intcolor[100],sum;boolok(intk,intc[100][100]){for(inti=1;in){for(i

6、nti=1;i<=n;i++)cout<>n;cin>>m;cout<<"輸入無向圖的鄰接矩陣:";for(i=1;i<=n;i++)for(j

7、=1;j<=n;j++)cin>>c[i][j];cout<<"著色所有可能的解:";backtrack(1,n,m,c);cout<<"著色可能解的總數(shù)為:"<