騎士巡游問(wèn)題的回溯法分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上算法設(shè)計(jì)與分析課程論文 騎士巡游問(wèn)題的回溯法分析 學(xué)院：信息工程學(xué)院 姓名： 學(xué)號(hào)： 指導(dǎo)老師：?jiǎn)栴}描述： 騎士巡游（knight's tour）問(wèn)題是指在有8×8 方格的國(guó)際象棋棋盤(pán)上進(jìn)行奇異的騎士“L 型”（L-shaped）移動(dòng)的問(wèn)題。在國(guó)際象棋棋盤(pán)8×8 方格上的某個(gè)格子上放置一個(gè)騎士，然后這個(gè)騎士只能以馬跳的方式前進(jìn)，要求這個(gè)騎士相繼地到達(dá)所有的64 個(gè)方格，進(jìn)入每個(gè)方格一次且僅進(jìn)入一次。問(wèn)題分析：“L型”移動(dòng)： 騎士的步進(jìn)方式是按照“L型”移動(dòng)的，即如下圖所示，假設(shè)騎士的當(dāng)前位于粉色格子的位置，那么它的下一步可能出現(xiàn)的合法位置為

2、綠色格子的位置。如此，我們定義坐標(biāo)系，棋盤(pán)左上角格子為坐標(biāo)原點(diǎn)（0，0），橫坐標(biāo)X軸以右為正方向，Y軸以下為正方向，當(dāng)前騎士位置為（x，y），則可能出現(xiàn)的位置為(x-2,y+1)、(x-1,y+2)、(x+1,y+2)、(x+2,y+1)、(x+2,y-1)、(x+1,y-2)、(x-1,y-2)、(x-2,y-1)。如此，騎士沒(méi)進(jìn)一步都按照此方式步進(jìn)，直至整個(gè)棋盤(pán)都被“游走”一遍則完成。邊界情況分析：在騎士“巡游”的過(guò)程中難免會(huì)游走到棋盤(pán)的邊緣，那么此時(shí)下一步的坐標(biāo)位置可能超出棋盤(pán)邊界，此種情況下，需要相關(guān)的限定代碼予以限制。此外，因?yàn)橐笃灞P(pán)每個(gè)位置要巡游且只巡游一次，所以當(dāng)騎士巡游到某一

3、位置時(shí)，可能會(huì)出現(xiàn)，棋盤(pán)沒(méi)有被巡游完全，但不存在合法的下一步坐標(biāo)點(diǎn)，此種情況下，則涉及到回溯的問(wèn)題?；厮菟惴ǖ南嚓P(guān)介紹：回溯法總述： 回溯法(探索與回溯法)是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)的點(diǎn)稱為“回溯點(diǎn)”。 回溯法的深度優(yōu)先搜索策略： 回溯法的基本做法是搜索，或是一種組織得井井有的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題?；厮莘ㄔ趩?wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)

