骑士巡游问题的回溯法分析

算法设计与分析课程论文骑士巡游问题的回溯法分析学院：信息工程学院姓名：学号：指导老师：问题描述：骑士巡游（knight'stour）问题是指在有8×8方格的国际象棋棋盘上进行奇异的骑士“L型”（L-shaped）移动的问题。在国际象棋棋盘8×8方格上的某个格子上放置一个骑士，然后这个骑士只能以马跳的方式前进，要求这个骑士相继地到达所有的64个方格，进入每个方格一次且仅进入一次。问题分析：“L型”移动：骑士的步进方式是按照“L型”移动的，即如下图所示，假设骑士的当前位于粉色格子的位置，那么它的下一步可能出现的合法位置为绿色格子的位置。如此，我们定义坐标系，棋盘左上角格子为坐标原点（0，0），横坐标X轴以右为正方向，Y轴以下为正方向，当前骑士位置为（x，y），则可能出现的位置为(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)。如此，骑士没进一步都按照此方式步进，直至整个棋盘都被“游走”一遍则完成。边界情况分析：在骑士“巡游”的过程中难免会游走到棋盘的边缘，那么此时下一步的坐标位置可能超出棋盘边界，此种情况下，需要相关的限定代码予以限制。此外，因为要求棋盘每个位置要巡游且只巡游一次，所以当骑士巡游到某一位置时，可能会出现，棋盘没有被巡游完全，但不存在合法的下一步坐标点，此种情况下，则涉及到回溯的问题。回溯算法的相关介绍：回溯法总述：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法的深度优先搜索策略：回溯法的基本做法是搜索，或是一种组织得井井有的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的主要思想：回溯法在搜索解空间树时,通常采用两种策略避免无效搜索:其一是用约束函数在扩展结点处剪去不满足约束的子树;其二是用限界函数剪去得不到最优解的子树.这两类函数统称为剪枝函数。回溯法的解题步骤：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。骑士巡游问题的回溯法分析：骑士巡游问题中骑士每进一步都会面临下一步的多种选择，最终解也由N步的单步解构成，若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经做出的上一步，然后再继续向后步进。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。而边界情况是得到解的约束条件，即可据此获得剪枝函数。由此问题分析我们发现，骑士巡游问题求解过程恰与回溯法求解问题的思路相符合，则此问题可以用回溯法来求解。算法设计：算法描述：把棋盘左上角看作坐标原点，往右是x坐标正方向，往下是y坐标正方向。输入开始巡游的坐标，把每个格子初始化为没走过（visited[i][j]=false）。把初始坐标记做第1步（step=1），第1个格子标记为走过（visited[row-1][col-1]=true）。开始计算走法。首先计算每个格子下一步可能的走法，一共有8种，用循环把每一种走法都进行计算。判断是否超出棋盘和是否被标记走过（is_legal(x,y)&&(visited[cur_x][cur_y]==flase)），如不成立，则跳出判断语句；用select_direction()函数尝试下一步。如果成立，则标记此格走过（visited[cur_x][cur_y]=true）。并记录步数（step++）。判断是否已经走完所有格子（k=N*N）,如果成立，则说明没走完，递归到计算函数接着走棋盘；如果不成立，则说明已经走完所有格子，标记已经完成巡游。然后输出巡游结果。这样当所有方案都输出后，结束程序。如果从这某个格子开始，无法走遍所有格子，则巡游没完成，则程序判断从此点出发无法巡游棋盘的每一个位置。回溯说明：此程序的回溯关键在于递归上，根据递归算法的特性，函数中调用递归函数，则进入递归，重新进入函数，当递归结束时，跳出，接着刚才函数的下面的语句运行。程序中，假设已经走到第K步，进入递归，走第K+1步，如果发现第K+1步走不下去，即是说，（is_legal(x,y)&&(visited[cur_x][cur_y]==tlase)）不成立，则跳出，接着刚才函数(第K步)运行，如果发现第K步也走不下去了，同样跳出，接着第K-1步运行。这样就实现了回溯的方法。函数及变量说明：函数或变量类型变量或函数名意义常量WIDTH棋盘大小（8*8棋盘则值为8）常量MAX_DIR供选择方向数Int型数组chessboard[WIDTH][WIDTH]棋盘数组（用来存储路径）Int型数组direction[WIDTH][WIDTH]方向数组Int型数组visited[WIDTH][WIDTH][MAX_DIR]棋盘标记数组（用来标记单元格是否被访问过）Int型变量cur_x,cur_y当前坐标Int型变量step所走步数Int型数组var_x[MAX_DIR]，var_y[MAX_DIR]下一步，坐标的变化情况Int型变量last_direction;最近一次的方向无返回值函数init_direction()方位具体表示无返回值函数init_status(intx,inty)初始状态无返回值函数print()打印结果（包括格式控制）返回值Int型函数is_legal(intx,inty)判断点是否合法返回值Int型函数is_end()判断是否巡游完毕返回值Int型函数select_direction()选择前进方向无返回值函数forward()前进至下一步无返回值函数backward()回溯至上一步返回值Int型函数tourist()巡游函数（根据情况调用以上两函数）返回值Int型函数main()主函数程序流程图：开始输入起始坐标程序代码：#includestdio.h#includememory.h#defineWIDTH8#defineMAX_DIR8//表示没有方向可选intchessboard[WIDTH][WIDTH]={0};//棋盘数组intdirection[WIDTH][WIDTH];intvisited[WIDTH][WIDTH][MAX_DIR]={0};//初始时为0表明各个位置的各个方向都未访问过intcur_x,cur_y;//当前坐标intstep;//已走的步数intlast_direction;//上一次走的方向//下面两个数组用来记住选择某个方向后，推进到下一位置时x方向和y方向的值的变化intvar_x[MAX_DIR];开始巡游（tourist()）计算走法(select_direction())判断是否合法(is_legal(x,y))判断巡游是否完成(is_end())打印巡游过程(print())结束NNYYintvar_y[MAX_DIR];//八个方向的坐标变化情况voidinit_direction(){var_x[0]=-2;var_y[0]=-1;var_x[1]=-1;var_y[1]=-2;var_x[2]=1;var_y[2]=-2;var_x[3]=2;var_y[3]=-1;var_x[4]=2;var_y[4]=1;var_x[5]=1;var_y[5]=2;var_x[6]=-1;var_y[6]=2;var_x[7]=-2;var_y[7]=1;}//设置初始状态voidinit_status(intx,inty){step=1;chessboard[x][y]=step;step++;cur_x=x;cur_y=y;direction[x][y]=MAX_DIR;//每个位置都没有选择方向last_direction=MAX_DIR;//上一次方向也没有init_direction();}//输出巡游结果voidprint(){intx,y;printf(+);for(x=0;xWIDTH;x++)printf(----+);printf(\n);for(x=0;xWIDTH;x++){printf(|);for(y=0;yWIDTH;y++)printf(%3d|,chessboard[x][y]);printf(\n);printf(+);for(y=0;yWIDTH;y++)printf(----+);printf(\n);}}//判断走这一步是否可行intis_legal(intx,inty){if(x0||x=WIDTH)return0;if(y0||y=WIDTH)return0;if(chessboard[x][y]!=0)return0;return1;}//判断是否遍历完成intis_end(){if(stepWIDTH*WIDTH)return1;elsereturn0;}//判断是否回到起点intis_back_to_start(){if(step==1)return1;elsereturn0;}intselect_direction(){inttry_x,try_y,next_x,next_y;inti,j;intcount,min_dir;min_dir=MAX_DIR;last_direction=MAX_DIR;for(i=0;iMAX_DIR;i++){try_x=cur_x+var_x[i];try_y=cur_y+var_y[i];if(is_legal(try_x,try_y)==1&&!visited[cur_x][cur_y][i])//找出可选方向最少的方向{count=0;for(j=0;jMAX_DIR;j++){next_x=try_x+var_x[j];next_y=try_y+var_y[j];if(is_legal(next_x,next_y)&&!visited[cur_x][cur_y][j])count++;}if(countmin_dir){last_direction=i;min_dir=count;}}}if(last_direction==MAX_DIR)return0;//没有方向可选elsereturn1;//有方向可选}voidforward(){//该位置的这个方向已经试探过了visited[cur_x][cur_y][last_direction]=1;cur_x+=var_x[last_direction];cur_y+=var_y[last_direction];chessboard[cur_x][cur_y]=step;step++;direction[cur_x][cur_y]=last_direction;last_direction=MAX_DIR;}voidbackward(){inti;step--;chessboard[cur_x][cur_y]=0;//将last_direction置为上一位置到(curr_x,curr_y)所选择的方向last_direction=direction[cur_x][cur_y];//把这个位置的各个方向都置为未访问过for(i=0;iMAX_DIR;i++)visited[cur_x][cur_y][i]=0;//根据这个方向回溯到上一位置，同时回溯到上一位置之后，在上一位置再试探时应该从//last_direction+1的方向开始。cur_x-=var_x[last_direction];cur_y-=va