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

基于回溯法的寶石排列問題研究安笙華(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)搜索問題的解，適合求解組合數(shù)較大的問題，因此，寶石排列問題也常用回溯法來解決。2、所用到的方法簡介 確定包含問題的所有解的解空間樹，在包含問題所有解的空間樹中，按照深度優(yōu)先的策略，從開始結(jié)點（根結(jié)點）出發(fā)搜索解空間樹。這個開始節(jié)點稱為活結(jié)點，同時也稱為當(dāng)前擴展結(jié)點。在當(dāng)前擴展接點處，探索向縱深方向一直一個新結(jié)點。這個新結(jié)點成為新的活結(jié)點，并成為當(dāng)前擴展接點。如果當(dāng)前擴展接點不能再向縱深方向移動，則當(dāng)前擴展結(jié)點就成為死結(jié)點。此時，應(yīng)往回移動（回溯）到最近的活結(jié)點，并使這個活結(jié)點成為當(dāng)前擴展結(jié)點?；厮莘ㄒ赃@種方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已無活結(jié)點為止。為了提高回溯發(fā)的搜索效率，避免無效搜索，用回溯法搜索至解空間樹的任一結(jié)點時，總是用剪枝函數(shù)先判斷該結(jié)點是否滿足問題的約束條件。如果滿足進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。否則，不去搜索以該結(jié)點為根的子樹，而是逐層向其祖先結(jié)點回溯。在排列寶石問題中回溯法用剪枝函數(shù)剪去導(dǎo)致不可行的子樹。3、問題分析 該問題可以看成n*n的矩陣中每一個元素與其同一行和同一列的元素都不相同。此時我們想到n后問題要求n*n格的棋盤上放置n個彼此不收攻擊的皇后。所以我們的寶石排列問題就可以看做是n后問題的擴展，即有n種不同的皇后且每種皇后有n個不同大小。實驗要求方陣中每一行和每一列的寶石都有n種不同形狀和n種不同顏色，所以問題可以看成n*n的矩陣中每一個元素與其同一行和同一列的元素都不相同。構(gòu)造問題的解空間樹由于每行每列寶石的形狀顏色各不相同，是問題的隱約束，可將其轉(zhuǎn)化為顯約束條件，在算法Backtrack()中，當(dāng)rown時，算法搜索至葉結(jié)點，得到一個新的排列寶石問題的放置方案，就使當(dāng)前以找到的可行方案數(shù)cnt增加1。當(dāng)rownBackTrace(row+1,col);rown5、結(jié)論#include #define N 9int shapeNN;/記錄方陣寶石的形狀int colorNN;/記錄方陣寶石的顏色bool stoneNN;/stoneij表示i形狀的j顏色的石子是否已經(jīng)用過int cnt = 0;int n = 0;/row行，col列bool isOK(int row,int col)if(stoneshaperowcolcolorrowcol) /如果石子沒有被用過 /檢查這一行【檢查將寶石放到該位置是否滿足與該行其他寶石不同形狀，不同顏色的條件】 for(int i=1;icol;i+) if(shaperowi=shaperowcol | colorrowi=colorrowcol) return false; /檢查這一列【檢查將寶石放到該位置是否滿足與該列其他寶石不同形狀，不同顏色的條件】 for(int j=1;jn) /排完了最后一行 cnt+; return ;else if(coln) /一行排序完畢，排序下一行 BackTrace(row+1,1);else for(int i=col;i=n;i+) /排列形狀 Swap(shaperowcol,shaperowi); for(int j=col;j=n;j+) /排列顏色 Swap(colorrowcol,colorrowj); if(isOK(row,col) /表示該寶石已經(jīng)被用過了 stoneshaperowcolcolorrowcol = false; BackTrace(row,col+1); stoneshaperowcolcolorrowcol = true; Swap(colorrowcol,colorrowj); Swap(shaperowcol,shaperowi); int main()while(scanf(%d,&n)!=EOF) /初始化工作 cnt = 0; for(int i=1;i=n;i+) for(int j=1;j=n;j+) colorij = j; shapeij = j; stoneij = true; BackTrace(1,1); printf(%dn,cnt);return 0;5.1算法分析本文用回溯法和遞歸法很好的求解了排列寶石問題?；厮莘ㄓ小巴ㄓ媒忸}法”之稱，在搜索過程中動態(tài)地產(chǎn)生問題的解空間，系統(tǒng)地搜索問題的所有解。當(dāng)搜索到解空間樹的任一結(jié)點時，判斷該結(jié)點是否包含問題的解。如果該結(jié)點肯定不包含，則“見壁回頭”，跳過以該結(jié)點為根的子樹的搜索，逐層向其祖先結(jié)點回溯，可大大縮減無效操作，提高搜索效率。因此，結(jié)合具體案例的實際設(shè)計合適的回溯點是應(yīng)用回溯法的關(guān)鍵所在。而遞歸具有回溯的功能，用遞歸回溯可探索出問題的所有解?；厮莘ǖ臅r間復(fù)雜度因案例的具體實際而異。對于不同的實例，回溯法的計算時間有很大的差異。對于很多具有大n的求解實例，應(yīng)用回溯法一般可在很短的時間內(nèi)求得其解，可見回溯法不失為一種快速有效的算法。5.2時間復(fù)雜度分析 對于排列寶石問題，計算可行性約束需要的時間p(n),在最優(yōu)情況下需比較2n次，p(n)=2n。時間復(fù)雜度為o(2n)在最壞的情況下有n！個結(jié)點需要計算可行性約束條件，故時間復(fù)雜o(p(n)n!)回溯法的效率很大程度上依賴于以下因素：（