1. 概述
1.1 八数码问题
所谓八数码问题是指这样一种游戏：将分别标有数字 1，2，3，…，8 的八
块正方形数码牌任意地放在一块 3×3 的数码盘上。放牌时要求不能重叠。于是，
在 3×3 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数
码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。如下
图表示了一个具体的八数码问题求解。
1.2 A*算法
A*算法属于一种启发式搜索,它扩展结点的次序类似于广度优先搜索,但不同
的是每生成一个子结点需要计算估价函数 F,以估算起始结点的约束经过该结点
至达目标结点的最佳路径代价;每当扩展结点时,意是在所有待扩展结点中选择具
有最小 F 值的结点做为扩展对象,以便使搜索尽量沿最有希望的方向进行.A*算
法只要求产生问题的全部状态空间的部分结点及关系,就可以求解问题了,搜索效
率较高。
1.3 A*算法的一般描述
1.3.1 约定
S：指示初使状态节点（Note）； G：指示搜索图
OPEN：作为存放待扩展节点的表；SNS：子节点集合
CLOSE：作为存放已被扩展节点的表
Move_First(Open)：指示取 Open 表首节点作为当前要被扩展的节点 n，同时
将节点 n 移到 CLOSE 表；
F(n) = G(n) + H(n)：评价函数，用于排列节点在 OPEN 表中的位置
1.3.2 算法过程
G:=S; OPEN := (S), CLOSE := ();
如果 OPEN 为空则算法失败
n := Move_First(OPEN);
如果 n 是目标结点，搜索完成。
