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

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

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

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

4、(直线距离)做为估价值，即 f=g(n) +sqrt (dxnx)*(dxnx) + (dy-ny)*(dy-ny):这样估价函数 f 在 g 值一定的情况卜一, 会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路 的搜索向终点的方向进行。明显优于盲目搜索策略。算法伪代码创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节 点。算起点的估价值，将起点放入OPEN表。while(OPEN!二NULL)从OPEN表中取估价值f最小的ij点n;if (n舀点=目标节点)break;for (当前节点n的每个子节点X)算X的估价值；辻(X

5、in OPEN)if( X的估价值小于0PE7表的估价值)把“设宜为X的父亲；更新OPEN表中的估价值；中有结点设为nl被扩展放入closed表时，nl的前驱刚好已 经存储好。下而说明closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed 表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时 它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱结 点的下标位宜，可以用数组实现，每个结点记录整数表示的8数码格局和它的前驱结点的下 标，输出路径时，根据前驱结点形成到达根结点的链条，递归输岀即可。解决结点重复扩展问题对于一个

6、结点有多种方式到达该结点，这样就可能多次将它加入op亡n表中，而 启发函数满足单调限制条件，后来达到该结点的路径不再是更优的，可以不予考虑。扩展某 结点时先看该结点是否已经扩展过，如果扩展过则略过。实现的可以线形遍历closed表， 但效率不高时间复杂度为0 ( closedSize),考虑每个结点可以用一个整数标识，用二叉平衡查找树可以得到更好的时间复杂度0 ( log (closedSize),程序中用基于红黑树思想 的set实现。实验结果输入数据(0表示空格)步数扩展结点数生成结点数搜索用时(亳秒)3124056782110312475680417280372815460无解112345

7、6780227913120192266参考文献王勋，凌云，费玉莲.2005.人工智能导论北京：科学出版社广树建，王锂淇.2008.新编C/C+程序设计教程广州：华南理工大学出版社 王文杰，史忠植2007.人工智能原理辅导与练习北京：淸华大学出版社出附录一源代码及其注释源代码及测试数据/*算法：A*是否最优解：是启发函数：每一个数字位与目标中该数字位的距离，满足单调限制。说明：A*算法是启发式搜索算法，搜索时充分利用当前状态距目标距离远近的启发信息，选取 当前未扩展结点中估价函数最小的进行扩展，生成结点数少，搜索空间较小，实现稍复杂, 备注：程序未对输入数孺进行检査 */pragma warni

8、ng(disable:4786) #include include include #include include using namespace std;/*item记录搜索空间中一个结点 state记录用整数形式表示的8数码格局 blank记录当前空格位置，主要用于程序优化，扩展时可不必在寻找空格位置g, h 对应 g(n), h(n)pre 记录当前结点由哪个结点扩展而来*/struct itemint state;int blank;int g；int h;int pre;； const int MAXSTEPS = 100000;const int MAXCHAR = 100;ch

9、ar bufMAXCHARMAXCHAR;irst)；puts();return;path (closedindex second); pr (closedindex first); puts();+steps;int mainOunsigned int tl = clock();freopenC, r, stdin);freopen(，z/z,stdout);setstates;char tmpC100;int i, x, y, a, b, nx, ny, end, next, index, kase = 0;pair start, target;item head;tate =;open

10、0h= calculate,;open 0b lank =;open0 pre= -1;open0. g= 0;index = 0;irst = open0state;open 10 preclosedindexsecond =re = index;open .endblank = b;open .endstate = next;open.end h=calculate(next,open lend g= + 1;+end;push_heap (open, open + end, cmpO);if (end = 0)puts(No solution);elsesteps);index);ind

11、ex + end);clock 0 一 t2);printf(，zNum of steps: %drT,printf (，zNum of expanded: %dn/z,printf(，zNum of generated: %dn，z,printfCTime consumed: %dnnz，, steps = 0;printf (Total time consumed: %dn，clockO - tl);return 0;系统中间及最终输出结果输入312405678Docu*ents and SettingsAdMinisratorDebug 1 exe*Please input the nu

12、nber: 3124M5678Now the initial nunbers are:2 5 8 t 2 5 8 2 5 8 107147 147 346AI03G306Is3 124 R 5fi 7 8Time cost：0nsTotaly covered steps：2Press any key to continue输入 312475680ozo8 4 2m 9 S2t250t258 2 5 8 2 5 8 2 5 8 2 5 5 Iwl78dl47 147 107 17 M? 0ys P3N346A026 3 0 G 3146 3 4 6 3 4.2 6input the number

13、0 for the blank?：7 5 6 8 0 initial numbers are:Target is：3 124 7 56 8 0T ime cost :0ms：Totaly coueied steps：4Press any key to continue输入 372815460*C: Docu*ents and Sett ingskAdBinist rat orDebug 1 exePlease input the niinbep： 37281546014 7Now the initial numbers are:No one can solue it?输入123456780cxc-OXIP lease input the n umber ：1 23456780Now the initial nunhers ai*e:zJ-I14 714? 047 4R7 437 432 5 8 258 2 5 8 2 5 0 2 0 5 2 3 5 2437A 43? 430 438 4 0