马踏棋盘问题
题目：在8×8的国际象棋盘上，马从任一点出发，只走63步（日字走法），就遍历整个棋盘，找出这样的路径。
这是一个经典题了，我试着用回溯法做了，但是效率太低了。请问哪种算法做这个题效率要高些呢？
还有，能不能用分治法做这个题？
问题点数：0、回复次数：11Top
1 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-05-22 00:13:03 得分 0
#include <stdio.h>
int f[11][11] ;
int adjm[121][121];
long fgf;
void creatadjm(void);
void e(int,int,int,int);
void travel(int,int);
int n,m;
int main()
{
int i,j,k,l;
printf("Input n:");scanf("%d",&n);
m=n*n;
creatadjm();
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
printf("\n");
}
getchar();
printf("Input i,j:");
scanf("%d %d",&i,&j);
l=(i-1)*n+j;
while ((i>0)||(j>0))
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=0;
k=0;
travel(l,k);
printf("%d\n",fgf);fgf=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) printf("%4d",f[i][j]);
printf("\n");
}
getchar();
printf("Input i,j:");scanf("%d %d",&i,&j);
l=(i-1)*n+j;
}
return 0;
}
void creatadjm()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
f[i][j]=0;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
adjm[i][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]==0)
{
f[i][j]=1;
if((i+2<=n)&&(j+1<=n)) e(i,j,i+2,j+1);
if((i+2<=n)&&(j-1>=1)) e(i,j,i+2,j-1);
if((i-2>=1)&&(j+1<=n)) e(i,j,i-2,j+1);
if((i-2>=1)&&(j-1>=1)) e(i,j,i-2,j-1);
if((j+2<=n)&&(i+1<=n)) e(i,j,i+1,j+2);
if((j+2<=n)&&(i-1>=1)) e(i,j,i-1,j+2);
if((j-2>=1)&&(i+1<=n)) e(i,j,i+1,j-2);
if((j-2>=1)&&(i-1>=1)) e(i,j,i-1,j-2);
}
return;
}
void travel(int p,int r)
{
int i,j,q;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j]>r) f[i][j]=0;
r=r+1;
i=((p-1)/n)+1;
j=((p-1)%n)+1;
f[i][j]=r;
fgf++;
//if(r==25)printf("%d\n",p);
/*
printf("i=%d,j=%d,r=%d\n",i,j,r); getchar();
*/
for(q=1;q<=m;q++)
{
i=((q-1)/n)+1;
j=((q-1)%n)+1;
if((adjm[p][q]==1)&&(f[i][j]==0)) travel(q,r);
}
return;
}
void e(int i1,int j1,int i2,int j2)
{
adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
return;
}
Top
2 楼nasi00（莫傲·逍遥）回复于 2005-05-22 00:34:49 得分 0
应该可以抽象成图的问题吧。
把64个点看成是64个顶点，那么如果马可以从一个点跳到另一个点，就可以看成两个顶点之间有一条无向边。那么问题就变成了从一个点找条路能够经过所有的顶点。这是Hamilton路问题。貌似H路问题现在还没有好的解法，回溯的效率还是可以接受的。毕竟8*8并不大。Top
3 楼Zephyrzzz（）回复于 2005-05-22 01:12:16 得分 0
这个问题(8x8的棋盘)可以用登山法做的,每次挑周围八个方向中允许跳位置最多的那个位置来跳就行了.Top
4 楼mostideal（三甲）回复于 2005-05-22 10:51:32 得分 0
dingTop
5 楼lzwei3842（赐缘）回复于 2005-05-22 11:01:29 得分 0
UPTop
6 楼qingyuan18（zealot_tang）回复于 2005-05-22 11:43:35 得分 0
登山法就是贪婪法，讲速度肯定贪婪法快，但讲优化度肯定回溯法好。Top
7 楼nasi00（莫傲·逍遥）回复于 2005-05-22 18:46:02 得分 0
贪心不保证有解阿，高效一点的算法应该就算是启发式搜索了Top
8 楼zhangbiao1981（北冥之鱼）回复于 2005-05-23 09:40:06 得分 0
改用图的路径遍历，效率比回溯法高Top
9 楼flyingdancing2005（返璞归C）回复于 2005-05-23 12:20:17 得分 0
up......Top
10 楼snailcl（蜗牛）回复于 2005-05-24 09:57:45 得分 0
mTop
11 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-05-24 10:11:22 得分 0
贪婪Top
