基于回溯法的寶石排序問題研究

《基于回溯法的寶石排序問題研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、基于回溯法的寶石排列問題研究安笙華(2014152148)??摘要本文采用回溯法對排列寶石問題：設(shè)有n種不同的顏色，同一種形狀的n顆寶石分別具有這種不同的顏色?，F(xiàn)有n種不同的形狀的寶石共n2棵，欲將這n2顆寶石排列成n行n列的一個方陣使方陣中每一行每一列的寶石都有n種不同的形狀和n種不同顏色。進(jìn)行了分析，詳細(xì)描述回溯法求解問題時算法的基本思想，并給出具體的算法設(shè)計和時間復(fù)雜度分析，最后對回溯法進(jìn)行了總結(jié)。關(guān)鍵字?回溯法；排列寶石問題；遞歸?1、引言因為回溯法是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法，回溯法求問題的一個解時只要搜索到問題的一個解就可以結(jié)束。它以深度優(yōu)先方式系統(tǒng)搜索問題

2、的解，適合求解組合數(shù)較大的問題，因此，寶石排列問題也常用回溯法來解決。2、所用到的方法簡介確定包含問題的所有解的解空間樹，在包含問題所有解的空間樹中，按照深度優(yōu)先的策略，從開始結(jié)點（根結(jié)點）出發(fā)搜索解空間樹。這個開始節(jié)點稱為活結(jié)點，同時也稱為當(dāng)前擴(kuò)展結(jié)點。在當(dāng)前擴(kuò)展接點處，探索向縱深方向一直一個新結(jié)點。這個新結(jié)點成為新的活結(jié)點，并成為當(dāng)前擴(kuò)展接點。如果當(dāng)前擴(kuò)展接點不能再向縱深方向移動，則當(dāng)前擴(kuò)展結(jié)點就成為死結(jié)點。此時，應(yīng)往回移動（回溯）到最近的活結(jié)點，并使這個活結(jié)點成為當(dāng)前擴(kuò)展結(jié)點。回溯法以這種方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點為止。為了提高回溯發(fā)的搜

3、索效率，避免無效搜索，用回溯法搜索至解空間樹的任一結(jié)點時，總是用剪枝函數(shù)先判斷該結(jié)點是否滿足問題的約束條件。如果滿足進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。否則，不去搜索以該結(jié)點為根的子樹，而是逐層向其祖先結(jié)點回溯。在排列寶石問題中回溯法用剪枝函數(shù)剪去導(dǎo)致不可行的子樹。3、問題分析該問題可以看成n*n的矩陣中每一個元素與其同一行和同一列的元素都不相同。此時我們想到n后問題要求n*n格的棋盤上放置n個彼此不收攻擊的皇后。所以我們的寶石排列問題就可以看做是n后問題的擴(kuò)展，即有n種不同的皇后且每種皇后有n個不同大小。?實驗要求方陣中每一行和每一列的寶石都有n種不同形狀和n種不同顏色，所

4、以問題可以看成n*n的矩陣中每一個元素與其同一行和同一列的元素都不相同。構(gòu)造問題的解空間樹由于每行每列寶石的形狀顏色各不相同，是問題的隱約束，可將其轉(zhuǎn)化為顯約束條件，在算法Backtrack(?)中，當(dāng)row>n時，算法搜索至葉結(jié)點，得到一個新的排列寶石問題的放置方案，就使當(dāng)前以找到的可行方案數(shù)cnt增加1。當(dāng)row

5、種不同顏色。4、算法BackTrace(row,col);if(isOK(row,col)){stone[shape[row][col]][color[row][col]]=false;BackTrace(row,col+1);stone[shape[row][col]][color[row][col]]=true;}BackTrace(row,col+1);àcol>nBackTrace(row+1,col);àrow>n5、結(jié)論#include#defineN9intshape[N][N];//記錄方陣寶石的形狀intcolor[N][N];//記錄方陣寶石的

6、顏色boolstone[N][N];//stone[i][j]表示i形狀的j顏色的石子是否已經(jīng)用過intcnt=0;intn=0;//row行，col列boolisOK(introw,intcol){if(stone[shape[row][col]][color[row][col]]){//如果石子沒有被用過//檢查這一行【檢查將寶石放到該位置是否滿足與該行其他寶石不同形狀，不同顏色的條件】for(inti=1;i

7、

8、color[row][i]==color[row][col]){returnfa

9、lse;}}//檢查這一列【檢查將寶石放到該位置是否滿足與該列其他寶石不同形狀，不同顏色的條件】for(intj=1;j

10、

11、color[j][col]==color[row][col]){returnfalse;}}returntrue;}else{//如果石子已經(jīng)被用過returnfalse;}}voidSwap(int&x,int&y){inttmp=x;x=y;y=tmp;}/