马踏算法

⑴ 求数据结构课程设计 马踏棋盘 C语言

没看见你说的是非递归的。

其实我也不懂，碰巧知道答案，在51CTO上下的。 不能插图。
9.3 马踏棋盘（1）
【题目要求】
国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。编写一个C程序，实现马踏棋盘操作，要求用1～64这64个数字标注马移动的路径，也就是按照求出的行走路线，将数字1，2，……64依次填入棋盘的方格中，并输出。
国际象棋中，"马"的移动规则如图9-4所示。

图9-4 "马"的移动规则
如图9-4所示，图中实心的圆圈代表"马"的位置，它下一步可移动到图中空心圆圈标注的8个位置上，该规则叫做"马走日"。但是如果"马"位于棋盘的边界附近，它下一步可移动到的位置就不一定有8个了，因为要保证"马"每一步都走在棋盘中。
【题目分析】
马踏棋盘的问题其实就是要将1，2，…，64填入到一个8*8的矩阵中，要求相邻的两个数按照"马"的移动规则放置在矩阵中。例如数字a放置在矩阵的(i,j)位置上，数字a+1只能放置在矩阵的(i-2,j+1)，(i-1,j+2)，(i+1,j+2)，(i+2,j+1)，(i+2,j-1)，(i+1,j-2)，(i-1,j-2)，(i-2,j-1)之中的一个位置上。将矩阵填满并输出。这样在矩阵中从1，2…遍历到64，就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵，在该矩阵中填有1，2…64这64个数字，相邻数字之间遵照"马走日"的规则。
解决马踏棋盘问题的一种比较容易理解的方法是应用递归的深度优先搜索的思想。因为"马"每走一步都是盲目的，它并不能判断当前的走步一定正确，而只能保证当前这步是可走的。"马"走的每一步棋都是从它当前位置出发，向下一步的8个位置中的1个行走（在它下一步有8个位置可走的情况下）。因此"马"当前所走的路径并不一定正确，因为它可能还有剩下的可选路径没有尝试，如图9-5所示。

图9-5 "马"的可选路径
如图9-5所示，假设最开始"马"位于棋盘的(0,0)的位置，接下来"马"有两处位置可走，即(1,2)和(2,1)。这时"马"是无法确定走2的位置最终是正确的，还是走3的位置最终是正确的。因此"马"只能任意先从一个路径走下去（例如从2的位置）。如果这条路是正确的，那当然是幸运的，如果不正确，则"马"要退回到第一步，继续从3的位置走下去。以后"马"走的每一步行走都遵循这个规则。这个过程就是一种深度搜索的过程，同时也是一种具有重复性操作的递归过程。可以用一棵"探索树"来描述该深度优先搜索过程，如图9-6所示。

