1、 首先,八数码问题包括一个初始状态(START) 和目标状态(TRAGET),所谓解决八数码问题就是在两个状态间寻找一系列可过渡状态: (STARTSTATE1STATE2.TARGET)这个状态是否存在就是我们要解决的第一个问题;第二个问题是我们要求出走的路径是什么。2.3八数码问题形式化描述初始状态: 初始状态向量:规定向量中各分量对应的位置,各位置上的数字。把33的棋盘写成一个二维向量。我们可以设定初始状态:后继函数:按照某种规则移动数字得到的新向量。例如: 路径耗散函数:规定每次移动代价为1,即每执行一条规则后总代价加1。2.4解决方案选择该问题是一个搜索问题。它是一种状态到另一种状态
2、的变换。要解决这个问题,必须先把问题转化为数字描述。由于八数码是一个3*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)其
4、实是无法预先知道的,所以实际上使用的是下面的估价函数: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算法伪代码首先定
5、义两个表,open表用于存放已经生成,且已用启发式函数进行过估计或评价,但尚未产生它们的后继节点的那些结点,这些结点也称未考察结点;closed表用于存放已经生成,且已考察过的结点。把起始格添加到 开启列表do 寻找开启列表中F值最低的格子, 我们称它为当前格 把它切换到关闭列表 对当前格相邻的8格中的每一个 if (它不可通过 | 已经在 关闭列表 中) 什么也不做 if (它不在开启列表中) 把它添加进 ,把当前格作为这一格的父节点, 计算这一格的 FGH if (它已经在开启列表中) if (用G值为参考检查新的路径是否更好,更低的G值意味着更好的路径) 把这一格的父节点改成当前格,并且
6、重新计算这一格的 GF 值 while( 目标格已经在 , 这时候路径被找到) 如果开启列表已经空了,说明路径不存在最后从目标格开始,沿着每一格的父节点移动直到回到起始格,这就是路径。四、算法实现4.1 实验环境(1)实验环境:Windows 7(2)IDE:codeblocks(图形界面的实现调用codeblocks里windows一系列函数)4.2数据结构本实验主要使用链表:/定义状态图中的结点数据结构typedef struct Node int data33;/结点所存储的状态 struct Node *parent;/指向结点的父亲结点 struct Node *child; /用于
7、指向临时子节点,并且用于最后的最佳路径上结点的子结点 struct Node *next;/指向open或者closed表中的后一个结点 int fvalue;/结点的总的路径 int gvalue;/结点的实际路径 int hvalue;/结点的到达目标的苦难程度NNode , *PNode;/* 定义两个全局链表 */PNode OPEN,CLOSE;4.3实验结果截屏4.4参考资料资料来源XX搜索,博客查找链接:5、实验心得1、学习了新的算法A*算法,结合了伪代码和网上的一些教程,实现了八数码问题的求解,这是对我们编程能力的一种提升,也让我们懂了更多做题的方法。 2、在这次实验中,存在着
8、许许多多细节上的小问题,是因为编程基础不牢靠而产生的,通过这次实验又让我们懂了许多细节上的问题,以后就不会发生类似的问题了。 3、小组合作的形式能让我们更多的去沟通与思考,学会理解与合作。附录:程序源代码及注释#include iostream#includeiomanipctimecmathcstdiowindows.hmmsystem.h /包含多媒体函数库#pragma comment(lib,winmm.lib)/包含多媒体函数库对应的库文件using namespace std;int start 33 = 2,8,3,1,6,4,7,0,5;int target33 = 1,3,4
9、,8,2,0,7,6,5;/* 将光标移动到指定位置 */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 = GetStdHandl
10、e(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; k +k) setcolor(hout,arrjk,arrjk); cout ; setcolor(hout,0,15); cout next = NULL;/判断链表是否为空OKbool isEmpty(PNode Head) if(Head-next = NULL) return true; els
11、e return 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; temp = theNode-dataij; if( temp ) /只有不是0的数字的才计入苦难值 for(m=0; mgvalue = 0;gvalue = parentNode-gvalue + 1;hvalue = compu
12、teHValue(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 addNode(PNode &LIST,PNode theNode)next = LIST-next
13、; LIST-next = theNode;/两个结点是否有相同的状态bool hasSameStatus(PNode ANode , PNode BNode) int i,j; for(i = 0 ; for(j = 0 ; if(ANode-dataij != BNode-dataij)/* 检测theNode是否在LIST表中,若在则sameNode指向与theNode有相同状态的结点 */bool inLink(PNode theNode, PNode &LIST, PNode &sameNode) sameNode = NULL; PNode temp = LIST- while(t
14、emp!=NULL) if(hasSameStatus(theNode,temp) = true) sameNode = temp; temp = temp-/将B节点的状态赋值给A结点void statusBToA(PNode &ANode , PNode BNode) ANode-dataij = BNode-/交换两个数字的值void changeAB(int &A , int &B) int C; C = B; B = A; A = C;/* 初始化OPEN表和CLOSE表,并将开始状态加入OPEN表中 */void initial(PNode &Start) initLink(OPE
15、N); initLink(CLOSE); /初始化起始结点,令初始结点的父节点为空结点 PNode NULLNode = NULL; Start = (PNode)malloc(sizeof(NNode); Start-dataij = startij;parent = NULL;child = NULL; computeAllValue(Start , NULLNode); /起始结点进入open表 addNode(OPEN , Start);/* 从OPEN表(非空)中找到f值最小的结点 */void findfValueMinNode(PNode &theMinNode,PNode &p
16、reNode) PNode p = OPEN,q = OPEN- theMinNode = q; preNode = OPEN; while(q-next) p = q; q = q- if(q-fvalue fvalue) preNode = p;/* 生成theNode结点的子节点的同时进行对子节点的处理 */void genDealSubNode(PNode theNode) int row; int col; PNode sameNode = NULL; getPosition(theNode , row , col); if(col!=2)/空的格子右边的格子向左移动 PNode r
17、lNewNode = (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) )/不在CLOSE表中,但是在OPEN表中 if( sameNode-gvalue gvalue + 1)/把这一格的父节点改成当前格,
18、 并且重新计算这一格的 GF 值 sameNode-parent = theNode; computeAllValue(sameNode, theNode); else/不在CLOSE表中,也不在OPEN表中,则将其加入OPEN表中 addNode(OPEN,rlNewNode); rlNewNode- computeAllValue(rlNewNode, theNode);=0)/空的格子左边的格子向右移动 PNode lrNewNode = (PNode)malloc(sizeof(NNode); statusBToA(lrNewNode , theNode); changeAB(lrNe
19、wNode-datarowcol , lrNewNode-datarowcol - 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)/空的格子下边的格子向上移动 PNode duNewNode = (PNode)malloc(si
20、zeof(NNode); statusBToA(duNewNode , theNode); changeAB(duNewNode-datarow+1col , duNewNode-datarowcol); if( inLink(duNewNode, CLOSE, sameNode)=false )/已经在CLOSE表中,则忽略 if( inLink(duNewNode, OPEN, sameNode) )/不在CLOSE表中,但是在OPEN表中 addNode(OPEN,duNewNode); duNewNode- computeAllValue(duNewNode, theNode);=0)
21、/空的格子上边的格子向下移动 PNode udNewNode = (PNode)malloc(sizeof(NNode); statusBToA(udNewNode , theNode); changeAB(udNewNode-datarow-1col , udNewNode- if( inLink(udNewNode, CLOSE, sameNode)=false )/已经在CLOSE表中,则忽略 if( inLink(udNewNode, OPEN, sameNode) )/不在CLOSE表中,但是在OPEN表中 addNode(OPEN,udNewNode); udNewNode- computeAllValue(udNewNode, theNode);/* 通过调用前面写的函数实现总的函数 */bool A
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2