课 程 论 文
论文名称 姓 名 班 级 学 号 课程名称 任课教师 学 期 所在院系 八数码问题 人工智能 摘 要
八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。 八数码问题一般使用搜索法来解。
搜索法有广度优先搜索法、深度优先搜索法、A*算法等。这里详细讲述A*算法。
关键词:八数码问题；空间状态；搜索法；A*算法
一、 实验目的
理解并熟悉掌握A*算法。 二、 实验内容
九宫格中有8个数码，其中只有一个空，规则是只能把一个数码移动到空的格子中，要求从一个初始状态移动到一个目标状态所要花费的最少步数
三、问题的搜索形式描述（4要素） 初始状态：
8个数字将牌和空格在九宫格棋盘上的所有格局组成了问题的状态空间。其中，状态空间中的任一种状态都可以作为初始状态。 后继函数：
通过移动空格（上、下、左、右）和周围的任一棋子一次，到达新的合法状态。 目标测试：
比较当前状态和目标状态的格局是否一致。 路径消耗：
每一步的耗散值为1，因此整个路径的耗散值是从起始状态到目标状态的棋子移动的总步数。 四、解决方案介绍（原理）
常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广
度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。在这里就要用到启发式搜索
启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n) 其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。 在此八数码问题中，显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数，即错位数。 五、算法介绍
5.1 搜索算法一般介绍
在本实验中使用A*算法求解。A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。 5.2 算法伪代码
算法的功能：产生8数码问题的解(由初始状态到达目标状态的过程）
输入：初始状态，目标状态
输出：从初始状态到目标状态的一系列过程 算法描述： Begin：
读入初始状态和目标状态，并计算初始状态评价函数值f； 根据初始状态和目标状态，判断问题是否可解； If(问题可解)
把初始状态假如open表中； While（未找到解&&状态表非空）
①在open表中找到评价值最小的节点，作为当前结点；
②判断当前结点状态和目标状态是否一致，若一致，跳出循环；否则跳转到③；
③对当前结点，分别按照上、下、左、右方向移动空格位置来扩展新的状态结点，并计算新扩展结点的评价值f并记录其父节点；
④对于新扩展的状态结点，判断其是否重复，若不重复，把其加入到open表中；
⑤把当前结点从open表中移除；
End while End if
输出结果； End