采用A星算法实现八数码问题

1、人工智能实验一报告题目：采用A* 算法解决八数码问题成员：李文、郭弯弯学号：、专业：计算机科学与技术完成日期：2016/04/09一、实验要求、目的及分工1.1 实验要求使用 A* 算法实现八数码问题，并用图形界面展示。1.2 实验目的熟悉人工智能系统中的问题求解过程；熟悉状态空间的盲目搜索和启发式搜索算法的应用；熟悉对八数码问题的建模、求解及编程语言的应用。1.3 实验分工我们小组共两个人， 共同查找背景资料， 李文同学主要负责源代码， 郭弯弯同学主要负责实验报告以及演示文稿的完成。二、实验问题2.1问题描述所谓八数码问题是指这样一种游戏：将分别标有数字 1， 2， 3， ， 8 的八块正方

2、形数码牌任意地放在一块 33 的数码盘上。放牌时要求不能重叠。于是，在 3 3 的数码盘上出现了一个空格。 现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换， 直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4个方向可移动，在四个角落上有 2个方向可移动，在其他位置上有 3个方向可移动，问题描述如下图所示：150832478451326670(a)初始状态(b)目标状态图 1 八数码问题示意图2.2 问题解释首先，八数码问题包括一个初始状态 (START) 和目标状态 (TRAGET) ，所谓解决八数码问题就是在两个状态间寻找一

3、系列可过渡状态：STARTSTATE1STATE2.TARGET）这个状态是否存在就是我们要解决的第一个问题；第二个问题是我们要求出走的路径是什么。2.3 八数码问题形式化描述初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把33 的棋盘写成一个二维向量。我们可以设定初始状态：后继函数：按照某种规则移动数字得到的新向量。例如：路径耗散函数：规定每次移动代价为1，即每执行一条规则后总代价加1。2.4 解决方案选择该问题是一个搜索问题。它是一种状态到另一种状态的变换。要解决这个问题，必须先把问题转化为数字描述。由于八数码是一个3*3 的矩阵，但在算法中不是用矩阵，而是将这个矩阵

4、转化为一个二维数组，使用这个二维数组来表示八数码，但是移动时要遵守相关规则。按规则，每一次可以将一个与空格相邻的棋子移动到空格中， 实际上也可以看做空格的相反方向移动。 空格的移动方向可以是上下左右， 当然不能出边界。 棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化。经分析，问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。 这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。 广度优先是从初始状态一层一层向下找， 直到找到目标为止。 深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。启发式搜索就是在状态空间

5、中的搜索对每一个搜索的位置进行评估， 得到最好的位置，再从这个位置进行搜索直到目标。 这样可以省略大量无畏的搜索路径， 提高了效率。所以，本实验采用启发式 A* 搜索算法来实现。三、 A* 算法3.1 算法介绍A*算法是一种常用的启发式搜索算法。在 A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为：f(n) = g(n) + h(n)这里， f(n) 是估价函数， g(n) 是起点到终点的最短路径值（也称为最小耗费或最小代价）， h(n) 是 n 到目标的最短路经的启发值。由于这个 f(n) 其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n) =

6、 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 算法伪代码首先

7、定义两个表， open 表用于存放已经生成，且已用启发式函数进行过估计或评价，但尚未产生它们的后继节点的那些结点，这些结点也称未考察结点；closed 表用于存放已经生成，且已考察过的结点。把起始格添加到 开启列表 do寻找开启列表中F 值最低的格子 , 我们称它为当前格把它切换到关闭列表对当前格相邻的8 格中的每一个if ( 它不可通过| 已经在 关闭列表 中 )什么也不做if ( 它不在开启列表中 )把它添加进 开启列表 ，把当前格作为这一格的父节点, 计算这一格的 FGHif ( 它已经在开启列表中 )if ( 用 G 值为参考检查新的路径是否更好，更低的G 值意味着更好的路径 )把这一

