采用A星算法实现八数码问题Word文档下载推荐.docx
《采用A星算法实现八数码问题Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《采用A星算法实现八数码问题Word文档下载推荐.docx(17页珍藏版)》请在冰点文库上搜索。
首先,八数码问题包括一个初始状态(START)和目标状态(TRAGET),所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态:
(START>
STATE1>
STATE2>
...>
TARGET)
这个状态是否存在就是我们要解决的第一个问题;
第二个问题是我们要求出走的路径是什么。
2.3八数码问题形式化描述
初始状态:
初始状态向量:
规定向量中各分量对应的位置,各位置上的数字。
把3×
3的棋盘写成一个二维向量。
我们可以设定初始状态:
<
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'
第二点特别的重要。
可以证明应用这样的估价函数是可以找到最短路径的。
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<
stdlib.h>
iostream>
#include<
conio.h>
iomanip>
ctime>
cmath>
cstdio>
windows.h>
mmsystem.h>
//包含多媒体函数库
#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};
/*将光标移动到指定位置*/
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<
++k){
setcolor(hout,arr[j][k],arr[j][k]);
cout<
"
;
}
setcolor(hout,0,15);
cout<
endl;
//初始化一个空链表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;
temp=theNode->
data[i][j];
if(temp){//只有不是0的数字的才计入苦难值
for(m=0;
m<
++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;
gvalue=parentNode->
gvalue+1;
hvalue=computeHValue(theNode);
fvalue=theNode->
gvalue+theNode->
hvalue;
/***取得方格中空的格子的位置***/
voidgetPosition(PNodetheNode,int&
row,int&
col)
for(inti=0;
i<
3;
i++)
for(intj=0;
j<
j++)
if(theNode->
data[i][j]==0){
row=i;
col=j;
return;
/***将theNode所指结点作为第一个结点加入LIST表中***/
voidaddNode(PNode&
LIST,PNodetheNode)
next=LIST->
next;
LIST->
next=theNode;
//两个结点是否有相同的状态
boolhasSameStatus(PNodeANode,PNodeBNode)
inti,j;
for(i=0;
for(j=0;
if(ANode->
data[i][j]!
=BNode->
data[i][j])
/***检测theNode是否在LIST表中,若在则sameNode指向与theNode有相同状态的结点***/
boolinLink(PNodetheNode,PNode&
LIST,PNode&
sameNode)
sameNode=NULL;
PNodetemp=LIST->
while(temp!
=NULL){
if(hasSameStatus(theNode,temp)==true){
sameNode=temp;
temp=temp->
//将B节点的状态赋值给A结点
voidstatusBToA(PNode&
ANode,PNodeBNode)
ANode->
data[i][j]=BNode->
//交换两个数字的值
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));
Start->
data[i][j]=start[i][j];
parent=NULL;
child=NULL;
computeAllValue(Start,NULLNode);
//起始结点进入open表
addNode(OPEN,Start);
/***从OPEN表(非空)中找到f值最小的结点***/
voidfindfValueMinNode(PNode&
theMinNode,PNode&
preNode)
PNodep=OPEN,q=OPEN->
theMinNode=q;
preNode=OPEN;
while(q->
next){
p=q;
q=q->
if(q->
fvalue<
theMinNode->
fvalue){
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>
gvalue+1){//把这一格的父节点改成当前格,并且重新计算这一格的GF值
sameNode->
parent=theNode;
computeAllValue(sameNode,theNode);
else{//不在CLOSE表中,也不在OPEN表中,则将其加入OPEN表中
addNode(OPEN,rlNewNode);
rlNewNode->
computeAllValue(rlNewNode,theNode);
=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表中
addNode(OPEN,lrNewNode);
lrNewNode->
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表中
addNode(OPEN,duNewNode);
duNewNode->
computeAllValue(duNewNode,theNode);
=0){//空的格子上边的格子向下移动
PNodeudNewNode=(PNode)malloc(sizeof(NNode));
statusBToA(udNewNode,theNode);
changeAB(udNewNode->
data[row-1][col],udNewNode->
if(inLink(udNewNode,CLOSE,sameNode)==false){//已经在CLOSE表中,则忽略
if(inLink(udNewNode,OPEN,sameNode)){//不在CLOSE表中,但是在OPEN表中
addNode(OPEN,udNewNode);
udNewNode->
computeAllValue(udNewNode,theNode);
/***通过调用前面写的函数实现总的函数***/
boolA