int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(The_Node->num[i][j]!=End_Node->num[i][j])//遍历数码组比较差距
value++;
}
}
The_Node->evalue=value;
return value
}
2)第二个估值函数的计算：每一个数码和目标位置之间距离总和
case 5:value=abs(i-2)+abs(j-2);break;
case 6:value=abs(i-2)+abs(j-1);break;
case 7:value=abs(i-2)+j;break;
case 8:value=abs(i-1)+j;break;
case 0:value=0;break;
5、判断压入队的子节点数码组（优越点）的评估值，为零则表示搜索完成，退出搜索；
6、跳到步骤（2）；
数据结构：
算法当中的结点用结构体实现：
typedef struct node //八数码结构体
{
int num[N][N];//数码组
int evalue;//评估值，差距
int bandirect;//所屏蔽方向,防止往回推到上一状态,1上2下3左4右
}rear++;
que[rear]=g2;//存储节点到待处理队
if(g2->evalue==0)//为0则,搜索完成
{ g=g2;
i=5;
}
} else {
free(g2);//劣质节点抛弃
g2=NULL;｝
}
｝
}
界面图示：
2）如何以最简洁的方式表达一个结点在其四个方向的扩展
设定一个数组用以存储该结点在每个方位是否可扩展。操作一个结点时先根据空格的位置判断该结点可在哪些方向移动并在数组相应位置1.然后用一个for循环来解决不同方向移动时的相同操作代码的合并和不同操作代码的拆分处理。
部分关键代码：
int move(int tmp) //将空格进行移动操作。
for(int kk=0;kk<9;kk++)
node[n].num[kk]=node[temp].num[kk];
node[n].expension='Y';
node[n].father=temp;
if(same(n)) //判断node[n]是否为最终想得到的状态。
{
printResult();
{
g2->parent=g1;
switch(Direct)//设置屏蔽方向,防止往回推
{
case 1: g2->bandirect=2;break;
case 2: g2->bandirect=1;break;
case 3:g2->bandirect=4;break;
case 4: g2->bandirect=3;break;
printf(">>>>>>>>>>>>>搜索成功<<<<<<<<<<<<<<\n");
exit(1);
}
n++;
}
}
return 1;
}
结果图示及分析
2、A*算法
算法思想：
A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。第一个启发函数定义为“不在位”数码的个数W(n)。显然从当前结点移动到目标结点至少要移动W(n)步才能达到目标，显然有W(n)<=h*(n)。第二个启发函数定义为每个数与其目标位置之间的距离的总和p(n)。同样能断定至少要移动p(n)步才能达到目标，因此有p(n)<=h*(n)。两个算法过程类似,主要是在启发函数的计算过程不一样而已。
{
int tempNum;
int i,j;
int dir[4]={0};
for(j=0;j<9;j++) //判断空格的位置。
if(node[tmp].num[j]==0)
break;
//判断有哪几个方向可以移动
//如果空格不在第一列的位置并且该结点可以往左移动则标记此结点可以往左方向移动。以下类似
tempNum=node[temp].num[j+3];
node[temp].num[j+3]=0; node[n].bandirect='U';
}
//向各方向移动的相同处理
node[temp].num[j]=tempNum;
node[tmp].expension='N';
//存储移动后的结点，从中间结点temp复制
{
//距离计算：用该数码的所处位置与目标结点的横纵坐标绝对值之差
case 1:value=i+j;break;
case 2:value=i+abs(j-1);break;
case 3:value=i+abs(j-2);break;
case 4:value=abs(i-1)+abs(j-2);break;
2
8
3
1
4
7
6
5
1
2
3
8
4
7
6
5
二、设#43;+开发环境。
三、系统已实现的功能
用广度优先搜索算法和两种A*搜索算法实现八数码问题的求解系统。
四、算法思想及分析
1、广度优先搜索算法
算法思想：
这是一种盲目搜索算法。算法主要思想是从初始结点开始依次沿其上下左右四个方向扩展结点，并逐一检查这些后继结点是否为目标结点，若不等于目标结点则把该后继结点插入到数组末尾。然后取数组中未扩展的第一个结点重复以上操作，直到得到目标结点为止或在限定步数以内未得到解。
int Evaluate(Node * The_Node,Node * End_Node)
{
int total_value=0;
int value=0;
int i,j;
for(i=0;i<N;i++)//遍历数组计算每个数码与其目标位置之间的距离
{
for(j=0;j<N;j++)
{
switch(The_Node->num[i][j])
if (j!=6 && j!=7 && j!=8 && node[tmp].bandirect!='D') dir[3]=1;
//遍历某个结点的四个方向进行扩展后继结点
for(i=0;i<4;i++)
{
if (dir[i])
{
//复制原来的结点，防止被改变
for(int k=0;k<9;k++)
node[temp].num[k]=node[tmp].num[k];
2）如何表达结点在四个方向的扩展
采用switch结构根据空格位置判断可以移动的方位并存储待移动后的位置。用for循环遍历一个结点的四个方位。
部分关键代码：
1)第一个估值函数的计算：不在位的数码个数
int Evaluate(Node * The_Node,Node * End_Node)
{
int value=0;//不在位数字的个数
int father; //记录父节点的下标。
}Node;
扩展的结点存储在数组里：
Node node[MAXSIZE]; //将搜索过的状态存储于该数组中。
算法当中遇到的问题和解决方法：
1）如何去表达八个数码的位置和每个结点状态的表示
用一维或二维数组去表示八个数码的位置关系，每个结点包含了一个一维数组（用来表示八个数码的位置关系），可扩展标记（用来标识一个结点是否被扩展过，避免重复扩展），限制移动方向的标记（避免一个结点在一个方向的重复扩展），记录父节点的指针（父节点下标）。
//不同方向移动的不同处理
if(i==0) {//向左移动
tempNum=node[temp].num[j-1];
node[temp].num[j-1]=0;node[n].bandirect='R';
}
elseif(i==1) {//向上移动
tempNum=node[temp].num[j-3];
};
total_value+=value;//所有距离相加
}
}
The_Node->evalue=total_value;
return total_value;
}
3）搜索过程：
while(rear!=front)//队不空
{front++;//出队
g1=que[front];
for(i=1;i<=4;i++)//分别从四个方向推导出新子节点
struct node *parent;//父节点
}Node;
扩展的结点存储在队列里：Node *que[MAX];//队列，用来存放扩展的结点。
算法当中遇到的问题和解决方法：
1）结点的状态表示
每个结点包含了一个二维数组（表示八个数码的位置关系）、每个结点的评估值、移动方向标记（避免一个结点在各方向的重复扩展）、父节点。