八数码问题实验报告.doc

《八数码问题》实验报告
一、实验目的：
熟练掌握启发式搜索算法。
二、实验内容：
使用启发式搜索算法求解8数码问题。编制程序实现求解8数码问题算法，采用估价函数
，
其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。
三、实验原理：
1. 问题描述：
八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。
要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
2. 原理描述：
启发式搜索
（1）原理
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
（2）估价函数
计算一个节点的估价函数，可以分成两个部分：
1、 已经付出的代价（起始节点到当前节点）；
2、 将要付出的代价（当前节点到目标节点）。
节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即 = + 。
是从初始节点到达当前节点n的实际代价；
是从节点n到目标节点的最佳路径的估计代价。
所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。
（3）算法描述：
① 把起始节点S放到OPEN表中，并计算节点S的；
② 如果OPEN是空表，则失败退出，无解；
③ 从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个
为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点；
④ 把节点从 OPEN 表中移出，并把它放入 CLOSED 的已扩展节点表中；
⑤ 如果是个目标节点，则成功退出，求得一个解；
⑥ 扩展节点，生成其全部后继节点。对于的每一个后继节点：
计算；如果 既不在OPEN表中，又不在CLOCED表中，则用估价函数把
它添入OPEN表中。从加一指向其父节点的指针，以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则
(I)以此新值取代旧值。
(II)从指向，而不是指向他的父节点。
(III)如果节点在CLOSED表中，则把它移回OPEN表中。
⑦ 转向②，即GOTO②。
（3） 算法流程图：

四、 实验结果
输入矩阵： 目标矩阵：
2
8
3

1
2
3
1
4
5

8
0
4
7
6
0

7
6
5

五、 实验小结
通过本次试验，我对启发式搜索有了更加深入的了解。在实验中，通过对两种启发式搜索所扩在的节点数来看，看来比更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。所以，要更好地定义一个估价函数还有待深入讨论。

源代码：
#include"stdio.h"
#define num 3 //宏定义数码的行列数为3

/*显示当前待调整数码矩阵*/
void show(int begin[num][num])
{
for(int i = 0; i < num; i++)
{
for(int j = 0; j < num; j++)
printf("%d ", begin[i][j]);
printf("\n");
}
printf("\n");
}

/*交换数码中的 begin[row_one][column_one] 与 begin[row_two][column_two] 这两个数*/
void exchange(int begin[num][num], int row_one, int column_one, int row_two, int column_two)
{
int temp;
temp = begin[row_two][column_two] ;
begin[row_two][column_two] = begin[row_one][column_one];
begin[row_one][column_one] = temp;
}

/*判断待调整的数码与最终数码相比正确位置数码的个数*/
int judge(int begin[num][num], int end[num][num])
{
int count=0; //count记录数码中正确位置的个数
for(int i = 0; i < num; i++) //检查当前图形的正确度
for(int j = 0; j < num; j++)
{
if(begin[i][j] == end[i][j] && end[i][j] != 0)
count++;
}
return count; //返回数码中正确位置的个数
}

