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

1、-作者xxxx-日期xxxx采用A星算法实现八数码问题【精品文档】 人工智能实验一报告 题目：采用A*算法解决八数码问题成 员： 李文、郭弯弯 学 号： 1452288、1452264专 业： 计算机科学与技术完成日期： 2016/04/09【精品文档】1、 实验要求、目的及分工 使用A*算法实现八数码问题，并用图形界面展示。a. 熟悉人工智能系统中的问题求解过程；b. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；c. 熟悉对八数码问题的建模、求解及编程语言的应用。我们小组共两个人，共同查找背景资料，李文同学主要负责源代码，郭弯弯同学主要负责实验报告以及演示文稿的完成。2、 实验问题所谓八数

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

3、态(TRAGET)，所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态： （START>STATE1>STATE2>.>TARGET）这个状态是否存在就是我们要解决的第一个问题；第二个问题是我们要求出走的路径是什么。八数码问题形式化描述初始状态： 初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把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

4、,8>路径耗散函数：规定每次移动代价为1，即每执行一条规则后总代价加1。该问题是一个搜索问题。它是一种状态到另一种状态的变换。要解决这个问题，必须先把问题转化为数字描述。由于八数码是一个3*3的矩阵，但在算法中不是用矩阵，而是将这个矩阵转化为一个二维数组，使用这个二维数组来表示八数码，但是移动时要遵守相关规则。按规则，每一次可以将一个与空格相邻的棋子移动到空格中，实际上也可以看做空格的相反方向移动。空格的移动方向可以是上下左右，当然不能出边界。棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化。经分析，问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个

5、寻找的过程就是状态空间搜索。常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提高了效率。所以，本实验采用启发式A*搜索算法来实现。3、 A*算法A*算法是一种常用的启发式搜索算法。在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n) 这

6、里，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'

7、;(n)（大多数情况下都是满足的，可以不用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。首先定义两个表，open表用于存放已经生成，且已用启发式函数进行过估计或评价，但尚未产生它们的后继节点的那些结点，这些结点也称未考察结点；closed表用于存放已经生成，且已考察过的结点。把起始格添加到 "开启列表" do 寻找开启列表中F值最低的格子, 我们称它为当前格 把它切换到关闭列表 对当前格相邻的8格中的每一个 if (它不可通过 |

8、 已经在 "关闭列表" 中) 什么也不做 if (它不在开启列表中) 把它添加进 "开启列表"，把当前格作为这一格的父节点, 计算这一格的 FGH if (它已经在开启列表中) if (用G值为参考检查新的路径是否更好，更低的G值意味着更好的路径) 把这一格的父节点改成当前格，并且重新计算这一格的 GF 值 while( 目标格已经在 "开启列表"， 这时候路径被找到) 如果开启列表已经空了，说明路径不存在最后从目标格开始，沿着每一格的父节点移动直到回到起始格，这就是路径。四、算法实现 实验环境(1)实验环境：Windows 7(2)

9、IDE：codeblocks（图形界面的实现调用codeblocks里windows一系列函数）本实验主要使用链表：/定义状态图中的结点数据结构typedef struct Node int data33;/结点所存储的状态 struct Node *parent;/指向结点的父亲结点 struct Node *child; /用于指向临时子节点，并且用于最后的最佳路径上结点的子结点 struct Node *next;/指向open或者closed表中的后一个结点 int fvalue;/结点的总的路径 int gvalue;/结点的实际路径 int hvalue;/结点的到达目标的苦难程度

10、NNode , *PNode;/* 定义两个全局链表 */PNode OPEN,CLOSE;资料来源百度搜索，博客查找链接：5、 实验心得1、 学习了新的算法A*算法，结合了伪代码和网上的一些教程，实现了八数码问题的求解，这是对我们编程能力的一种提升，也让我们懂了更多做题的方法。  2、在这次实验中，存在着许许多多细节上的小问题，是因为编程基础不牢靠而产生的，通过这次实验又让我们懂了许多细节上的问题，以后就不会发生类似的问题了。 3、小组合作的形式能让我们更多的去沟通与思考，学会理解与合作。附录：程序源代码及注释#include <stdlib.h>#include &l

