一、实验内容和要求
八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
例如：
2 8 3 1 2 3 1 6 4 7 0 5
8 4 7 6 5 (a) 初始状态 (b) 目标状态 图1 八数码问题示意图
请任选一种盲目搜索算法（广度优先搜索或深度优先搜索）或任选一种启发式搜索方法（全局择优搜索，加权状态图搜索，A算法或 A* 算法）编程求解八数码问题（初始状态任选）。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进行分析总结，得出结论。 二、实验目的
1. 熟悉人工智能系统中的问题求解过程；
2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用； 3. 熟悉对八数码问题的建模、求解及编程语言的应用。 三、实验算法
A*算法是一种常用的启发式搜索算法。
在A*算法中，一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为： f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值（也称为最小耗费或最小代价），h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数： f(n) = g(n) + h(n)
其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：（1）g(n)>=g'(n)（大多数情况下都是满足的，可以不
用考虑），且f必须保持单调递增。（2）h必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。 3.A*算法的步骤
A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。 A*算法的步骤如下：
1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。
2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。
3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。
4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。
5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。 四、程序框图
五、实验结果及分析 输入初始状态：2 8 3
1 6 4 7 0 5
目标状态： 1 2 3
8 0 4 7 6 5
运行结果屏幕打印
OPEN表与CLOSE表：
OPEN 1 2 3 4 2 3 4 5 6 2 3 4 6 7 2 3 4 6 8 9 2 3 4 8 9 10
2 3 4 8 11 12 13 2 3 4 8 12 13 14 15 3 4 8 12 13 14 15 16 17 4 8 12 13 14 15 16 17 18 19 4 8 12 13 14 15 16 17 19 20 8 12 13 14 15 16 17 19 21 22 12 13 14 15 16 17 19 21 22 23 12 13 14 15 16 17 19 21 22 24 25 12 13 14 15 16 17 19 21 22 24 26 发现26为目标节点
CLOSE 0 0 1 0 1 5 0 1 5 7 0 1 5 7 6 0 1 5 7 6 9 0 1 5 7 6 9 11 0 1 5 7 6 9 11 2 0 1 5 7 6 9 11 2 3 0 1 5 7 6 9 11 2 3 18 0 1 5 7 6 9 11 2 3 18 4 0 1 5 7 6 9 11 2 3 18 4 8 0 1 5 7 6 9 11 2 3 18 4 8 23 0 1 5 7 6 9 11 2 3 18 4 8 23 24
搜索树： 5…8 0 2 3 1 8 4 7 6 5 1…7 2 0 3 1 8 4 7 6 5 2..11 2 8 3 1 6 4 7 0 5 0…7 2 8 3 1 04 7 6 5 3..11 2 8 3 0 1 4 7 6 5 4..11 2 8 3 1 4 0 7 6 5 6…9 2 3 0 1 8 4 7 6 5 10.14 2 8 3 1 6 4 7 0 5 11.14 2 8 3 1 6 4 7 50 18.10 0 8 3 21 4 7 6 5 19.12 2 8 3 71 4 0 6 5 21.12 2 8 3 1 4 3 7 6 5 22.14 2 8 3 1 4 5 7 6 0 7…9 1 2 3 084 76 5 10.11 2 3 4 1 80 76 5 20.11 80 3 21 4 7 6 5 12 3 24..8 12 3 70 4 68 5 8..12 78 4 0 6 5 9..10 12 3 80 4 7 6 5 23..9 12 3 78 4 60 5 11..9 10 3 82 4 7 6 5 12.13 12 3 86 4 7 0 5 13.13 12 3 84 0 7 6 5 注释： 每个方格中最上面两个数字分别为编号与启发值，下面九个数字为八数码。较粗的箭头为解路径
25.12 12 3 78 4 650
目标节点
14.12 013 82 4 7 6 5
15.14 310 82 4 7 6 5
六、结论
对于八数码问题，BFS算法最慢，A*算法较快。八数码问题的一个状态实际上是0~9的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列。如果一个数字0~8的随机排列871526340，用F(X)表示数字X前面比它小的数的个数，全部数字的F(X)之和为Y=∑(F(X))，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。因此，
