8
数和
15
数问题
－、问题描述
8
数或
15
数问题是同一个问题，其就是一个随机排列的
8
个或
15
个数在一个方正格子中移动到达规定的一个目标状态。由于只有一个空格子，故只有在空格附近的棋子可以移动。
二、算法描述
F
算法选择
此问题需要对所有可能的路径进行穷举，但是由于随着树的高度的加大，其子结点的增加宿舍剧增，所以对所有的子结点进行穷举是不大现实的。而根据当前的状态和目标状态进行对比可以用一个评估函数来评估当前状态的好坏情况。而在这里我们选择
A*
算法来进行求解，
A*
算法是一种最好优先的算法。
f'(n) = g'(n) + h'(n)
，
f'(n)
是估价函数，
g'(n)
是起点到终点的最短路径值，这里就表示树的高度，
h'(n)
是
n
到目标的最断路经的启发值，其原理是把当前产生的状态和以前所以的状态的评估函数值进行对比，选择其中最小的评估函数继续进行下一步。这里我选择
h'(n)
的启发值为每个格子到达它的目标位置所需要经过的最少步数。
F
算法描述
需要说明的几点：
1.
用
OpenArr
表示初始节点列表
(
待扩展，此为一个动态数组
)
2
．
ClosedArr
保存已经访问过的结点
3
．算法首先需要给出初始状态，由于随机产生的状态并不一定能够走到目标状态，因此这里采用从标准状态往回走产生一个被打乱的随机状态，这样可以保证有解。
算法实现：
1.
OpenArr
放置初始结点
2.
如果
OpenArr
为空集，则退出并给出失败信号
3. n
取为
OpenArr
的第一个节点，并从
OpenArr
中删除节点
n
4.
如果
n
为目标节点，则退出并给出成功信号
5.
否则，将产生
n
子节点，并对
n
的每个子结点
n’
进行如下操作：
1
）如果
n’
不在
OpenArr
和
ClosedArr
表中，则把
n’
放入
OpenArr
表中
2
）否则，如果在
OpenArr
表中，计算评估值，并且如果比表中的评估函数的值小，则更新表中的评估值为当前的值。
3
）否则，如果在