【人工智能实验】A*算法求解8数码问题
目录实验一A*算法求解8数码问题一、实验目的二、实验原理三、实验结果四、实验总结附录代码推荐文章实验一A*算法求解8数码问题一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。
二、实验原理A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n),且hn≤h*n,h*n为n节点到目的结点的最优路径的代价。
图2.1 八数码问题的求解八数码问题是在3×3的九宫格棋盘上，摆有8个刻有1～8数码的将牌。棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。如下图2.1表示了一个具体的八数码问题求解。
三、实验结果表3.1不同启发函数h(n)求解8数码问题的结果比较
启发函数h(n)
不在位数
将牌“不在位”的距离和
0
初始状态
283604175
283604175
283604175
目标状态
123804765
123804765
123804765
最优解
最佳路径长度
为：8
最佳路径为：
第1层的状态：
283
064
175
第2层的状态：
283
164
075
第3层的状态：
283
164
705
第4层的状态：
283
104
765
第5层的状态：
203
184
765
第6层的状态：
023
184
765
第7层的状态：
123
084
765
第8层的状态：
123
804
765
最佳路径长度
为：8
最佳路径为：
第1层的状态：
283
064
175
第2层的状态：
283
164
075
第3层的状态：
283
164
705
第4层的状态：
283
104
765
第5层的状态：
203
184
765
第6层的状态：
023
184
765
第7层的状态：
123
084
765
第8层的状态：
123
804
765
最佳路径长度为：8
最佳路径为：
第1层的状态：
283
064
175
第2层的状态：
283
164
075
第3层的状态：
283
164
705
第4层的状态：
283
104
765
第5层的状态：
203
184
765
第6层的状态：
023
184
765
第7层的状态：
123
084
765
第8层的状态：
123
804
765
扩展节点数
（不包括叶子节点）
17
8
294
生成节点数
（包含叶子节点）
33
17
470
运行时间
（迭代次数）
220.00ms
120.00ms
1469.00ms
四、实验总结1、画出A*算法求解N数码问题的流程图。
根据A*算法的实验原理，f=g(n)+h(n)；这样估价函数f(n)在g(n)一定的情况下，会或多或少的受距离估计值h(n)的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行,因此f是根据需要找到一条最小代价路径的观点来估算节点的。设计A*算法的流程图如图4.1.1所示，按照流程图编写伪代码，进而编写完整的程序。其中OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。在扩展结点时，还需要考虑两个表即OPEN表和CLOSED表中是否存在了该节点的后继节点。具体编程思路参照算法4.1。
图4.1.1A*算法求解八数码问题的流程图
算法4.1
将起始点加入open表
当open表不为空时：
寻找open表中f值最小的点current
它是终止点，则找到结果，程序结束。
否则，Open表移出current，对current表中的每一个临近点
若它不可走或在close表中，略过
若它不在open表中，加入。
若它在open表中，计算g值，若g值更小，替换其父节点为current，更新
它的g值。
若open表为空，则路径不存在。
2、分析不同的估价函数对A*算法性能的影响。
对于同一问题启发函数h(n)可以有多种设计方法。在本次时实验中，通过选用“将牌不在位数”和“将牌‘不在位’的距离和”两种不同的启发函数，同时还编写了不考虑h值进行搜索，即不采用启发性搜索的算法（按照广度优先搜索的策略）。正如表3.1所示，我们通过将第一种和第二种启发函数对比，发现第二种启发函数优于第一种启发函数，将采用启发函数与不采用启发性函数对比发现，采用启发性函数远远优于不采用启发性函数。
下面，以图4.2.2为例，分析第二种启发函数求解的过程。第二种启发函数为h(n)=将牌‘不在位’的距离和，初始时的值为6,将牌1：2，将牌2：1，将牌6：2，将牌7：1，将牌8:2。在实验结果演示（表3.1）时，并没有选取图4.3初始状态来比较不同启发函数以及不采用启发函数对求解效率的影响，而是选取了图4.2.1初始状态进行演示，因为图4.2.2的步骤较为复杂，对于不同启发函数对于实验结果和实验效率的影响较为明显。第三种启发函数是按照广度优先搜索的策略。
图4.2.1初始状态 图4.2.2A*算法求解八数码示意图
3、根据宽度优先搜索算法和A*算法求解八数码问题的结果，分析启发式搜索的特点。
根据表3-1的结果，我们可以发现采用A*算法求解八数码问题时间以及搜索的节点数目远远小于采用宽度优先搜索算法，这说明对于八数码问题，选用的启发性信息有利于搜索效率的提高。但是理论上来讲，如果选用的启发性信息过强，则可能找不到最优解。
4、实验心得体会
当时面对300行的代码时，不知从何处下手，通过查阅资料和请教老师，以及与同学深入探讨，仔细研究A*算法之后，才明白程序如何编写，各部分的函数如何构成。同时，通过本次实验，发现选用不同的启发函数，对于实验的结果有较大的影响。正如表3-1所示，选用第一或第二种（也就是采用A*算法）远远优于普通的广度优先搜索，同时，明显的感觉到第二种启发函数效率更高，更快的找到最优解。但是，在实验过程中，也遇到了一些问题，比如初始值的八数码初始值的选择对于实验结果的影响很大，在选取一些样例时，比如1,3,0,2,8,4,7,6,5，实验结果达到20000次依然没有停止，无法比较两种启发函数的优越性，鉴于时间原因，选取一些迭代次数较小就可以达到目标状态的样例进行验证，发现第二种结果优于第一种启发函数的结果。总的来说，实践出真知，只有把书上的理论知识运用到实践，才是真正地掌握。本次实验顺利完成，还是挺开心的。
附录代码#include"iostream"#include"stdlib.h"#include"conio.h"#include#include#definesize3usingnamespacestd;//定义二维数组来存储数据表示某一个特定状态typedefintstatus[size][size];structSpringLink;//定义状态图中的结点数据结构typedefstructNode{statusdata;//结点所存储的状态，一个3*3矩阵structNode*parent;//指向结点的父亲结点structSpringLink*child;//指向结点的后继结点structNode*next;//指向open或者closed表中的后一个结点intfvalue;//结点的总的路径intgvalue;//结点的实际路径inthvalue;//结点的到达目标的困难程度}NNode,*PNode;//定义存储指向结点后继结点的指针的地址typedefstructSpringLink{structNode*pointData;//指向结点的指针structSpringLink*next;//指向兄第结点}SPLink,*PSPLink;PNodeopen;PNodeclosed;//OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点//开始状态与目标状态/*statusstartt={1,3,0,8,2,4,7,6,5};最佳路径为2statusstartt={1,3,0,2,8,4,7,6,5};迭代超过20000次，手动停止statusstartt={2,8,3,1,6,4,7,0,5};statusstartt={2,8,3,6,0,4,1,7,5};//实验报告*/intt=0;//迭代次数,相当于运行时间intcount_extendnode=0;//扩展结点intcount_sumnode=0;//生成节点statusstartt={2,8,3,6,0,4,1,7,5};//实验报告statustarget={1,2,3,8,0,4,7,6,5};//初始化一个空链表voidinitLink(PNode&Head){Head=(PNode)malloc(sizeof(NNode));Head->next=NULL;}//判断链表是否为空boolisEmpty(PNodeHead){if(Head->next==NULL)returntrue;elsereturnfalse;}//从链表中拿出一个数据voidpopNode(PNode&Head,PNode&FNode){if(isEmpty(Head)){FNode=NULL;return;}FNode=Head->next;Head->next=Head->next->next;FNode->next=NULL;}//向结点的最终后继结点链表中添加新的子结点voidaddSpringNode(PNode&Head,PNodenewData){PSPLinknewNode=(PSPLink)malloc(sizeof(SPLink));newNode->pointData=newData;newNode->next=Head->child;Head->child=newNode;}//释放状态图中存放结点后继结点地址的空间voidfreeSpringLink(PSPLink&Head){PSPLinktmm;while(Head!=NULL){tmm=Head;Head=Head->next;free(tmm);}}//释放open表与closed表中的资源voidfreeLink(PNode&Head){PNodetmn;tmn=Head;Head=Head->next;free(tmn);while(Head!=NULL){//首先释放存放结点后继结点地址的空间freeSpringLink(Head->child);tmn=Head;Head=Head->next;free(tmn);}}//向普通链表中添加一个结点voidaddNode(PNode&Head,PNode&newNode){newNode->next=Head->next;Head->next=newNode;}//向非递减排列的链表中添加一个结点（已经按照权值进行排序）voidaddAscNode(PNode&Head,PNode&newNode){PNodeP;PNodeQ;P=Head->next;Q=Head;while(P!=NULL&&P->fvaluefvalue){Q=P;P=P->next;}//上面判断好位置之后，下面就是简单的插入了newNode->next=Q->next;Q->next=newNode;}/*//计算结点的h值f=g+h.按照不在位的个数进行计算intcomputeHValue(PNodetheNode){intnum=0;for(inti=0;igvalue=parentNode->gvalue+1;//theNode->hvalue=computeHValue(theNode);theNode->hvalue=0;theNode->fvalue=theNode->gvalue+theNode->hvalue;}//初始化函数，进行算法初始条件的设置voidinitial(){//初始化open以及closed表initLink(open);initLink(closed);//初始化起始结点，令初始结点的父节点为空结点PNodeNULLNode=NULL;PNodeStart=(PNode)malloc(sizeof(NNode));for(inti=0;iparent=NULL;Start->child=NULL;Start->next=NULL;computeAllValue(Start,NULLNode);//起始结点进入open表addAscNode(open,Start);}//将B节点的状态赋值给A结点voidstatusAEB(PNode&ANode,PNodeBNode){for(inti=0;idata[i][j];}}}//两个结点是否有相同的状态boolhasSameStatus(PNodeANode,PNodeBNode){for(inti=0;idata[i][j])returnfalse;}}returntrue;}//结点与其祖先结点是否有相同的状态boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode){while(AnceNode!=NULL){if(hasSameStatus(OrigiNode,AnceNode))returntrue;AnceNode=AnceNode->parent;}returnfalse;}//取得方格中空的格子的位置voidgetPosition(PNodetheNode,int&row,int&col){for(inti=0;inext;while(theLink!=NULL){if(hasSameStatus(spciNode,theLink)){theNodeLink=theLink;returntrue;}preNode=theLink;theLink=theLink->next;}returnfalse;}//产生结点的后继结点(与祖先状态不同)链表voidSpringLink(PNodetheNode,PNode&spring){introw;intcol;getPosition(theNode,row,col);//空的格子右边的格子向左移动if(col!=2){PNoderlNewNode=(PNode)malloc(sizeof(NNode));statusAEB(rlNewNode,theNode);changeAB(rlNewNode->data[row][col],rlNewNode->data[row][col+1]);if(hasAnceSameStatus(rlNewNode,theNode->parent)){free(rlNewNode);//与父辈相同，丢弃本结点}else{rlNewNode->parent=theNode;rlNewNode->child=NULL;rlNewNode->next=NULL;computeAllValue(rlNewNode,theNode);//将本结点加入后继结点链表addNode(spring,rlNewNode);}}//空的格子左边的格子向右移动if(col!=0){PNodelrNewNode=(PNode)malloc(sizeof(NNode));statusAEB(lrNewNode,theNode);changeAB(lrNewNode->data[row][col],lrNewNode->data[row][col-1]);if(hasAnceSameStatus(lrNewNode,theNode->parent)){free(lrNewNode);//与父辈相同，丢弃本结点}else{lrNewNode->parent=theNode;lrNewNode->child=NULL;lrNewNode->next=NULL;computeAllValue(lrNewNode,theNode);//将本结点加入后继结点链表addNode(spring,lrNewNode);}}//空的格子上边的格子向下移动if(row!=0){PNodeudNewNode=(PNode)malloc(sizeof(NNode));statusAEB(udNewNode,theNode);changeAB(udNewNode->data[row][col],udNewNode->data[row-1][col]);if(hasAnceSameStatus(udNewNode,theNode->parent)){free(udNewNode);//与父辈相同，丢弃本结点}else{udNewNode->parent=theNode;udNewNode->child=NULL;udNewNode->next=NULL;computeAllValue(udNewNode,theNode);//将本结点加入后继结点链表addNode(spring,udNewNode);}}//空的格子下边的格子向上移动if(row!=2){PNodeduNewNode=(PNode)malloc(sizeof(NNode));statusAEB(duNewNode,theNode);changeAB(duNewNode->data[row][col],duNewNode->data[row+1][col]);if(hasAnceSameStatus(duNewNode,theNode->parent)){free(duNewNode);//与父辈相同，丢弃本结点}else{duNewNode->parent=theNode;duNewNode->child=NULL;duNewNode->next=NULL;computeAllValue(duNewNode,theNode);//将本结点加入后继结点链表addNode(spring,duNewNode);}}}//输出给定结点的状态voidoutputStatus(PNodestat){for(inti=0;i