马走日棋盘算法讲课讲稿

1、马走日棋盘算法精品文档马走日棋盘算法问题描述在给定大小的方格状棋盘上 , 将棋子 ”马 ”放在指定的起始位置 , 棋子 ”马 ”的走子的规则为必须在棋盘上走 ”日 ”字 ; 从棋子 ”马 ”的起始位置开始 , 搜索出一条可行的路径 , 使得棋子 ”马 ”能走遍棋盘上的所有落子点 , 而且每个落子点只能走一次 ;例如 : 棋盘大小为5*5 , 棋子马放的起始落子点为( 3 , 3 ) ;算法需要搜索一条从位置( 3 , 3 )开始的一条包括从(1,1),(1,2),(1,3)1),(5(,52,),(5,3),(5,4),(5,5 ) 总共 25 个可以落子的全部位置;问题分析通过上面的问题描述

2、,我们对问题的内容有了正确的理解, 接下来我们开始对问题进行具体细致的分析 ,以求找到解决问题的正确的可行的合理的方法;首先我们需要在程序中用合适的数据结构表示在问题中出现的棋盘, 棋子 , 棋子的走子过程 ; 接下来我们需要对核心问题进行分析, 即如何搜索一条可行的路径, 搜索采取何种策略,搜索的过程如何表示;对于一个大小为 n*m 大小的棋盘 , 棋子从当前位置 ( x , y ) 出发 ,可以到达的下一个位置 ( x , y ):(1) ( x +1 , y +2 )(2) ( x +1 , y 2 )(3) ( x 1, y +2 )(4) ( x 1, y 2 )(5) ( x +2

3、, y +1)(6) ( x +2, y 1)(7) ( x -2, y + 1)(8) ( x -2, y 1 )收集于网络，如有侵权请联系管理员删除精品文档限制条件 :1.1 <= x <= n , 1 <= y <= m;棋盘(n的:高度, m: 棋盘的宽度 );2.( x , y必须是)棋子记录表中没有包括的新位置;3.棋子走子过程记录表中没有包括棋盘上的所有可以落子的位置;对这个过程不停迭代的过程也就是对解空间搜索的过程, 搜索直到棋子走子记录表中包括棋盘上的所有可以落子的位置, 就搜索到了一条可行的路径,路径包括棋盘上的所有落子点;或者搜索完整个解空间,仍然

4、找不到一条可行的解,则搜索失败 ;下面我们举例来说明搜索的过程;棋盘大小:5*5棋子起始位置:(3,3)搜索过程:(1) 从当前位置 ( 3 , 3 ) 出发可以有 8 个新的位置选择 ; 首先选择新位置 1 , 将新位置 1作为当前棋子位置, 开始新的搜索 ;如果搜索不成功 , 则搜索回退 , 选择新位置 2 , 以此类推 , 就可以搜索完整个解空间 ,只要从该问题有解 , 则可以保证一定可以搜索到 ;2) 从新位置 1 开始新的搜索 ,可以选择的新位置有两个 , 先选择位置 1 , 从位置 1 开始新的搜索;(3) 下图是经过 18 步搜索之后的状态 , 从位置 18 出发 , 已经没有没

5、走过的新位置可以选择 , 则搜索失败 ;收集于网络，如有侵权请联系管理员删除精品文档搜索回退到17 步 , 从位置 17 开始搜索除了18 之外的新位置 , 从图上可以看出已经没有新位置可以选择 , 继续回退到16 步 , 搜索除了17 的新位置 ; 以此类推 .知道搜索完整个解空间,或者搜索到一个可行解;(4) 下图展示了搜索成功的整个搜索过程;系统设计一 . 用例图二. 类设计三. 顺序图四 . 核心算法设计通过上面的分析, 我们现在可以将算法的大概框架写出来了, 具体的代码请参考本文章后面的源程序 ;下面我们先列出了经典回溯算法的框架; 由于考虑到程序实现的方便性, 所以本文中采用的回溯

6、算法对经典算法进行了适当的修改;经典算法 :void BackTrack( int t ) if ( t > n ) OutPut( x ); else for( int I = f( n , k ) ; i <=g( n , k ) ; i + ) x t = h ( i ); if ( ConsTraint( t ) && Bound( k ) ) BackTrack( k+ 1 ); 本文采用的算法 : bool Search( Location curLoc )/开始计算 ;收集于网络，如有侵权请联系管理员删除精品文档 m_complex+; / 修改棋盘标

