采用A星算法实现八数码问题.docx
《采用A星算法实现八数码问题.docx》由会员分享，可在线阅读，更多相关《采用A星算法实现八数码问题.docx（17页珍藏版）》请在冰点文库上搜索。
采用A星算法实现八数码问题
人工智能实验一报告
题目：
采用A*算法解决八数码问题
成员：
李文、郭弯弯
学号：
、
专业：
计算机科学与技术
完成日期：
2016/04/09
1、实验要求、目的及分工
1.1实验要求
使用A*算法实现八数码问题，并用图形界面展示。
1.2实验目的
a.熟悉人工智能系统中的问题求解过程；
b.熟悉状态空间的盲目搜索和启发式搜索算法的应用；
c.熟悉对八数码问题的建模、求解及编程语言的应用。
1.3实验分工
我们小组共两个人，共同查找背景资料，李文同学主要负责源代码，郭弯弯同学主要负责实验报告以及演示文稿的完成。
2、实验问题
2.1问题描述
所谓八数码问题是指这样一种游戏：
将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。
放牌时要求不能重叠。
于是，在3×3的数码盘上出现了一个空格。
现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。
空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如下图所示：
1
5
0
4
7
8
3
2
6
8
3
2
4
5
1
6
7
0
（a）初始状态（b）目标状态
图1八数码问题示意图
2.2问题解释
首先，八数码问题包括一个初始状态（START）和目标状态（TRAGET），所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态：
（START>STATE1>STATE2>...>TARGET）
这个状态是否存在就是我们要解决的第一个问题；第二个问题是我们要求出走的路径是什么。
2.3八数码问题形式化描述
初始状态：
初始状态向量：
规定向量中各分量对应的位置，各位置上的数字。
把3×3的棋盘写成一个二维向量。
我们可以设定初始状态：
<1,5,2,4,0,3,6,7,8>
后继函数：
按照某种规则移动数字得到的新向量。
例如：
<1,5,2,4,0,3,6,7,8>→<1,0,2,4,5,3,6,7,8>
路径耗散函数：
规定每次移动代价为1，即每执行一条规则后总代价加1。
2.4解决方案选择
该问题是一个搜索问题。
它是一种状态到另一种状态的变换。
要解决这个问题，必须先把问题转化为数字描述。
由于八数码是一个3*3的矩阵，但在算法中不是用矩阵，而是将这个矩阵转化为一个二维数组，使用这个二维数组来表示八数码，但是移动时要遵守相关规则。
按规则，每一次可以将一个与空格相邻的棋子移动到空格中，实际上也可以看做空格的相反方向移动。
空格的移动方向可以是上下左右，当然不能出边界。
棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化。
经分析，问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。
这个寻找的过程就是状态空间搜索。
常用的状态空间搜索有深度优先和广度优先。
广度优先是从初始状态一层一层向下找，直到找到目标为止。
深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。
这样可以省略大量无畏的搜索路径，提高了效率。
所以，本实验采用启发式A*搜索算法来实现。
3、A*算法
3.1算法介绍
A*算法是一种常用的启发式搜索算法。
在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。
A*算法的估价函数可表示为：
f'（n）=g'（n）+h'（n）
这里，f'（n）是估价函数，g'（n）是起点到终点的最短路径值（也称为最小耗费或最小代价），h'（n）是n到目标的最短路经的启发值。
由于这个f'（n）其实是无法预先知道的，所以实际上使用的是下面的估价函数：
f（n）=g（n）+h（n）
其中g（n）是从初始结点到节点n的实际代价，h（n）是从结点n到目标结点的最佳路径的估计代价。
在这里主要是h（n）体现了搜索的启发信息，因为g（n）是已知的。
用f（n）作为f'（n）的近似，也就是用g（n）代替g'（n），h（n）代替h'（n）。
这样必须满足两个条件：
（1）g（n）>=g'（n）（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。
（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h（n）<=h'（n）。
第二点特别的重要。
可以证明应用这样的估价函数是可以找到最短路径的。
3.2算法伪代码
首先定义两个表，open表用于存放已经生成，且已用启发式函数进行过估计或评价，但尚未产生它们的后继节点的那些结点，这些结点也称未考察结点；
closed表用于存放已经生成，且已考察过的结点。
把起始格添加到"开启列表"
do
{
寻找开启列表中F值最低的格子,我们称它为当前格
把它切换到关闭列表
对当前格相邻的8格中的每一个
if（它不可通过||已经在"关闭列表"中）
{
什么也不做
}
if（它不在开启列表中）
{
把它添加进"开启列表"，把当前格作为这一格的父节点,计算这一格的FGH
if（它已经在开启列表中）
{
if（用G值为参考检查新的路径是否更好，更低的G值意味着更好的路径）
{
把这一格的父节点改成当前格，并且重新计算这一格的GF值
}
}while（目标格已经在"开启列表"，这时候路径被找到）
如果开启列表已经空了，说明路径不存在
最后从目标格开始，沿着每一格的父节点移动直到回到起始格，这就是路径。
四、算法实现
4.1实验环境
（1）实验环境：
Windows7
（2）IDE：
codeblocks（图形界面的实现调用codeblocks里windows一系列函数）
4.2数据结构
本实验主要使用链表：
//定义状态图中的结点数据结构
typedefstructNode
{
intdata[3][3];//结点所存储的状态
structNode*parent;//指向结点的父亲结点
structNode*child;//用于指向临时子节点，并且用于最后的最佳路径上结点的子结点
structNode*next;//指向open或者closed表中的后一个结点
intfvalue;//结点的总的路径
intgvalue;//结点的实际路径
inthvalue;//结点的到达目标的苦难程度
}NNode,*PNode;
/***定义两个全局链表***/
PNodeOPEN,CLOSE;
4.3实验结果截屏
4.4参考资料
资料来源XX搜索，博客查找
链接：
5、实验心得
1、学习了新的算法——A*算法，结合了伪代码和网上的一些教程，实现了八数码问题的求解，这是对我们编程能力的一种提升，也让我们懂了更多做题的方法。
2、在这次实验中，存在着许许多多细节上的小问题，是因为编程基础不牢靠而产生的，通过这次实验又让我们懂了许多细节上的问题，以后就不会发生类似的问题了。
3、小组合作的形式能让我们更多的去沟通与思考，学会理解与合作。
附录：
程序源代码及注释
#include
#include
#include
#include
#include
#include
#include
#include
#include//包含多媒体函数库
#pragmacomment（lib,"winmm.lib"）//包含多媒体函数库对应的库文件
usingnamespacestd;
intstart[3][3]={2,8,3,1,6,4,7,0,5};
inttarget[3][3]={1,3,4,8,2,0,7,6,5};
//定义状态图中的结点数据结构
typedefstructNode
{
intdata[3][3];//结点所存储的状态
structNode*parent;//指向结点的父亲结点
structNode*child;//用于指向临时子节点，并且用于最后的最佳路径上结点的子结点
structNode*next;//指向open或者closed表中的后一个结点
intfvalue;//结点的总的路径
intgvalue;//结点的实际路径
inthvalue;//结点的到达目标的苦难程度
}NNode,*PNode;
/***定义两个全局链表***/
PNodeOPEN,CLOSE;
/*将光标移动到指定位置*/
voidgotoxy（HANDLEhout,constintX,constintY）
{
COORDcoord;
coord.X=X;
coord.Y=Y;
SetConsoleCursorPosition（hout,coord）;
}
voidsetcolor（HANDLEhout,constintbg_color,constintfg_color）
{
SetConsoleTextAttribute（hout,bg_color*16+fg_color）;
}
HANDLEhout=GetStdHandle（STD_OUTPUT_HANDLE）;//取标准输出设备对应的句柄
voidoutput（intx,inty,intarr[3][3]）
{
inti,j,k;
for（j=0;j<3;++j）{
for（i=0;i<5;++i）{
gotoxy（hout,x,y+5*j+i）;
for（k=0;k<3;++k）{
setcolor（hout,arr[j][k],arr[j][k]）;
cout<<"";
}
}
}
setcolor（hout,0,15）;
cout<}
//初始化一个空链表OK
voidinitLink（PNode&Head）
{
Head=（PNode）malloc（sizeof（NNode））;
Head->next=NULL;
}
//判断链表是否为空OK
boolisEmpty（PNodeHead）
{
if（Head->next==NULL）
returntrue;
else
returnfalse;
}
//求a和b相减的绝对值
intsubAbs（inta,intb）
{
return（a>b）?
（a-b）:
（b-a）;
}
/***计算结点的h值（到达目标结点的苦难程度）***/
intcomputeHValue（PNodetheNode）
{
intvalue=0,singlevalue;
inti,j,k,m;
inttemp;
for（i=0;i<3;++i）{
for（j=0;j<3;++j）{
temp=theNode->data[i][j];
if（temp）{//只有不是0的数字的才计入苦难值
for（k=0;k<3;++k）{
for（m=0;m<3;++m）{
if（target[k][m]==temp）{
singlevalue=subAbs（i,k）+subAbs（j,m）;
value+=singlevalue;
k=3;
break;
}
}
}
}
}
}
returnvalue;
}
//计算结点的f，g，h值
voidcomputeAllValue（PNode&theNode,PNodeparentNode）
{
if（parentNode==NULL）
theNode->gvalue=0;
else
theNode->gvalue=parentNode->gvalue+1;
theNode->hvalue=computeHValue（theNode）;
theNode->fvalue=theNode->gvalue+theNode->hvalue;
}
/***取得方格中空的格子的位置***/
voidgetPosition（PNodetheNode,int&row,int&col）
{
for（inti=0;i<3;i++）
for（intj=0;j<3;j++）
if（theNode->data[i][j]==0）{
row=i;
col=j;
return;
}
}
/***将theNode所指结点作为第一个结点加入LIST表中***/
voidaddNode（PNode&LIST,PNodetheNode）
{
theNode->next=LIST->next;
LIST->next=theNode;
}
//两个结点是否有相同的状态
boolhasSameStatus（PNodeANode,PNodeBNode）
{
inti,j;
for（i=0;i<3;i++）
for（j=0;j<3;j++）
if（ANode->data[i][j]!
=BNode->data[i][j]）
returnfalse;
returntrue;
}
/***检测theNode是否在LIST表中,若在则sameNode指向与theNode有相同状态的结点***/
boolinLink（PNodetheNode,PNode&LIST,PNode&sameNode）
{
sameNode=NULL;
PNodetemp=LIST->next;
while（temp!
=NULL）{
if（hasSameStatus（theNode,temp）==true）{
sameNode=temp;
returntrue;
}
temp=temp->next;
}
returnfalse;
}
//将B节点的状态赋值给A结点
voidstatusBToA（PNode&ANode,PNodeBNode）
{
for（inti=0;i<3;i++）
for（intj=0;j<3;j++）
ANode->data[i][j]=BNode->data[i][j];
}
//交换两个数字的值
voidchangeAB（int&A,int&B）
{
intC;
C=B;
B=A;
A=C;
}
/***初始化OPEN表和CLOSE表，并将开始状态加入OPEN表中***/
voidinitial（PNode&Start）
{
initLink（OPEN）;
initLink（CLOSE）;
//初始化起始结点，令初始结点的父节点为空结点
PNodeNULLNode=NULL;
Start=（PNode）malloc（sizeof（NNode））;
for（inti=0;i<3;i++）
for（intj=0;j<3;j++）
Start->data[i][j]=start[i][j];
Start->parent=NULL;
Start->child=NULL;
Start->next=NULL;
computeAllValue（Start,NULLNode）;
//起始结点进入open表
addNode（OPEN,Start）;
}
/***从OPEN表（非空）中找到f值最小的结点***/
voidfindfValueMinNode（PNode&theMinNode,PNode&preNode）
{
PNodep=OPEN,q=OPEN->next;
theMinNode=q;preNode=OPEN;
while（q->next）{
p=q;
q=q->next;
if（q->fvaluefvalue）{
theMinNode=q;
preNode=p;
}
}
}
/***生成theNode结点的子节点的同时进行对子节点的处理***/
voidgenDealSubNode（PNodetheNode）
{
introw;
intcol;
PNodesameNode=NULL;
getPosition（theNode,row,col）;
if（col!
=2）{//空的格子右边的格子向左移动
PNoderlNewNode=（PNode）malloc（sizeof（NNode））;
statusBToA（rlNewNode,theNode）;
changeAB（rlNewNode->data[row][col],rlNewNode->data[row][col+1]）;
if（inLink（rlNewNode,CLOSE,sameNode）==false）{//已经在CLOSE表中，则忽略
if（inLink（rlNewNode,OPEN,sameNode））{//不在CLOSE表中，但是在OPEN表中
if（sameNode->gvalue>theNode->gvalue+1）{//把这一格的父节点改成当前格,并且重新计算这一格的GF值
sameNode->parent=theNode;
computeAllValue（sameNode,theNode）;
}
}
else{//不在CLOSE表中，也不在OPEN表中,则将其加入OPEN表中
addNode（OPEN,rlNewNode）;
rlNewNode->parent=theNode;
computeAllValue（rlNewNode,theNode）;
}
}
}
if（col!
=0）{//空的格子左边的格子向右移动
PNodelrNewNode=（PNode）malloc（sizeof（NNode））;
statusBToA（lrNewNode,theNode）;
changeAB（lrNewNode->data[row][col],lrNewNode->data[row][col-1]）;
if（inLink（lrNewNode,CLOSE,sameNode）==false）{//已经在CLOSE表中，则忽略
if（inLink（lrNewNode,OPEN,sameNode））{//不在CLOSE表中，但是在OPEN表中
if（sameNode->gvalue>theNode->gvalue+1）{//把这一格的父节点改成当前格,并且重新计算这一格的GF值
sameNode->parent=theNode;
computeAllValue（sameNode,theNode）;
}
}
else{//不在CLOSE表中，也不在OPEN表中,则将其加入OPEN表中
addNode（OPEN,lrNewNode）;
lrNewNode->parent=theNode;
computeAllValue（lrNewNode,theNode）;
}
}
}
if（row!
=2）{//空的格子下边的格子向上移动
PNodeduNewNode=（PNode）malloc（sizeof（NNode））;
statusBToA（duNewNode,theNode）;
changeAB（duNewNode->data[row+1][col],duNewNode->data[row][col]）;
if（inLink（duNewNode,CLOSE,sameNode）==false）{//已经在CLOSE表中，则忽略
if（inLink（duNewNode,OPEN,sameNode））{//不在CLOSE表中，但是在OPEN表中
if（sameNode->gvalue>theNode->gvalue+1）{//把这一格的父节点改成当前格,并且重新计算这一格的GF值
sameNode->parent=theNode;
computeAllValue（sameNode,theNode）;
}
}
else{//不在CLOSE表中，也不在OPEN表中,则将其加入OPEN表中
addNode（OPEN,duNewNode）;
duNewNode->parent=theNode;
computeAllValue（duNewNode,theNode）;
}
}
}
if（row!
=0）{//空的格子上边的格子向下移动
PNodeudNewNode=（PNode）malloc（sizeof（NNode））;
statusBToA（udNewNode,theNode）;
changeAB（udNewNode->data[row-1][col],udNewNode->data[row][col]）;
if（inLink（udNewNode,CLOSE,sameNode）==false）{//已经在CLOSE表中，则忽略
if（inLink（udNewNode,OPEN,sameNode））{//不在CLOSE表中，但是在OPEN表中
if（sameNode->gvalue>theNode->gvalue+1）{//把这一格的父节点改成当前格,并且重新计算这一格的GF值
sameNode->parent=theNode;
computeAllValue（sameNode,theNode）;
}
}
else{//不在CLOSE表中，也不在OPEN表中,则将其加入OPEN表中
addNode（OPEN,udNewNode）;
udNewNode->parent=theNode;
computeAllValue（udNewNode,theNode）;
}
}
}
}
/***通过调用前面写的函数实现总的函数***/
boolA
升级会员 