马走日棋盘算法_第1页
马走日棋盘算法_第2页
马走日棋盘算法_第3页
马走日棋盘算法_第4页
马走日棋盘算法_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

马走日棋盘算法问题描述在给定大小的方格状棋盘上, 将棋子”马”放在指定的起始位置 , 棋子”马” 的走子的规则为必须在棋盘上走”日”字; 从棋子”马”的起始位置开始, 搜索出一条可行的路径, 使得棋子”马”能走遍棋盘上的所有落子点, 而且每个落子点只能走一次; 例如: 棋盘大小为5*5 , 棋子马放的起始落子点为 ( 3 , 3 ) ; 算法需要搜索一条从位置( 3 , 3 ) 开始的一条包括从( 1 , 1 ) , ( 1 , 2 ) , ( 1 , 3 ) ( 5 , 1 ) , ( 5 , 2 ) , ( 5 , 3 ) , ( 5 , 4 ) , ( 5 , 5 ) 总共25个可以落子的全部位置;问题分析通过上面的问题描述,我们对问题的内容有了正确的理解,接下来我们开始对问题进行具体细致的分析,以求找到解决问题的正确的可行的合理的方法;首先我们需要在程序中用合适的数据结构表示在问题中出现的棋盘 , 棋子 , 棋子的走子过程 ; 接下来我们需要对核心问题进行分析, 即如何搜索一条可行的路径 , 搜索采取何种策略 , 搜索的过程如何表示 ;对于一个大小为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, y +1)(6) ( x +2, y 1)(7) ( x -2, y + 1)(8) ( x -2, y 1 )限制条件:1. 1 = x = n , 1 = y 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+; /修改棋盘标志; 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 = 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棋子起始位置 : ( 1 , 1 )搜索解空间大小 : 76497搜索结果图示 :棋子起始位置 : ( 3 , 3 )搜索解空间大小 : 11077搜索结果图示 :结论: 对于5*5 的棋盘 ,此问题有可行解,搜索解空间大小随棋子的起始位置不同而不同,从某些位置起始搜索 , 此问题可能没有可行解; (3). 测试数据3 :棋盘大小 : 6 * 6棋子起始位置 : ( 4 , 2 )搜索到的可行解 : 2029720结果图示 :(4). 测试数据4:棋盘大小 : 7 * 7棋子起始位置 : ( 3 , 3 )搜索解空间大小 : 12799463结果图示 :结论通过多组数据的测试,我们发现当棋盘的高度 height = 5 , 宽度 width = 5 的时候, 该棋盘问题的解空间比较小,本文采用的算法可以在很短的时间内搜索完整个解空间 ; 当棋盘为5*5 大小 , 整个解空间大小为1829421 = 2 (21) ; 由于棋盘和棋子的一些特点 ( 如: 棋子从当前位置出发只能到达棋盘上的某些特殊点, 而且这些点必须不包含在走子记录表中), 这就给分析棋盘算法的时间复杂度带来了一些困难, 我们只能通过不同大小棋盘的特点来大概分析算法的时间复杂度, 通过实际的测试(在棋盘大小为5*5 ), 估算的时间复杂度与实际的复杂度基本在一个数量级;上图是一个5*5大小的棋盘 , 方框所在的位置 ( 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 , 76 ) / 300万 = pow( 2

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论