八数码问题A*算法的实现及性能分析 计算机科学与技术学院专业：计算机科学与技术 杨凯迪目录一、8数码问题1.问题描述八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8 的八块正方形数码牌任意地放在一块3×3 的数码盘上放牌时要求不能重叠于是，在3×3 的数码盘上出现了一个空格现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如图1-1所示 初始状态 过渡状态 最终状态图1-1 八数码问题执行过程2. 八数码问题形式化描述初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字把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,8>目标测试：新向量是都是目标状态。
即<1,2,3,4,5,6,7,8,0>是目标状态？路径耗散函数：每次移动代价为1，每执行一条规则后总代价加13. 解决方案该问题是一个搜索问题它是一种状态到另一种状态的变换要解决这个问题，必须先把问题转化为数字描述由于八数码是一个3*3的矩阵，但在算法中不实用矩阵，而是将这个矩阵转化为一个一维数组，使用这个一维数组来表示八数码，但是移动时要遵守相关规则1) 可用如下形式的规则来表示数字通过空格进行移动：→(2)共24条移动规则，对应与每个位置的移动规则3)搜索顺序举例： 1) 优先移动行数小的棋子(数字) 2) 同一行中优先移动列数大的棋子(4)约束规则：不使离开既定位置的数字数增加八数码的节点扩展应当遵循棋子的移动规则按规则，每一次可以将一个与空格相邻的棋子移动到空格中，实际上也可以看做空格的相反方向移动空格的移动方向可以是上下左右，当然不能出边界棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格向右，下，左，上移动后，新位置是原位置分别加上1,3，-1，-3。
在这里，空格可以用任意数字表示操作本文用u(up) r(right) d(down) l(left) 分别表示空格的向上向右向下向左四个操作经分析，8数码问题的搜索策略共有：1.广度优先搜索、2.深度优先搜索、3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，等等其中广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法本实验采用启发式A*搜索算法来实现二、A*算法1. A*搜索算法一般介绍A* 算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数评估每次的的决策的价值，决定先尝试哪一种方案，这样可以极大的优化普通的广度优先搜索一般来说，从出发点(A)到目的地(B)的最短距离是固定的，我们可以写一个函数 judge() 估计 A 到 B 的最短距离，如果程序已经尝试着从出发点 A 沿着某条路线移动到了 C 点, 那么我们认为这个方案的 A B 间的估计距离为 A 到 C 实际已经行走了的距离 H 加上用 judge() 估计出的 C 到 B 的距离如此，无论我们的程序搜索展开到哪一步，都会算出一个评估值，每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束。
A*算法是一个可采纳的最好优先算法A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n)这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值，h'(n)是n到目标的最断路经的启发值由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似g(n)代替g'(n)，但g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的2. A*算法的伪代码创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点 算起点的估价值; 将起点放入OPEN表; while(OPEN!=NULL) { 从OPEN表中取估价值f最小的节点n; if(n节点==目标节点){ break; } for(当前节点n 的每个子节点X) { 算X的估价值; if(X in OPEN) { if( X的估价值小于OPEN表的X估价值 ){ 把n设置为X的父亲; 更新OPEN表中的估价值; //取最小路径的估价值 } } if(X inCLOSE) { if( X的估价值小于CLOSE表的X估价值 ){ 把n设置为X的父亲; 将该节点从close表中除去 把X节点放入OPEN //取最小路径的估价值 } } if(X not inboth){ 把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //升序排列open } }//end for 将n节点插入CLOSE表中; 按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}//end while(OPEN!=NULL) 保存路径，即从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径；3. 建立合适的启发式A*算法有个计算公式 f(x) = g(x)+h(x)其中g(x)为从起始状态到当前状态所消耗的步数，h(x)为一个启发值，估算从当前状态到目标状态所需的步数，一般h(x)小于等于实际需要步数为好，这样不会将最优解忽略，因为h(x)和解空间有一些关系，如果h(x)设置的比实际需要的步数多，那么解空间就有可能将最优解忽略举个例子吧，宽度优先搜索就是h(x)=0带来的效果，深度优先搜索就是g(x)=0带来的效果，不过h(x)距离h*(x)[实际需要的步数]的程度不能过大，否则h(x)就没有过强的区分能力，算法效率并不会很高对一个好的h(x)的评价是：h(x)在h*(n)[实际需要的步数]的下界之下，并且尽量接近h*(n)[实际需要的步数].那么8数码问题g(x) 为经过上下左右移动空格附近的数字来得到新状态所需步数，h(x)为当前状态与目标状态的距离，就是所有不在目标位置的数字总和，必然小于h*(x)三、算法实现及性能比较这里通过c++语言来实现各种排序算法（源码见附录），程序运行环境为windows 7，所用编译器为vs2013。
实验分别以不同的初始棋盘和相同的目标棋盘为例进行测试初始数码棋盘1：2 0 3 1 4 6 7 5 8初始数码棋盘2：2 4 3 0 6 8 1 7 5初始数码棋盘3：2 3 7 6 4 8 1 0 5初始数码棋盘4：3 2 4 5 0 7 8 1 6初始数码棋盘5：4 0 3 2 6 8 1 7 5初始数码棋盘6：1 4 3 5 7 0 2 6 8 初始数码棋盘7：4 6 3 2 8 5 1 0 7目标数码棋盘：1 2 3 4 5 6 7 8 0实验部分结果如图3-1：图3-1.测试结果四、算法性能分析在测试中我们根据不同的初始数码状态相同的目标数码状态，产生不同的移动步骤，并给出了其步数和运行时间（单位ms）表1为不同的初始数码状态相同的目标数码状态测试后得到的运行时间数据表2为不同的初始数码状态相同的目标数码状态能否的到正确的步骤与否的数据 初始数据棋盘1棋盘2棋盘3棋盘4棋盘5棋盘6棋盘7步数51121013017时间(ms)52.531507.6918220134.4202815.83表1 步数和运行时间（单位ms） 初始数据棋盘1棋盘2棋盘3棋盘4棋盘5棋盘6棋盘7正确与否TTTFTFT表2 能否得到正确步骤为了直观起见，根据实验数据画出不同的初始数码状态相同的目标数码状态下时间随步数的变化趋势图如图3-2所示： 图3-2时间随步数的变化趋势图根据实验数据表2，我们可得到该算法得到正确步骤路径的概率为：71.42%。
五、结论最后我们得出结论：时间性能上，算法所需时间随步数的增加而逐渐呈增加趋势，但并不是线性增长部分时间不随移动步数变化该算法能得到正确的解概率约为71.42%六、参考文献1．《Artificial intelligence :;a modern approach 人工智能 : 一种现代方法》 作者：Russell, Stuart J. 出版社：清华大学出版社附录#include#include#include#include#includeusing namespace std;struct node{ int a[3][3]; //存放矩阵 int father; //父节点的位置 int gone; //是否遍历过,1为是,0为否 int fn; //评价函数的值 int x,y; //空格的坐标 int deep; //节点深度 };vector store; //存放路径节点int mx[4]={-1,0,1,0};int my[4]={0,-1,0,1。