基于回溯法的寶石排序問(wèn)題研究.docx

基于回溯法的寶石排列問(wèn)題研究安笙華(2014152148)摘要 本文采用回溯法對(duì)排列寶石問(wèn)題：設(shè)有n種不同的顏色，同一種形狀的n顆寶石分別具有這種不同的顏色?，F(xiàn)有n種不同的形狀的寶石共n2棵，欲將這n2顆寶石排列成n行n列的一個(gè)方陣使方陣中每一行每一列的寶石都有n種不同的形狀和n種不同顏色。進(jìn)行了分析，詳細(xì)描述回溯法求解問(wèn)題時(shí)算法的基本思想，并給出具體的算法設(shè)計(jì)和時(shí)間復(fù)雜度分析，最后對(duì)回溯法進(jìn)行了總結(jié)。關(guān)鍵字 回溯法；排列寶石問(wèn)題；遞歸1、引言 因?yàn)榛厮莘ㄊ且粋€(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法，回溯法求問(wèn)題的一個(gè)解時(shí)只要搜索到問(wèn)題的一個(gè)解就可以結(jié)束。它以深度優(yōu)先方式系統(tǒng)搜索問(wèn)題的解，適合求解組合數(shù)較大的問(wèn)題，因此，寶石排列問(wèn)題也常用回溯法來(lái)解決。2、所用到的方法簡(jiǎn)介 確定包含問(wèn)題的所有解的解空間樹(shù)，在包含問(wèn)題所有解的空間樹(shù)中，按照深度優(yōu)先的策略，從開(kāi)始結(jié)點(diǎn)（根結(jié)點(diǎn)）出發(fā)搜索解空間樹(shù)。這個(gè)開(kāi)始節(jié)點(diǎn)稱為活結(jié)點(diǎn)，同時(shí)也稱為當(dāng)前擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展接點(diǎn)處，探索向縱深方向一直一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)成為新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展接點(diǎn)。如果當(dāng)前擴(kuò)展接點(diǎn)不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）到最近的活結(jié)點(diǎn)，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)?；厮莘ㄒ赃@種方式遞歸的在解空間中搜索，直至找到所要求的解或解空間中已無(wú)活結(jié)點(diǎn)為止。為了提高回溯發(fā)的搜索效率，避免無(wú)效搜索，用回溯法搜索至解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，總是用剪枝函數(shù)先判斷該結(jié)點(diǎn)是否滿足問(wèn)題的約束條件。如果滿足進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。否則，不去搜索以該結(jié)點(diǎn)為根的子樹(shù)，而是逐層向其祖先結(jié)點(diǎn)回溯。在排列寶石問(wèn)題中回溯法用剪枝函數(shù)剪去導(dǎo)致不可行的子樹(shù)。3、問(wèn)題分析 該問(wèn)題可以看成n*n的矩陣中每一個(gè)元素與其同一行和同一列的元素都不相同。此時(shí)我們想到n后問(wèn)題要求n*n格的棋盤上放置n個(gè)彼此不收攻擊的皇后。所以我們的寶石排列問(wèn)題就可以看做是n后問(wèn)題的擴(kuò)展，即有n種不同的皇后且每種皇后有n個(gè)不同大小。實(shí)驗(yàn)要求方陣中每一行和每一列的寶石都有n種不同形狀和n種不同顏色，所以問(wèn)題可以看成n*n的矩陣中每一個(gè)元素與其同一行和同一列的元素都不相同。構(gòu)造問(wèn)題的解空間樹(shù)由于每行每列寶石的形狀顏色各不相同，是問(wèn)題的隱約束，可將其轉(zhuǎn)化為顯約束條件，在算法Backtrack()中，當(dāng)rown時(shí)，算法搜索至葉結(jié)點(diǎn)，得到一個(gè)新的排列寶石問(wèn)題的放置方案，就使當(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)用過(guò)int cnt = 0;int n = 0;/row行，col列bool isOK(int row,int col)if(stoneshaperowcolcolorrowcol) /如果石子沒(méi)有被用過(guò) /檢查這一行【檢查將寶石放到該位置是否滿足與該行其他寶石不同形狀，不同顏色的條件】 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)被用過(guò)了 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算法分析本文用回溯法和遞歸法很好的求解了排列寶石問(wèn)題。回溯法有“通用解題法”之稱，在搜索過(guò)程中動(dòng)態(tài)地產(chǎn)生問(wèn)題的解空間，系統(tǒng)地搜索問(wèn)題的所有解。當(dāng)搜索到解空間樹(shù)的任一結(jié)點(diǎn)時(shí)，判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果該結(jié)點(diǎn)肯定不包含，則“見(jiàn)壁回頭”，跳過(guò)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯，可大大縮減無(wú)效操作，提高搜索效率。因此，結(jié)合具體案例的實(shí)際設(shè)計(jì)合適的回溯點(diǎn)是應(yīng)用回溯法的關(guān)鍵所在。而遞歸具有回溯的功能，用遞歸回溯可探索出問(wèn)題的所有解?；厮莘ǖ臅r(shí)間復(fù)雜度因案例的具體實(shí)際而異。對(duì)于不同的實(shí)例，回溯法的計(jì)算時(shí)間有很大的差異。對(duì)于很多具有大n的求解實(shí)例，應(yīng)用回溯法一般可在很短的時(shí)間內(nèi)求得其解，可見(jiàn)回溯法不失為一種快速有效的算法。5.2時(shí)間復(fù)雜度分析 對(duì)于排列寶石問(wèn)題，計(jì)算可行性約束需要的時(shí)間p(n),在最優(yōu)情況下需比較2n次，p(n)=2n。時(shí)間復(fù)雜度為o(2n)在最壞的情況下有n！個(gè)結(jié)點(diǎn)需要計(jì)算可行性約束條件，故時(shí)間復(fù)雜o(p(n)n!)回溯法的效率很大程度上依賴于以下因素：（