8、格的父节点改成当前格， 并且重新计算这一格的GF值 while( 目标格已经在 开启列表 ， 这时候路径被找到 )如果开启列表已经空了，说明路径不存在最后从目标格开始，沿着每一格的父节点移动直到回到起始格，这就是路径。四、算法实现4.1 实验环境(1)实验环境： Windows 7(2)IDE ：codeblocks（图形界面的实现调用codeblocks里 windows 一系列函数）4.2 数据结构本实验主要使用链表：/定义状态图中的结点数据结构typedef struct Nodeint data33;/ 结点所存储的状态struct Node *parent;/指向结点的父亲结点str

9、uct Node *child; / 用于指向临时子节点，并且用于最后的最佳路径上结点的子结点struct Node *next;/指向 open 或者 closed 表中的后一个结点int fvalue;/ 结点的总的路径int gvalue;/结点的实际路径int hvalue;/结点的到达目标的苦难程度NNode , *PNode;/*定义两个全局链表*/PNode OPEN,CLOSE;4.3 实验结果截屏4.4 参考资料资料来源百度搜索，博客查找链接：五、实验心得1、学习了新的算法 A*算法，结合了伪代码和网上的一些教程，实现了八数码问题的求解，这是对我们编程能力的一种提升，也让我们

10、懂了更多做题的方法。2、在这次实验中，存在着许许多多细节上的小问题，是因为编程基础不牢靠而产生的，通过这次实验又让我们懂了许多细节上的问题，以后就不会发生类似的问题了。、小组合作的形式能让我们更多的去沟通与思考，学会理解与合作。附录：程序源代码及注释#include #include #include#include #include #include #include #include #include / 包含多媒体函数库#pragma comment(lib,winmm.lib)/using namespace std;int start 33 = 2,8,3,1,6,4,7,0,5;i

11、nt target33 = 1,3,4,8,2,0,7,6,5;包含多媒体函数库对应的库文件/ 定义状态图中的结点数据结构typedef struct Nodeint data33;/结点所存储的状态struct Node *parent;/指向结点的父亲结点structNode *child;/ 用于指向临时子节点，并且用于最后的最佳路径上结点的子结点struct Node *next;/指向open 或者closed表中的后一个结点int fvalue;/结点的总的路径int gvalue;/结点的实际路径int hvalue;/NNode , *PNode;结点的到达目标的苦难程度/*定

12、义两个全局链表*/PNode OPEN,CLOSE;/*将光标移动到指定位置*/void gotoxy(HANDLE hout, const int X, const int Y)COORD coord;coord.X = X;coord.Y = Y;SetConsoleCursorPosition(hout,coord);void setcolor(HANDLE hout, const int bg_color, const int fg_color)SetConsoleTextAttribute(hout, bg_color*16+fg_color);HANDLE hout = GetSt

13、dHandle(STD_OUTPUT_HANDLE); /取标准输出设备对应的句柄void output(int x,int y,int arr33)int i,j,k;for(j=0; j3; +j)for(i=0; i5; +i)gotoxy(hout,x,y+5*j+i);for(k=0; k3; +k)setcolor(hout,arrjk,arrjk);cout ;setcolor(hout,0,15);cout next = NULL;判断链表是否为空 OKbool isEmpty(PNode Head)if(Head-next = NULL)return true;elseret

