马踏棋盘贪心算法

1、【问题描述】马的遍历问题。在8x8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。【初步设计】首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：1、输入初始位置坐标x,y；2、步骤c:如果c64输出一个解，返回上一步骤c-(x，y) c计算(x,y)的八个方位的子结点，选出那此可行的子结点循环遍历所有可行子结点，步骤C+重复2显然(2)是一个递归调用的过程，大致如下：void dfs(int x,int y,int count)int i,tx,ty;if(countN*N)output_solution();/输入一个解return;for(I=

2、0;i8;+i)tx=hni.x;/hn保存八个方位子结点ty=hni.y;stxty=count;dfs(tx,ty,count+1);/递归调用stxty=0;这样做是完全可行的，它输入的是全部解，但是马遍历当8x8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也 非常慢。怎么才能快速地得到部分解呢？【贪心算法】其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择出口最小的进 行搜索，出口的意思是在这些子结点中它们的可行子结点的个数，也就是孙子结点越少的越优先跳，

3、为什么要这样选取，这是一种局部调整最优的做法，如 果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现死结点(顾名思义就是没有出口又没有跳过的结点)，这样对下面的搜索纯粹是徒 劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为 为贪心算法，也叫贪婪算法或启发示算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心 策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非

4、常明显的 提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。 在前面的算法基础之上，增添一些程序加以实现： 函数1：计算结点出口多少int ways_out(int x,int y)int i,count=0,tx,ty;if(x0lly=Nlly=Nllsxy0)return -1;/-1表示该结点非法或者已经跳过了for(i=0;i8;+i)tx=x+dxi;ty=y+dyi;if(tx0|ty=N|ty=N)continue;if(stxty=0)+count;return count;函数2：按结

5、点出口进行排序void sortnode(h_node *hn,int n)/采用简单排序法，因为子结点数最多只有8 int i,j,t;h_node temp;for(i=0;in;+i)for(t=i,j=i+1;jn;+j)if(hnj.waysouti)temp=hni;hni=hnt;hnt=temp;函数3：修改后的搜索函数void dfs(int x,int y,int count)int i,tx,ty;h_node hn8;if(countN*N)output_solution();return;for(i=0;i8;+i)/求 子结点和出口hni.x=tx=x+dxi;hn

6、i.y=ty=y+dyi;hni.waysout=ways_out(tx,ty);sortnode(hnoo)；for(ino;hnE. way soufAO+i) ；x!nr for(；A-8 ;+.)-rxnhnE.XrynhnE.y;s【rx=rycounr;dfs(rx Jyoounr+1)；swxsyHo;国港4“ws园港void maR)5-r LFXyfor(iH0;A-N;+.yMI8fwfor5r0;A-N;+j)sesho;prinrf(-Horse jump while N=dnlnpur rhe posiro-n Lo start疽 N)( scanf(=%d%d=RPxy)rs潜辞 wrt whue(XAO