7、志 ; m_chessTable curLoc.x-1 curLoc.y-1 = 1;/是否搜索成功结束标志 ; if( isSuccess() ) return true; /还有未走到的棋盘点 ,从当前位置开始搜索 ; else / 递归搜索未走过的棋盘点; for( int i = 0 ; i < 8 ; i+ ) Location newLocation = GetSubTreeNode( curLoc , i ) ;if( isValide( newLocation ) && m_chessTablenewLocation.x-1newLocation.y-1

8、= 0 ) if( Search( newLocation ) = true ) /填写记录表 ;MarkInTable( newLocation, curLoc ); return true; /搜索失败 ,恢复棋盘标志 ; m_chessTablecurLoc.x-1curLoc.y-1 = 0; return false; 测试数据和测试结果(1). 测试数据 1 :棋盘大小棋子起始位置(1,1)(4,4)(2,3)略搜索到的可行解无无无无搜索解空间大小22232223501略结论 : 对于 4 * 4 和小于 4*4 的棋盘 ,此问题无可行解 ;(2). 测试数据2:棋盘大小:5*5棋

9、子起始位置:(1,1)搜索解空间大小: 76497搜索结果图示:棋子起始位置:(3,3)收集于网络，如有侵权请联系管理员删除精品文档搜索解空间大小: 11077搜索结果图示:结论 : 对于 5*5 的棋盘 ,此问题有可行解 ,搜索解空间大小随棋子的起始位置不同而不同 ,从某些位置起始搜索, 此问题可能没有可行解 ;(3). 测试数据3 :棋盘大小:6*6棋子起始位置:(4,2)搜索到的可行解: 2029720结果图示:(4). 测试数据4:棋盘大小:7*7棋子起始位置:(3,3)搜索解空间大小: 12799463结果图示:结论通过多组数据的测试,我们发现当棋盘的高度height <= 5

10、 ,宽度 width <= 5的时候 , 该棋盘问题的解空间比较小,本文采用的算法可以在很短的时间内搜索完整个解空间;收集于网络，如有侵权请联系管理员删除精品文档当棋盘为5*5 大小 , 整个解空间大小为1829421 = 2 (21) ;由于棋盘和棋子的一些特点( 如 :棋子从当前位置出发只能到达棋盘上的某些特殊点, 而且这些点必须不包含在走子记录表中), 这就给分析棋盘算法的时间复杂度带来了一些困难 , 我们只能通过不同大小棋盘的特点来大概分析算法的时间复杂度 , 通过实际的测试 (在棋盘大小为 5*5 ), 估算的时间复杂度与实际的复杂度基本在一个数量级 ;上图是一个 5*5 大小

11、的棋盘 , 方框所在的位置( 3 , 3 ) 出发可以到达的点有8 个,而下次从 8 个新的搜索点出发平均能到达的有2 个点 , 还有 25 1 8 = 16 个点 , 16 个点中除去 4 个点就剩一般的点没有走过 , 从这 4 个点出发 , 可以到达的新的搜索点平均有 2 个, 当棋盘上的一半以上的点全都走过 ,则从剩余的 12 个点出发可以到达的新的搜索点平均只有 1;通过上面的分析, 我们可以得出Space( 5*5 ) = 8 * pow( 2, 8 ) * pow( 2 , 4 ) * 12 = pow( 2 ,20 );同理 ,我们可以对棋盘大小为8*8 的解空间大小进行估算; 当然估算当中的一些特殊点的选择是需要一些技巧和实际经验的, 虽然最终结果可能不准确, 但是能够保证基本在一个数量级上 ;Space( 8 * 8 ) = pow( 4 , 8 ) * pow( 4 , 4 ) * pow( 2 , 20 ) * pow( 2 , 32 );可以看出 ,解空间是相当大的, 我们假设计算机每分种搜索300 万步 , 对于棋子 ”马 ”给定一个起始位置 , 要想证明此问题无解, 则需要搜索的时间为( 下面数字均为估计值) :Time( 8 * 8 ) = Space ( 8 * 8 ) / 300万 = pow( 2