4、時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ǖ闹饕枷耄夯厮莘ㄔ谒阉鹘饪臻g樹(shù)時(shí),通常采用兩種策略避免無(wú)效搜索:其一是用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹(shù);其二是用限界函數(shù)剪去得不到最優(yōu)解的子樹(shù).這兩類(lèi)函數(shù)統(tǒng)稱為剪枝函數(shù)?；厮莘ǖ慕忸}步驟： (1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間； (2)確定易于搜索的解空間結(jié)構(gòu)； (3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。騎士巡游問(wèn)題的回溯法分析： 騎士巡游問(wèn)題中騎士每進(jìn)一步都會(huì)面臨下一步的多種選擇，最終解也由N步的單步解

5、構(gòu)成，若嘗試到某一步時(shí)發(fā)現(xiàn)已經(jīng)無(wú)法繼續(xù)，就返回到前一步，修改已經(jīng)做出的上一步，然后再繼續(xù)向后步進(jìn)。這樣，直到回溯到第一步，并且已經(jīng)將第一步的所有可能情況都嘗試過(guò)之后，即可得出問(wèn)題的全部解。而邊界情況是得到解的約束條件，即可據(jù)此獲得剪枝函數(shù)。 由此問(wèn)題分析我們發(fā)現(xiàn)，騎士巡游問(wèn)題求解過(guò)程恰與回溯法求解問(wèn)題的思路相符合，則此問(wèn)題可以用回溯法來(lái)求解。算法設(shè)計(jì)：算法描述： 把棋盤(pán)左上角看作坐標(biāo)原點(diǎn)，往右是x坐標(biāo)正方向，往下是y坐標(biāo)正方向。輸入開(kāi)始巡游的坐標(biāo)，把每個(gè)格子初始化為沒(méi)走過(guò)（visitedij=false）。把初始坐標(biāo)記做第1步（step=1），第1個(gè)格子標(biāo)記為走過(guò)（visitedrow-1co

6、l-1=true）。開(kāi)始計(jì)算走法。首先計(jì)算每個(gè)格子下一步可能的走法，一共有8種，用循環(huán)把每一種走法都進(jìn)行計(jì)算。判斷是否超出棋盤(pán)和是否被標(biāo)記走過(guò)（is_legal(x,y)&&(visitedcur_xcur_y=flase)），如不成立，則跳出判斷語(yǔ)句；用select_direction()函數(shù)嘗試下一步。如果成立，則標(biāo)記此格走過(guò)（visitedcur_xcur_y=true）。并記錄步數(shù)（step+）。判斷是否已經(jīng)走完所有格子（k=N*N）,如果成立，則說(shuō)明沒(méi)走完，遞歸到計(jì)算函數(shù)接著走棋盤(pán)；如果不成立，則說(shuō)明已經(jīng)走完所有格子，標(biāo)記已經(jīng)完成巡游。然后輸出巡游結(jié)果。這樣當(dāng)所有方案

7、都輸出后，結(jié)束程序。如果從這某個(gè)格子開(kāi)始，無(wú)法走遍所有格子，則巡游沒(méi)完成，則程序判斷從此點(diǎn)出發(fā)無(wú)法巡游棋盤(pán)的每一個(gè)位置?；厮菡f(shuō)明： 此程序的回溯關(guān)鍵在于遞歸上，根據(jù)遞歸算法的特性，函數(shù)中調(diào)用遞歸函數(shù)，則進(jìn)入遞歸，重新進(jìn)入函數(shù)，當(dāng)遞歸結(jié)束時(shí)，跳出，接著剛才函數(shù)的下面的語(yǔ)句運(yùn)行。程序中，假設(shè)已經(jīng)走到第K步，進(jìn)入遞歸，走第K+1步，如果發(fā)現(xiàn)第K+1步走不下去，即是說(shuō)，（is_legal(x,y)&&(visitedcur_xcur_y=tlase)）不成立，則跳出，接著剛才函數(shù)(第K步)運(yùn)行，如果發(fā)現(xiàn)第K步也走不下去了，同樣跳出，接著第K-1步運(yùn)行。這樣就實(shí)現(xiàn)了回溯的方法。函數(shù)及變量

8、說(shuō)明：函數(shù)或變量類(lèi)型變量或函數(shù)名意義常量WIDTH棋盤(pán)大小（8*8棋盤(pán)則值為8）常量MAX_DIR供選擇方向數(shù)Int型數(shù)組chessboardWIDTHWIDTH棋盤(pán)數(shù)組（用來(lái)存儲(chǔ)路徑）Int型數(shù)組directionWIDTHWIDTH方向數(shù)組Int型數(shù)組visitedWIDTHWIDTHMAX_DIR 棋盤(pán)標(biāo)記數(shù)組（用來(lái)標(biāo)記單元格是否被訪問(wèn)過(guò)）Int型變量cur_x,cur_y當(dāng)前坐標(biāo)Int型變量step所走步數(shù)Int型數(shù)組var_xMAX_DIR，var_yMAX_DIR下一步，坐標(biāo)的變化情況Int型變量last_direction;最近一次的方向無(wú)返回值函數(shù)init_direction(

9、)方位具體表示無(wú)返回值函數(shù)init_status(int x, int y)初始狀態(tài)無(wú)返回值函數(shù)print()打印結(jié)果（包括格式控制）返回值Int型函數(shù)is_legal(int x, int y)判斷點(diǎn)是否合法返回值Int型函數(shù)is_end()判斷是否巡游完畢返回值Int型函數(shù)select_direction()選擇前進(jìn)方向無(wú)返回值函數(shù)forward()前進(jìn)至下一步無(wú)返回值函數(shù)backward()回溯至上一步返回值Int型函數(shù)tourist()巡游函數(shù)（根據(jù)情況調(diào)用以上兩函數(shù)）返回值Int型函數(shù)main()主函數(shù)程序流程圖：開(kāi)始輸入起始坐標(biāo)開(kāi)始巡游（tourist()）計(jì)算走法(select_

10、direction()N判斷是否合法(is_legal(x, y)NY判斷巡游是否完成(is_end()Y打印巡游過(guò)程(print()結(jié)束程序代碼：專心-專注-專業(yè)#include<stdio.h>#include<memory.h>#define WIDTH 8#define MAX_DIR 8 /表示沒(méi)有方向可選int chessboardWIDTHWIDTH=0; /棋盤(pán)數(shù)組int directionWIDTHWIDTH;int visitedWIDTHWIDTHMAX_DIR = 0;/初始時(shí)為0表明各個(gè)位置的各個(gè)方向都未訪問(wèn)過(guò)int cur_x,cur_y;

11、/當(dāng)前坐標(biāo)int step; /已走的步數(shù)int last_direction; /上一次走的方向/ 下面兩個(gè)數(shù)組用來(lái)記住選擇某個(gè)方向后，推進(jìn)到下一位置時(shí)x方向和y方向的值的變化int var_xMAX_DIR;int var_yMAX_DIR;/八個(gè)方向的坐標(biāo)變化情況void init_direction()var_x0 = -2; var_y0 = -1;var_x1 = -1; var_y1 = -2;var_x2 = 1; var_y2 = -2;var_x3 = 2; var_y3 = -1;var_x4 = 2; var_y4 = 1;var_x5 = 1; var_y5 = 2;

12、var_x6 = -1; var_y6 = 2;var_x7 = -2; var_y7 = 1;/設(shè)置初始狀態(tài)void init_status(int x, int y)step = 1;chessboardxy = step;step +;cur_x = x;cur_y = y;directionxy = MAX_DIR; /每個(gè)位置都沒(méi)有選擇方向last_direction = MAX_DIR; /上一次方向也沒(méi)有init_direction();/輸出巡游結(jié)果void print()int x, y;printf(" +");for (x = 0; x < WI

13、DTH; x+)printf("-+");printf("n");for (x = 0; x < WIDTH; x+) printf(" |");for (y = 0; y < WIDTH; y+) printf("%3d |",chessboardxy);printf("n");printf(" +");for (y = 0; y < WIDTH; y+) printf("-+");printf("n");/判斷走這

14、一步是否可行int is_legal(int x, int y)if( x < 0 | x >= WIDTH)return 0;if( y < 0 | y >= WIDTH)return 0;if( chessboardxy != 0 )return 0;return 1;/判斷是否遍歷完成int is_end()if( step > WIDTH * WIDTH )return 1;elsereturn 0;/判斷是否回到起點(diǎn)int is_back_to_start()if (step = 1) return 1;else return 0;int select_

15、direction()int try_x, try_y, next_x, next_y;int i,j;int count,min_dir;min_dir = MAX_DIR;last_direction = MAX_DIR;for( i = 0; i < MAX_DIR; i+ )try_x = cur_x + var_xi;try_y = cur_y + var_yi;if(is_legal( try_x, try_y ) = 1 && !visitedcur_xcur_yi)/找出可選方向最少的方向count = 0;for( j = 0; j < MAX_D

16、IR; j+ )next_x = try_x + var_xj;next_y = try_y + var_yj;if(is_legal(next_x, next_y) && !visitedcur_xcur_yj)count +;if( count < min_dir )last_direction = i;min_dir = count;if(last_direction = MAX_DIR)return 0; /沒(méi)有方向可選elsereturn 1; /有方向可選void forward()/ 該位置的這個(gè)方向已經(jīng)試探過(guò)了visitedcur_xcur_ylast_d

17、irection = 1;cur_x += var_xlast_direction;cur_y += var_ylast_direction;chessboardcur_xcur_y = step;step +;directioncur_xcur_y = last_direction;last_direction = MAX_DIR;void backward()int i;step -;chessboardcur_xcur_y = 0;/ 將last_direction置為上一位置到(curr_x, curr_y)所選擇的方向last_direction = directioncur_xcu

18、r_y;/把這個(gè)位置的各個(gè)方向都置為未訪問(wèn)過(guò)for( i = 0; i < MAX_DIR; i+ )visitedcur_xcur_yi = 0;/ 根據(jù)這個(gè)方向回溯到上一位置，同時(shí)回溯到上一位置之后，在上一位置再試探時(shí)應(yīng)該從/ last_direction+1的方向開(kāi)始。cur_x -= var_xlast_direction;cur_y -= var_ylast_direction;int tourist()do if (select_direction()forward();elsebackward(); while (!is_back_to_start() && !is_end();if (is_back_to_start()return 0;else return 1;int main()int start_x = 1,start_y = 1;/起始位置坐標(biāo)printf("棋盤(pán)的大小為：%d×%dn",WIDTH,WIDTH);printf(&quo