/* 将待调整数码从开始位置移动到终止位置，并将其过程输出*/
int yidong(int begin[num][num], int end[num][num]
, int right, int jishu, int ji_shu[50][3][3]
, int biaoji, int row, int column) //biaoji存储上一轮移动的反方向代号
{
int temp_zhi;
show(begin); //显示数组矩阵
if(jishu >= 20)
return 0;
int node; //,node为标记
int temp; //存储当前待调整数码正确的个数
for(int q=0; q<jishu; q++) //检查交换后的end[][]图形是否先前已经遍历过了
{
node = 1;
for(int w=0; w<num && node; w++)
for(int r=0; r<num && node; r++)
if(ji_shu[q][w][r] != begin[w][r])
node = 0;
if(node == 1) //如果先前遍历过，返回0
{
return 0;
}
}
for(int i = 0; i < num; i++)
for(int j = 0; j < num; j++)
ji_shu[jishu][i][j] = begin[i][j];

if(right == num * num - 1) //如果待调整数码与最终数码完全相同时，返回1
return 1;
if(row > 0 && biaoji != 0) //存储0的位置不是在第一行
{
exchange(begin, row - 1, column, row , column); //将0与其上面的元素交换存储位置
temp = judge(begin, end);
if(temp < right) //如果交换后正确数码的个数不大于原来正确数码的个数
exchange(begin, row - 1, column, row , column); //再将其交换回来
else if(temp >= right) //如果交换后正确数码的个数大于或等于原来正确数码的个数
{
temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 2, row-1, column);
if( temp_zhi == 1) //进行下一步的移动
return 1;
exchange(begin, row - 1, column, row , column); //再将其交换回来
}
}
if(column > 0 && biaoji != 1)
{
exchange(begin, row, column - 1, row , column); //将0与其左边的元素交换存储位置
temp = judge(begin, end);
if(temp < right)
exchange(begin, row, column - 1, row , column);
else if(temp >= right)
{
temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu ,3, row, column - 1);
if(temp_zhi == 1)
return 1;
exchange(begin, row, column - 1, row , column);
}
}

if(row < num-1 && biaoji != 2)
{
exchange(begin, row + 1, column, row , column); //将0与其下面的元素交换存储位置
temp = judge(begin, end);
if(temp < right)
exchange(begin, row + 1, column, row , column);
else if(temp >= right)
{
temp_zhi =yidong(begin, end, temp, jishu+1, ji_shu, 0, row+1, column);
if(temp_zhi == 1)
return 1;
exchange(begin, row + 1, column, row , column);
}
}
if(column < num-1 && biaoji != 3)
{
exchange(begin, row, column + 1, row , column); //将0与其右边的元素交换存储位置
temp = judge(begin, end);
if(temp < right)
exchange(begin, row, column + 1, row , column);
else if(temp >= right)
{
temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 1, row, column+1);
if(temp_zhi == 1)
return 1;
exchange(begin, row, column + 1, row , column);
}
}
return 0; //移动失败，返回0
}

/*有用户输入待调整的数码矩阵最初状态的数，并将其存入到begin[][]数组中*/
void shuru(int begin[][num],int blank[])
{
int temp, node, zero = 0;
for (int i = 0; i < num; i++)
for(int j = 0; j < num; j++)
{
node = 1;
printf("请输入第%d行，第%d列的元素的值：", i+1, j+1);
scanf("%d", &temp);
for (int q = 0; q <= i && node == 1; q++) //当输入的值有重复的，提示重新输入
for (int w = 0; w < j; w++)
if(temp == begin[q][w])
{
printf("输入重复，请重新输入\n");
node = 0;
j--;
break;
}
if(temp < 0 || temp > num*num-1) //当输入的值不是在数码的区间范围内时，提示重新输入
{
printf("请输入从%d到%d的数\n", zero, num*num-1);
node = 0;
j--;
}
if(node == 1) //如果输入满足条件
{
if(temp == 0) //如果输入的值为零，由blank[0]记录行号，blank[1]记录列号
{
blank[0] = i;
blank[1] = j;
}
begin[i][j] = temp;//将满足条件的值存储起来
}
}
}

int main()
{
int jishu = 0, ji_shu[50][3][3];//jishu存储已经遍历过的八数码图形的个数，jishu[][][]存储已经遍历过的八数码图形的形状
int row; //存储数字零的行数
int column; //存储数字零的列数
int begin[num][num], blank[2],count=1;
int end[num][num] = {1, 2, 3, 8, 0, 4, 7, 6, 5}; //给最终状态的数码矩阵赋值
printf ("-------%d数码游戏开始！--------\n", num);
shuru(begin, blank); //输入带调整状态的数码矩阵的值
row = blank[0];
column = blank[1];
if(yidong (begin, end,judge(begin,end),jishu,ji_shu,4,row,column) == 0)
printf("\n此8数码的问题可能无解！");
else
show(begin);
getchar();getchar();
return 0;
}