qifashisousuojietiaoma.txt

启发式搜索解跳马 启发式搜索解跳马 启发式搜索解跳马

对于跳马问题一个启发式规则是，在选择当前步的方向时去选择满足下面条件的方向，当按这个方向推进到下一位置时，这个位置所可以再选择的方向最少。也就是说在当前位置优先选一个走起来比较“艰难”的方向来推进。加入这种启发式规则之后，运行效果加快了很多，无论从哪个位置起跳，很快就能找到解。
那么，怎么在上述程序的基础上加入启发式思想呢？首先，引入一个难易矩阵，如下。它表示从每一个点出发，可以朝几个方向跳，换言之，也就是可以有多少方向能到达此点。方向越多，说明越容易跳到。
int accessibility[M][N]=	//   棋盘相应点的难易值
{{   2,3,4,4,4,4,3,2   }	,
  {   3,4,6,6,6,6,4,3   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   3,4,6,6,6,6,4,3   }   ,
  {   2,3,4,4,4,4,3,2   }   };
	要让马先跳难跳的位置，就必须对每一个点的所有方向进行排序，排序后，就是当前点马的跳法策略。在此，可以用冒泡排序进行排序，把马不可能跳的方向也方向(即马会超出边界的方向)也排到后面，这样，马如果在(i,j)点，只要依次跳accessibility[i][j]个方向即可，而后面的方向是不可能跳到的。
加入启发式思想后，对上述程序改进如下。如果想找一条循环路径，即马跳到最后一步之后，再跳一步又回到了起点，只要把go函数里的print_map()上两行加入即可。运用此程序，很快就能找到解。
/*
对于骑士游历问题一个启发式规则是，在选择当前步的方向时去选择满足下面条件的方向，
当按这个方向推进到下一位置时，这个位置所可以再选择的方向最少。
也就是说在当前位置优先选一个走起来比较"艰难"的方向来推进。
*/
//马踏棋盘的递归程序
//棋盘大小：8*8
//起始位置：0,0
#define M 8
#define N 8
＃i nclude <stdio.h>

int map[M][N];
int count=0;
int countnum=0;  //用于统计走法种数
int accessibility[M][N]=	//   棋盘相应点的难易值
{{   2,3,4,4,4,4,3,2   }	,
  {   3,4,6,6,6,6,4,3   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   4,6,8,8,8,8,6,4   }   ,
  {   3,4,6,6,6,6,4,3   }   ,
  {   2,3,4,4,4,4,3,2   }   };

int direction[8][2]={{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2}};//马可能前进的8个方向
int newDirection[8][2];//排序后的方向

void print_map();
bool go(int i,int j);
void sort(int a,int b);

void main()
{
	freopen("out.txt","w",stdout);
	for(int k=0;k<M;k++)
		for(int l=0;l<N;l++)
			map[k][l]=0;
	go(0,0);
	printf("End at:%ld\n",countnum); 
}

bool go(int i,int j)
{
	count++;					//计数器
	map[i][j]=count;			//棋盘置当前步数
	if(count==64)				//如果已经遍历棋盘则打印一次走法
	{
		//for (int a=0;a<8;a++)
		//	if ((i + direction[a][0])==0 && (j + direction[a][1])==0)
				print_map();
	}
	else
	{
		int m,n;
		sort(i,j);
		for (int k=0;k<accessibility[i][j];k++)	//实际上不是每个点都有8个方向，应该是accessibility[i][j]个方向
		{
			m=i+newDirection[k][0];
			n=j+newDirection[k][1];
			if(m>=0 && m<M && n>=0 && n<N)
				if(map[m][n]==0)
				{
					go(m,n);
					sort(i,j);
				}
		}
		//sort(i,j);
	}

	map[i][j]=0;//回退，置零
	count--;//计数器减

	return false;//注意：如果函数没有返回值，会默认返回true
}

void sort(int a,int b)//对(a,b)点的8个方向进行重新排序，把较难走的排在前面
{
	int i,j,swap_x,swap_y;
	for (i=0;i<8;i++)
	{
		newDirection[i][0] = direction[i][0];
		newDirection[i][1] = direction[i][1];
	}
	//冒泡排序：把马越容易跳着的点的方向放到后面；另外，也把不可能的方向放到后面
	for (i=8-1;i>=0;i--)
		for (j=0;j<i;j++)
		{
			if(!(a+newDirection[j+1][0] < 0 || a+newDirection[j+1][0] >= M || b+newDirection[j+1][1] < 0 || b+newDirection[j+1][1] >= N))
			{
				if(a+newDirection[j][0] < 0 || a+newDirection[j][0] >= M || b+newDirection[j][1] < 0 || b+newDirection[j][1] >= N)
				{
					swap_x = newDirection[j][0];
					swap_y = newDirection[j][1];
					newDirection[j][0] = newDirection[j+1][0];
					newDirection[j][1] = newDirection[j+1][1];
					newDirection[j+1][0] = swap_x;
					newDirection[j+1][1] = swap_y;
				}
				else if(accessibility[a+newDirection[j][0]][b+newDirection[j][1]] > accessibility[a+newDirection[j+1][0]][b+newDirection[j+1][1]])
				{
					swap_x = newDirection[j][0];
					swap_y = newDirection[j][1];
					newDirection[j][0] = newDirection[j+1][0];
					newDirection[j][1] = newDirection[j+1][1];
					newDirection[j+1][0] = swap_x;
					newDirection[j+1][1] = swap_y;
				}
			}
		}
}

void print_map()
{
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
			printf("%3d",map[i][j]);
		printf("\n");
	};
	countnum=countnum+1;
	printf("Now Count:%d\n\n",countnum);
}