用回溯法求解圖的m著色問(wèn)題.doc

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

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

2、都已被搜索遍才結(jié)束。而回溯法在用來(lái)求問(wèn)題的任一解時(shí)，只要搜索到問(wèn)題的一個(gè)解就可結(jié)束?；厮莘◤拈_(kāi)始結(jié)點(diǎn)(根結(jié)點(diǎn))出發(fā)，以深度優(yōu)先搜索的方式搜索整個(gè)解空間。這個(gè)開(kāi)始結(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)。回溯法即以這種工作方式遞歸地在解空間

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

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

5、式遞歸地對(duì)可行子樹(shù)進(jìn)行搜索，或剪去不可行子樹(shù)。五、實(shí)驗(yàn)結(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<<"輸入無(wú)向圖的鄰接矩陣:";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ù)為:"<