11、t;iostream>#include<conio.h>#include <iomanip>#include <ctime>#include <cmath>#include <cstdio>#include <windows.h>#include <mmsystem.h>/包含多媒体函数库#pragma comment(lib,"winmm.lib")/包含多媒体函数库对应的库文件using namespace std;int start 33 = 2,8,3,1,6,4,7,0,5;

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

13、表 */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 = GetStdHa

14、ndle(STD_OUTPUT_HANDLE); /取标准输出设备对应的句柄void output(int x,int y,int arr33) int i,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,arrjk,arrjk); cout<< " " setcolor(hout,0,15); cout << endl;/初始化一个空链表OKvoid initLink(PNode &am

15、p;Head) Head = (PNode)malloc(sizeof(NNode); Head->next = NULL;/判断链表是否为空OKbool isEmpty(PNode Head) if(Head->next = NULL) return true; else return false;/求a和b相减的绝对值int subAbs(int a,int b) return (a>b)?(a-b):(b-a);/* 计算结点的h值(到达目标结点的苦难程度) */int computeHValue(PNode theNode) int value = 0,singlev

16、alue; int i,j,k,m; int temp; for(i=0; i<3; +i) for(j=0; j<3; +j) temp = theNode->dataij; if( temp ) /只有不是0的数字的才计入苦难值 for(k=0; k<3; +k) for(m=0; m<3; +m) if( targetkm=temp ) singlevalue = subAbs(i,k) + subAbs(j,m); value += singlevalue; k = 3; break; return value;/计算结点的f，g，h值void compu

17、teAllValue(PNode &theNode , PNode parentNode) if(parentNode = NULL) theNode->gvalue = 0; else theNode->gvalue = parentNode->gvalue + 1; theNode->hvalue = computeHValue(theNode); theNode->fvalue = theNode->gvalue + theNode->hvalue;/* 取得方格中空的格子的位置 */void getPosition(PNode theN

18、ode , int &row , int &col) for(int i = 0 ; i < 3 ; i+) for(int j = 0 ; j < 3 ; j+) if(theNode->dataij = 0) row = i; col = j; return; /* 将theNode所指结点作为第一个结点加入LIST表中 */void addNode(PNode &LIST,PNode theNode) theNode->next = LIST->next; LIST->next = theNode;/两个结点是否有相同的状态bo

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

20、e = 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 < 3 ; j+) ANode->dataij

21、 = 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 <

22、 3 ; i+) for(int j = 0 ; j < 3 ; j+) Start->dataij = 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)

23、 PNode p = OPEN,q = OPEN->next; theMinNode = q; preNode = OPEN; while(q->next) p = q; q = q->next; if(q->fvalue < theMinNode->fvalue) theMinNode = q; preNode = p; /* 生成theNode结点的子节点的同时进行对子节点的处理 */void genDealSubNode(PNode theNode) int row; int col; PNode sameNode = NULL; getPositio

24、n(theNode , row , col); if(col!=2)/空的格子右边的格子向左移动 PNode rlNewNode = (PNode)malloc(sizeof(NNode); statusBToA(rlNewNode , theNode); changeAB(rlNewNode->datarowcol , rlNewNode->datarowcol + 1); if( inLink(rlNewNode, CLOSE, sameNode)=false )/已经在CLOSE表中，则忽略 if( inLink(rlNewNode, OPEN, sameNode) )/不在

25、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);

26、if(col!=0)/空的格子左边的格子向右移动 PNode lrNewNode = (PNode)malloc(sizeof(NNode); statusBToA(lrNewNode , theNode); changeAB(lrNewNode->datarowcol , lrNewNode->datarowcol - 1); if( inLink(lrNewNode, CLOSE, sameNode)=false )/已经在CLOSE表中，则忽略 if( inLink(lrNewNode, OPEN, sameNode) )/不在CLOSE表中，但是在OPEN表中 if( sa

27、meNode->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)/空的格子下边的格子向上移动

28、 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, OPEN, sameNode) )/不在CLOSE表中，但是在OPEN表中 if( sameNode->gvalue > the

29、Node->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)/空的格子上边的格子向下移动 PNode udNewNode = (PNode)

30、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->gvalue + 1)/把这一格的

31、父节点改成当前格, 并且重新计算这一格的 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)=false) findfValueMinNode(theMinNode, preNode); if(theMinNode->hvalue = 0) break; /将结点从OPEN表中删除并加到CLOSE表中 preNode->next = theMin