1、1八数码问题 A*算法的实现及性能分析计算机科学与技术学院专业：计算机科学与技术161210404 杨凯迪2目录一、8 数码问题 .31.问题描述 .32. 八数码问题形式化描述 .33. 解决方案 .4二、A*算法 .41. A*搜索算法一般介绍 .42. A*算法的伪代码 .53. 建立合适的启发式 .6三、算法实现及性能比较 .7四、算法性能分析 .8五、结论 .9六、参考文献 .10附录 .103一、8 数码问题1.问题描述八数码问题是指这样一种游戏：将分别标有数字 1，2，3，8 的八块正方形数码牌任意地放在一块 33 的数码盘上。放牌时要求不能重叠。于是，在 33 的数码盘上出现了
2、一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动，在四个角落上有 2 个方向可移动，在其他位置上有 3 个方向可移动，问题描述如图 1-1 所示初始状态 过渡状态 最终状态图 1-1 八数码问题执行过程2. 八数码问题形式化描述初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把 33的棋盘按从左到右，从上到下的顺序写成一个一维向量。我们可以设定初始状态：后继函数：按照某种规则移动数字得到的新向量。例如：目标测试：新向量是都是目标状态。
3、即是目标状态？路径耗散函数：每次移动代价为 1，每执行一条规则后总代价加 1。43. 解决方案该问题是一个搜索问题。它是一种状态到另一种状态的变换。要解决这个问题，必须先把问题转化为数字描述。由于八数码是一个 3*3 的矩阵，但在算法中不实用矩阵，而是将这个矩阵转化为一个一维数组，使用这个一维数组来表示八数码，但是移动时要遵守相关规则。(1) 可用如下形式的规则来表示数字通过空格进行移动：(2)共 24 条移动规则，对应与每个位置的移动规则。(3)搜索顺序举例：1) 优先移动行数小的棋子(数字)2) 同一行中优先移动列数大的棋子(4)约束规则：不使离开既定位置的数字数增加八数码的节点扩展应当遵
4、循棋子的移动规则。按规则，每一次可以将一个与空格相邻的棋子移动到空格中，实际上也可以看做空格的相反方向移动。空格的移动方向可以是上下左右，当然不能出边界。棋子的位置，也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格向右，下，左，上移动后，新位置是原位置分别加上 1,3，-1，-3。在这里，空格可以用任意数字表示。操作本文用 u(up) r(right) d(down) l(left) 分别表示空格的向上向右向下向左四个操作。经分析，8 数码问题的搜索策略共有：1.广度优先搜索、2.深度优先搜索、3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，等
5、等。其中广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。本实验采用启发式 A*搜索算法来实现。二、A*算法1. A*搜索算法一般介绍A* 算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数评估每次的的决策的价值，决定先尝试哪一种方案，这样可以极大的优化普通的广度优先搜索。一般来说，从出发点(A)到目的地 (B)的最短距离是固定的，我们可以写一个函数 judge() 估计 A 到 B 的最短距离，如果程序已经尝试着5从出发点 A 沿着某条路线移动到了 C 点, 那么我们认为这个方案的 A B 间的估计距离为 A 到 C 实际已经行走了的
6、距离 H 加上用 judge() 估计出的 C 到 B 的距离。如此，无论我们的程序搜索展开到哪一步，都会算出一个评估值，每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：f(n) = g(n) + h(n)这里，f(n)是估价函数，g(n) 是起点到终点的最短路径值， h(n)是 n 到目标的最断路经的启发值。由于这个 f(n)其实是无法预先知道的，所以我们用前面的估价函数 f
7、(n)做近似。g(n) 代替 g(n)，但 g(n)=g(n)才可（大多数情况下都是满足的，可以不用考虑） ，h(n)代替 h(n)，但 h(n)#include#include#include#includeusing namespace std;struct nodeint a33; /存放矩阵int father; /父节点的位置 int gone; /是否遍历过,1为是,0为否int fn; /评价函数的值int x,y; /空格的坐标int deep; /节点深度 ;vector store; /存放路径节点int mx4=-1,0,1,0;int my4=0,-1,0,1; /上下左右移动数组int top; /当前节点在store中的位置bool check(int num) /判断storenum节点与目标节点是否相同,目标节点储存在store0
