马踏棋盘算法分析

1、问题描述:
      M行、N列棋盘，棋子从起始点P1按照中国象棋“马”的z走法，走跳遍所有点，每个点仅能走一次，最后一步跳至目的点P2。
2、算法分析:
      有可采用两种算法，深度优先搜索(DFS)和广度优先搜索(BFS)。两种算法优劣可参考人工智能书籍中关于状态空间搜索算法分析。本人认为，只要方法得当，两种算法均可以求得问题的全部解。而针对“马踏棋盘”这个问题，DFS缺在效率上高于BFS，BFS求解过程的存贮空间需求要远低于BFS。DFS算法需要1个链栈表作为辅助，BFS算法需要2个双向链表。
3、实现伪码:
     以下伪码实现DFS算法，函数返回TRUE表明求出一个解，数组BOARD 中各个元素值即为行走步骤。也可以逆向访问栈求解。修改部分代码可以求得全部通路，但是求解时间可能特别长(M=N=5,P1={0,0},P2={4,4}情况下求得全部解56个解时间在1秒左右)。

#define M  5
#define N  5

ElemType{POINT pt; BOOL expanded; void* parent;} 链表节点数据类型
STACK OPEN；
int BOARD[M][N]；//棋盘数组

int ExpandNode(POINT pt,POINT* pts);//根据某种策略扩展节点pt并保存在pts,返回扩展总数。

BOOL  SearchByDFS(POINT P1,POINT P2)    /*POINT P1,P2入口、出口点*/
{
 ListNode tail,head;
 POINT ptsExpanded[7];
 int  Marked=0;

 ElemType append,data={P1,FALSE,NULL};
 Push( OPEN,data );   
 BOARD[P1]=++marked;

 while(NULL!=(tail=GetTop(OPEN)))//GetTop()返回栈顶指针
 {
    data=tail.data;
    if( Marked==M*N && data.pt==P2) //最后一步并且是目标节点，OK
 {
      BOARD[data.pt]=++marked;
   return TRUE;
 }

   if( data.expanded==TRUE )//该节点已经扩展过则移除
   {
      BOARD[data.pt]=0;   --marked;
      Pop( OPEN );
      continue;
   }

   tail->data.expanded=true; BOARD[data.y][data.x]=++marked; //首先标记
   numExpanded=ExpandNode( data.pt, ptsExpanded[]);//扩展节点
   for(i=0;i<numExpanded;++)
   {
     append={ptsExpanded[ i],   FALSE,   (void *)tail };
     Push(OPEN, append); //扩展节点放入OPEN表
   }
 }//end while
}

4。节点扩展策略：

     函数ExpandNode(POINT pt,POINT* pts)的策略将极大影响求解效率及解的顺序。8个方位可供测试，若在棋盘上，再测试该点没有走过（BOARD[pt] ==0），若是目标点P2则应该满足当前已经走过的点数(marked)等于MN-1。

责任编辑 webmaster

相关链接

蒙特卡罗算法在围棋游戏AI中的...

背包问题的算法集

负载均衡的基本算法

算法—用栈实现递归

QQ程序的加密算法-C#版

欧几里德算法和Stein算法

银行家算法及流程图

字符串匹配之BM算法