用A星算法解决八数码问题.docx

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

1、A*算法解决八数码问题1问题描述1.1什么是八数码问题八数码游戏包括一个3×3的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。与空位相邻的棋子可以滑动到空位中。游戏的目的是要达到一个特定的目标状态。标注的形式化如下：123456781.2问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。初始状态：任何状态都可以被指定为初始状态。操作符：用来产生4个行动（上下左右移动）。目标测试：用来检测状态是否能匹配上图的目标布局。路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得

2、到上图的目标状态。1.3解决方案介绍1.3.1算法思想估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n)其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解）的条件，关键在于估价函数h(n)的选取。估价值h(n)<=n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值>实际值,搜索的点数少

3、，搜索范围小，效率高，但不能保证得到最优解。搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。1.3.2启发函数   进一步考虑当前结点与目标结点的距离信息，令启发函数h(n)为当前8个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有h(t)=0，对于结点m和n（n是m的子结点）有h(m)–h(n)<=1=Cost(m,n)满足单调限制条件。2算法介绍2.1A*算法的一般介绍A*（A-Star)算法是一种静态路网中求解最短路最有  A star算法在静态路网中的应用效的

4、方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。2.2算法伪代码　　创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。　　while(OPEN!=NULL)　　　{　　　从OPEN表中取估价值f最小的节点n;　if(n节点=

5、=目标节点){break;}　　　for(当前节点n的每个子节点X)　　　{　　算X的估价值;　　　if(XinOPEN)　　{　if(X的估价值小于OPEN表的估价值){把n设置为X的父亲;　　　更新OPEN表中的估价值;//取最小路径的估价值}　　}if(XinCLOSE){　if(X的估价值小于CLOSE表的估价值){把n设置为X的父亲;　　　更新CLOSE表中的估价值;　　　把X节点放入OPEN//取最小路径的估价值}　　　}if(Xnotinboth){把n设置为X的父亲;　　求X的估价值;　　　并将X插入OPEN表中;//还没有排序}　　}//endfor　　

6、将n节点插入CLOSE表中;　　　按照估价值将OPEN表中的节点排序;//实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。　　}//endwhile(OPEN!=NULL)保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；3算法实现3.1实验环境与问题规模对于８数码问题，每个结点有８个数字和一个空格，可以将空格看成０，那么一共有９个数字，３２位的int可以表示２*109，可以用一个整数表示一个结点对应的信息。计算一个整数中０（即空格）的位置比较耗时间，用一个整数存储当前结点０的位置，还要存储对应的g,h值以及该结点由哪个结点扩展来的信

7、息。本实验用C++编写源程序，环境选用VisualStudio2005。程序采用文本输入输出，输入文件为astar.in，A*算法输出文件为astar.out，可以用记事本打开。输入格式为一个测试用例由两个中间由一空行隔开的８数码格局组成，输出为对应测试用例的走法路径及相关统计信息，程序假定输入数据符合要求，未做检查。3.2数据结构3.2.1open表的数据结构表示     考虑对open表的操作，每次需要得到所有待扩展结点中f值最小的那个结点，用堆进行实现，可以达到O(log(heapSize))时间复杂度。3.2.2clo