14、urn false;求 a 和 b 相减的绝对值int subAbs(int a,int b)return (ab)?(a-b):(b-a);/*计算结点的 h 值 ( 到达目标结点的苦难程度) */int computeHValue(PNode theNode)int value = 0,singlevalue;int i,j,k,m;int temp;for(i=0; i3; +i)for(j=0; jdataij;if( temp ) /只有不是 0 的数字的才计入苦难值for(k=0; k3; +k)for(m=0; mgvalue = 0;elsetheNode-gvalue = p

15、arentNode-gvalue + 1;theNode-hvalue = computeHValue(theNode); theNode-fvalue = theNode-gvalue + theNode-hvalue;/*取得方格中空的格子的位置*/void getPosition(PNode theNode , int &row , int &col)for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j dataij = 0)row = i;col = j;return;/*将 theNode 所指结点作为第一个结点加入LIST 表中*/void addN

16、ode(PNode &LIST,PNode theNode)theNode-next = LIST-next;LIST-next = theNode;/ 两个结点是否有相同的状态bool hasSameStatus(PNode ANode , PNode BNode)int i,j;for(i = 0 ; i 3 ; i+)for(j = 0 ; j dataij != BNode-dataij)return false;return true;/* 检测 theNode 是否在 LIST 表中 , 若在则 sameNode指向与 theNode 有相同状态的结点 */bool inLink(

17、PNode theNode, PNode &LIST, PNode &sameNode)sameNode = NULL;PNode temp = LIST-next;while(temp!=NULL)if(hasSameStatus(theNode,temp) = true)sameNode = temp;return true;temp = temp-next;return false;将 B 节点的状态赋值给 A 结点void statusBToA(PNode &ANode , PNode BNode)for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j d

18、ataij = BNode-dataij;交换两个数字的值void changeAB(int &A , int &B)int C;C=B;B=A;A=C;/*初始化 OPEN表和 CLOSE表，并将开始状态加入OPEN表中 */void initial(PNode &Start)initLink(OPEN);initLink(CLOSE);初始化起始结点，令初始结点的父节点为空结点PNode NULLNode = NULL;Start = (PNode)malloc(sizeof(NNode);for(int i = 0 ; i 3 ; i+)for(int j = 0 ; j dataij

19、= startij;Start-parent = NULL;Start-child = NULL;Start-next = NULL;computeAllValue(Start , NULLNode);起始结点进入 open 表addNode(OPEN , Start);/*从 OPEN表( 非空 ) 中找到 f 值最小的结点 */void findfValueMinNode(PNode &theMinNode,PNode &preNode)PNode p = OPEN,q = OPEN-next;theMinNode = q;preNode = OPEN;while(q-next)p = q

20、;q = q-next;if(q-fvalue fvalue)theMinNode = q;preNode= p;/*生成 theNode 结点的子节点的同时进行对子节点的处理*/void genDealSubNode(PNode theNode)int row;int col;PNode sameNode = NULL;getPosition(theNode , row , col);if(col!=2)/空的格子右边的格子向左移动PNode rlNewNode = (PNode)malloc(sizeof(NNode);statusBToA(rlNewNode , theNode);cha

21、ngeAB(rlNewNode-datarowcol,rlNewNode-datarowcol+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);

22、else/不在 CLOSE表中，也不在OPEN表中 , 则将其加入 OPEN表中addNode(OPEN,rlNewNode);rlNewNode-parent = theNode;computeAllValue(rlNewNode, theNode);if(col!=0)/空的格子左边的格子向右移动PNode lrNewNode = (PNode)malloc(sizeof(NNode);statusBToA(lrNewNode , theNode);changeAB(lrNewNode-datarowcol,lrNewNode-datarowcol-1);if( inLink(lrNewN

23、ode, 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);lrNew

24、Node-parent = theNode;computeAllValue(lrNewNode, theNode);if(row!=2)/空的格子下边的格子向上移动PNode duNewNode = (PNode)malloc(sizeof(NNode);statusBToA(duNewNode , theNode);changeAB(duNewNode-datarow+1col, duNewNode-datarowcol);if( inLink(duNewNode, CLOSE, sameNode)=false )/已经在CLOSE表中，则忽略if( inLink(duNewNode, OP

25、EN, 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)

26、/空的格子上边的格子向下移动PNode udNewNode = (PNode)malloc(sizeof(NNode);statusBToA(udNewNode , theNode);changeAB(udNewNode-datarow-1col, udNewNode-datarowcol);if( inLink(udNewNode, CLOSE, sameNode)=false )/已经在CLOSE表中，则忽略if( inLink(udNewNode, OPEN, sameNode) )/不在CLOSE表中，但是在OPEN表中if( sameNode-gvalue theNode-gvalu

27、e + 1)/把这一格的父节点改成当前格,并且重新计算这一格的GF值sameNode-parent = theNode;computeAllValue(sameNode, theNode);else/不在 CLOSE表中，也不在OPEN表中 , 则将其加入 OPEN表中addNode(OPEN,udNewNode);udNewNode-parent = theNode;computeAllValue(udNewNode, theNode);/*通过调用前面写的函数实现总的函数*/bool AStar(PNode &theMinNode)PNode Start;initial(Start);theMinNode = NULL;PNode preNode = NULL;while(isEmpty(OPEN)=fa