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

《骑士巡游问题的回溯法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析课程论文骑士巡游问题的回溯法分析学院：信息工程学院姓名：学号：指导老师：问题描述：骑士巡游（knight'stour）问题是指在有8×8方格的国际象棋棋盘上进行奇异的骑士“L型”（L-shaped）移动的问题。在国际象棋棋盘8×8方格上的某个格子上放置一个骑士，然后这个骑士只能以马跳的方式前进，要求这个骑士相继地到达所有的64个方格，进入每个方格一次且仅进入一次。问题分析：“L型”移动：骑士的步进方式是按照“L型”移动的，即如下图所示，假设骑士的当前位于粉色格子的位置，那么它的下一

2、步可能出现的合法位置为绿色格子的位置。如此，我们定义坐标系，棋盘左上角格子为坐标原点（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)。如此，骑士没进一步都按照此方式步进，直至整个棋盘都被“游走”一遍则完成。边界情况分析：在骑士“巡游”的过程中难免会游走到棋盘的边缘，那么此时下一步的坐标位置可

3、能超出棋盘边界，此种情况下，需要相关的限定代码予以限制。此外，因为要求棋盘每个位置要巡游且只巡游一次，所以当骑士巡游到某一位置时，可能会出现，棋盘没有被巡游完全，但不存在合法的下一步坐标点，此种情况下，则涉及到回溯的问题。回溯算法的相关介绍：回溯法总述：回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。回溯法的深度优先搜索策

4、略：回溯法的基本做法是搜索，或是一种组织得井井有的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的主要思想：回溯法在搜索解空间树时,通常采用两种策略避免无效搜索:其一是用约束函数在扩展结点处剪去不满足约束的子树;其二是用限界

5、函数剪去得不到最优解的子树.这两类函数统称为剪枝函数。回溯法的解题步骤：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。骑士巡游问题的回溯法分析：骑士巡游问题中骑士每进一步都会面临下一步的多种选择，最终解也由N步的单步解构成，若尝试到某一步时发现已经无法继续，就返回到前一步，修改已经做出的上一步，然后再继续向后步进。这样，直到回溯到第一步，并且已经将第一步的所有可能情况都尝试过之后，即可得出问题的全部解。

6、而边界情况是得到解的约束条件，即可据此获得剪枝函数。由此问题分析我们发现，骑士巡游问题求解过程恰与回溯法求解问题的思路相符合，则此问题可以用回溯法来求解。算法设计：算法描述：把棋盘左上角看作坐标原点，往右是x坐标正方向，往下是y坐标正方向。输入开始巡游的坐标，把每个格子初始化为没走过（visited[i][j]=false）。把初始坐标记做第1步（step=1），第1个格子标记为走过（visited[row-1][col-1]=true）。开始计算走法。首先计算每个格子下一步可能的走法，一共有8

7、种，用循环把每一种走法都进行计算。判断是否超出棋盘和是否被标记走过（is_legal(x,y)&&(visited[cur_x][cur_y]==flase)），如不成立，则跳出判断语句；用select_direction()函数尝试下一步。如果成立，则标记此格走过（visited[cur_x][cur_y]=true）。并记录步数（step++）。判断是否已经走完所有格子（k=N*N）,如果成立，则说明没走完，递归到计算函数接着走棋盘；如果不成立，则说明已经走完所有格子，标记已经完成巡游。然后

8、输出巡游结果。这样当所有方案都输出后，结束程序。如果从这某个格子开始，无法走遍所有格子，则巡游没完成，则程序判断从此点出发无法巡游棋盘的每一个位置。回溯说明：此程序的回溯关键在于递归上，根据递归算法的特性，函数中调用递归函数，则进入递归，重新进入函数，当递归结束时，跳出，接着刚才函数的下面的语句运行。程序中，假设已经走到第K步，进入递归，走第K+1步，如果发现第K+1步走不下去，即是说，（is_legal(x,y)&&(visited[cur_x][cur_y]==tlase)）不成立，则跳出，