图9-6 深度优先搜索过程
"马"的行走过程实际上就是一个深度探索的过程。如图9-6所示，"探索树"的根结点为"马"在棋盘中的初始位置（这里用4*4的棋盘示意）。接下来"马"有两种行走方式，于是根结点派生出两个分支。而再往下一步行走，根结点的两个孩子又能够分别派生出其他不同的"行走路线"分支，如此派生下去，就得到了"马"的所有可能的走步状态。可以想见，该探索树的叶子结点只可能有两种状态：一是该结点不能再派生出其他的"走步"分支了，也就是"马"走不通了；二是棋盘中的每个方格都被走到，即"马"踏遍棋盘。于是从该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过程。
如何才能通过搜索这棵探索树找到这条马踏棋盘的行走路径呢？可以采用深度优先搜索的方法以先序的方式访问树中的各个结点，直到访问到叶结点。如果叶结点是第二种情况的叶结点，则搜索过程可以结束，因为找到了马踏棋盘的行走路径；如果叶结点为第一种情况的叶结点，即走不通了，则需要返回到上一层的结点，顺着该结点的下一条分支继续进行深度优先搜索下去。
因此在设计"马踏棋盘"的算法时可以借鉴前面讲过的图的深度优先遍历算法和二叉树的先序遍历算法。但是在这里并不需要真正地构建这样一棵探索树，我们只需要借用探索树的思想。在实际的操作过程中，所谓的探索树实际就是深度优先搜索的探索路径，每个结点实际就是当前的棋盘状态，而所谓的叶结点要么就是在当前棋盘状态下，"马"无法再进行下一步行走；要么就是马踏棋盘成功。该算法描述可如下：
int TravelChess Board (int x,int y,int tag)
{
chess[x][y] = tag;
if(tag == 64) { return 1;}
找到"马"的下一个行走坐标（x1,y1），如果找到返回flag=1,否则返回flag=0；
while(flag ){
if(TravelChessBoard (x1,y1,tag+1))return 1; /*递归调用TravelChess ， 从x1,y1向下搜索；如果从 x1,y1往下马踏棋盘成功，返回1*/
else
继续找到"马"的下一个行走坐标（x1,y1），如果找到返回flag=1,否则返回flag=0；
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
9.3 马踏棋盘（2）
http://book.51cto.com 2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)
摘要：《妙趣横生的算法（C语言实现）》第9章综合题，，本章将列举一些经典的综合题编程实例。这些题目生动有趣，同时具有一定的难度，因此作者尽量做到讲解深入浅出，把问题讲透彻，讲清楚。同时希望读者能从中得到启发，启迪思维，提高自身的编程水平。本节为大家介绍马踏棋盘。
标签：妙趣横生 C语言实现 妙趣横生的算法（C语言实现）

Oracle帮您准确洞察各个物流环节
9.3 马踏棋盘（2）
该算法中通过函数TravelChess()递归地搜索"马"的每一种走法。其中参数x，y指定 "马" 当前走到棋盘中的位置，tag是标记变量，每走一个棋盘方格，tag自动增1，它标识着马踏棋盘的行走路线。
算法首先将当前"马"处在棋盘中的位置上添加标记tag，然后判断tag是否等于64，如果等于64，说明这是马踏棋盘的最后一步，因此搜索成功，程序应当结束，返回1。否则，找到"马"下一步可以走到的位置(x1,y1)，如果找到这个位置坐标，flag置1，否则flag置0。
下面在flag为1的条件下（即找到x1,y1），递归地调用函数TravelChess()。也就是从x1,y1指定的棋盘中的位置继续向下深度搜索。如果从x1,y1向下搜索成功，即程序一直执行下去，直到tag等于64返回1，那就说明"马"已经踏遍棋盘（马踏棋盘的过程是：先走到棋盘的(x,y）位置，再从(x1,y1)向下深度搜索，走遍全棋盘），于是搜索结束，返回1；否则继续找到"马"的下一个可以行走的坐标(x1,y1)，如果找到这个位置坐标，flag置1，并从(x1,y1)向下重复上述的递归搜索，否则flag置0，本次递归结束。
如果找遍当前位置(x,y)的下一个坐标(x1,y1)（一般情况是8种），但是从(x1,y1)向下继续深度优先搜索都不能成功地"马踏棋盘"（此时flag等于0），则表明当前所处的状态并不处于马踏棋盘的"行走路径"上，也就是说"马"本不应该走到(x,y)的位置上，因此将chess[x][y]置0，表明棋盘中该位置未被走过（擦掉足迹），同时返回0，程序退到上一层的探索状态。
这里应当知道，所谓当前位置(x,y)的下一个坐标(x1,y1)是指"马"下一步可以走到的地方，用坐标(x1,y1)返回。在探索树中它处在(x,y)所在的结点的子结点中，如图9-7所示。

图9-7 (x,y)的下一个坐标(x1,y1)
当前位置(x,y)的下一个坐标(x1,y1)的可选个数由当前棋盘的局面决定。一般情况下是有8种可走的位置（如图9-7所示），但是如果"马"位于棋盘的边缘（如图9-7所示的探索树的根结点）或者8个可选位置中有的已被"马"前面的足迹所占据，在这两种情况下(x1,y1)的可选个数就不是8个了。
上述搜索算法相当于先序遍历探索树，只不过它不一定是将探索树完整地遍历，而是当tag等于64时，也就是棋盘被全部"踏遍"时就停止继续搜索了。
下面给出完整的程序清单供读者参考。
程序清单9-3
/*--------------------------------- 9-3.c --------------------------*/
#include "stdio.h"
#define X 8
#define Y 8
int chess[X][Y];

int nextxy(int *x,int *y,int count) /*找到基于x、y位置的下一个可走的位置*/
{
switch(count)
{
case 0: if(*x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0) {*x =*x+2;*y = *y-1;return 1; } break;
case 1: if(*x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0) {*x = *x+2; *y = *y+1 ;
return 1;}break;
case 2: if(*x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0) {*x = *x+1; *y = *y-2; return 1;} break;
case 3: if(*x+1<=X-1 && *y+2<=Y-1 &&chess[*x+1][*y+2]==0) {*x = *x+1; *y = *y+2;
return 1;}break;
case 4: if(*x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0) {*x = *x-2; *y = *y-1; return 1;} break;
case 5: if(*x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0){*x = *x-2; *y = *y+1; return 1;} break;
case 6:if(*x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0) {*x = *x-1; *y = *y-2;return 1;}break;
case 7: if(*x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0) {*x = *x-1; *y = *y+2;
return 1;}break;
default: break ;
}
return 0;
}

int TravelChessBoard(int x,int y,int tag) /*深度优先搜索地"马踏棋盘"*/
{
int xx1 = x, yy1 = y, flag = 0,a,b ,count = 0 ;
chess[x][y] = tag;
if(tag == X*Y) { return 1;}
flag = nextxy(&x1,&y1,count);
while(flag == 0 && count <7){
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
while(flag ){
if(TravelChessBoard(x1,y1,tag+1))return 1;
xx1 = x;yy1 = y;
countcount = count +1;
flag = nextxy(&x1,&y1,count); /*寻找下一个(x,y)*/
while(flag == 0 && count <7){ /*循环地寻找下一个(x,y)*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
}
if(flag == 0)
chess[x][y] = 0;
return 0;
}
main()
{
int i,j;
for(i=0;i<X;i++)
for(j=0;j<Y;j++)
chess[i][j] = 0;
if(TravelChessBoard(2,0,1)) {
for(i=0;i<X;i++) {
for(j=0;j<Y;j++)
printf("%d ",chess[i][j]);
printf("\n");
}
printf("The horse has travelled the chess borad\n");
}
else
printf("The horse cannot travel the chess board\n");
getche();
}
9.3 马踏棋盘（3）
http://book.51cto.com 2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)
摘要：《妙趣横生的算法（C语言实现）》第9章综合题，，本章将列举一些经典的综合题编程实例。这些题目生动有趣，同时具有一定的难度，因此作者尽量做到讲解深入浅出，把问题讲透彻，讲清楚。同时希望读者能从中得到启发，启迪思维，提高自身的编程水平。本节为大家介绍int nextxy(int *x,int *y,int count)。
标签：妙趣横生 C语言实现 妙趣横生的算法（C语言实现）

Oracle帮您准确洞察各个物流环节
9.3 马踏棋盘（3）
【程序说明】
本程序中应用二维数组chess[8][8]作为8*8的棋盘，"马"每走到棋盘的(i,j)处，就将当前的步数tag赋值给chess[i][j]。为了方便起见，将数组chess设置为外部变量。另外定义字符常量X，Y，它规定棋盘的大小。本程序清单中将X和Y都设置为8。
函数TravelChessBoard()是上述马踏棋盘算法的具体实现。本程序中初始的(x,y)位置为(2,0)，说明"马"从chess[8][8]的chess[2][0]位置开始进行"马踏棋盘"的。在函数TravelChessBoard()中要调用函数nextxy()。
int nextxy(int *x,int *y,int count)
函数nextxy()包含3个参数：x和y为传递下来的"马"当前踏到棋盘上的位置，它是指针变量。变量count的作用是标记调用nextxy()过程的次数，根据count值的不同，返回基于(x,y)的下一个不同的坐标，以此来避免返回同一个坐标，真正实现寻找"针对当前位置(x,y)的下一个位置"的目的。函数nextxy()的作用是找到"马"当前的位置(x,y)的下一个可以行走的位置，并通过指针修改x、y的内容，将下一个位置坐标用变量x、y返回。
"寻找(x,y)的下一个位置坐标"的操作通过代码：
xx1 = x; yy1 = y; /*将坐标(x1,y1)初始化为当前访问的坐标 (x,y)，因为(x,y)不能被改动*/
flag = nextxy(&x1,&y1,count); /*寻找(x,y)下一个位置坐标(x1,y1)*/
while(flag == 0 && count <7){ /*循环地寻找(x,y)的下一个坐标*/
countcount = count + 1;
flag = nextxy(&x1,&y1,count);
}
实现。程序最开始将(x1,y1)初始化为当前坐标(x,y)，因为"马"的当前位置坐标(x,y)不能被轻易改动。然后将&x1、&y1作为函数nextxy的参数传递，并通过参数&x1和&y1返回当前坐标(x,y)的第count个下一个坐标(x1,y1)。只有当flag为1时，才表明找到了下一个坐标，于是循环可以停止。但是如果count的值超过了7，则说明无法找到(x,y)的下一个坐标，也就说明棋走不通了。所谓当前位置(x,y)的"下一个位置"，如图9-8所示。

（点击查看大图）图9-8 (x,y)的"下一个位置"示意
图中实心的圆圈的坐标为(x,y)，它周围的8个空心的圆圈1～8，为当前坐标(x,y)的可选的"下一个"坐标(x1,y1)。每次调用nextxy()都可能得到这8个坐标其中的一个，当参数count为i时，返回圆圈i所处的坐标。这样就保证了不返回同一个坐标。
如果像本程序这样将字符常量X和Y都设置为8，那么程序就执行8*8的马踏棋盘。但是这样一来会非常费时，实践证明应用本程序运算出8*8的马踏棋盘的结果要花几分钟的时间。因此读者在调试程序时可以通过设置X和Y的值减小棋盘的规格，从而更快地得到结果。
本程序的运行结果如图9-9所示。

（点击查看大图）图9-9 程序9-3的运行结果

⑵ 贪婪启发式和贪婪算法的区别是什么

马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。
贪心算法当然也有正确的时候。求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式
所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。其实很多的智能算法（也叫启发式算法），本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解，但是比单纯的贪心算法更靠近了最优解。例如遗传算法，模拟退火算法。

⑶ 马踏棋盘程序解释

实现马走完8×8棋盘的路线；
分步解析：
（1）
step[9][3]={{0,0,0},{1,1,2},{2,1,-2},{3,-1,2},{4,-1,-2},
{5,2,1},{6,2,-1},{7,-2,1},{8,-2,-1}};设定马可走的八个方向，第二维第一个是序号（没什么用），后两个分别得X坐标，Y坐标增量；
（2）
for(i=1;i<=8;i++)
for(j=1;j<=8;j++)
for(k=1;k<=8;k++)
{
x=i;y=j;
x=x+step[k][1];
y=y+step[k][2];
if(x>=1&&x<=8&&y>=1&&y<=8)
a[i][j]++ ; /* initilize array */
}
初始化整个棋盘，a[i][j]表示马在（i，j）上可走的方向个数；例如a[1][1]=2,说明马如果在(1,1)只能走（2，3）和（3，2）；这步为后面做铺垫；
（3）
for(z=1;z<=64;z++)
//标记棋盘的64个可达点，起点为1号，终点为64号，object[m][n]=z；

a[m][n]=0;//每走过一个点，就置该点为0，表示不能再走，（if(a[x][y]!=0) ）；
能走的话（a[i][j])!=0)就选一个小于min的点if(a[x][y]<min) 作为下一步棋； 之所以要选一个a[i][j]最小的点牵扯到一些算法，只有这样才能保证走遍所有点并且不重复。
最后打印，不用说了吧。
大概我想说的就这些。