用A算法解决八数码问题

《用A算法解决八数码问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档用A*算法解决八数码问题一、题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。二、问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。初始状态：任何状态都可以被指定为初始状态。操作符：用来产生4个行动（上下左右移动）。目标测试：用来检测状态是否能匹配上图的目标布局。路径费用函数：

2、每一步的费用为1，因此整个路径的费用是路径中的步数。现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍三、解决方案介绍1.A*算法的一般介绍A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即实用文档；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。Astar算法在静态路网中的应用2.算法伪代码创建两个表

3、，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。　　while(OPEN!=NULL)　　　{　　　从OPEN表中取估价值f最小的节点n;　if(n节点==目标节点)实用文档{break;}　　　for(当前节点n的每个子节点X)　　　{　　算X的估价值;　　　if(XinOPEN)　　{　if(X的估价值小于OPEN表的估价值){把n设置为X的父亲;　　　更新OPEN表中的估价值;//取最小路径的估价值}　　}if(XinCLOSE){　if(X的估价值小于CLOS

4、E表的估价值){把n设置为X的父亲;　　　更新CLOSE表中的估价值;　　　把X节点放入OPEN//取最小路径的估价值}　　　}if(Xnotinboth)实用文档{把n设置为X的父亲;　　求X的估价值;　　　并将X插入OPEN表中;//还没有排序}　　}//endfor　　将n节点插入CLOSE表中;　　　按照估价值将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。　　}//endwhile(OPEN!=NULL)保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径.四、

5、源程序#include#include#includeusingnamespacestd;constintROW=3;实用文档constintCOL=3;constintMAXDISTANCE=10000;constintMAXNUM=10000;intabs(inta){if(a>0)returna;elsereturn-a;}typedefstruct_Node{intdigit[ROW][COL];intdist;//距离intdep;//深度intindex;//索引值}Nod

6、e;Nodesrc,dest;vectornode_v;//储存节点实用文档boolisEmptyOfOPEN(){//判断Open表是否空for(inti=0;i

7、ndex].digit[i][j]!=digit[i][j])returnfalse;}returntrue;}ostream&operator<<(ostream&os,Node&node){实用文档for(inti=0;i&rstep_v){//输出步骤rstep_v.push_back(node_v[inde

8、x]);index=node_v[index].index;while(index!=0){rstep_v.push_back(node_v[index]);index=node_v[index].index;}for(