. .
用 A*算法解决八数码问题
一、 题目:八数码问题也称为九宫问题。在 3×3 的棋盘,有八个棋子,每个
棋子上标有 1 至 8 的某一数字,不同棋子上标的数字不一样。棋盘上还有
一个空格,与空格相邻的棋子可以移到空格中。要解决的问题是:任意给
出一个初始状态和一个目标状态,找出一种从初始转变成目标状态的移动
棋子步数最少的移动步骤。
二、 问题的搜索形式描述
状态:状态描述了 8 个棋子和空位在棋盘的 9 个方格上的分布。
初始状态:任何状态都可以被指定为初始状态。
操作符:用来产生 4 个行动〔上下左右移动〕。
目标测试:用来检测状态是否能匹配上图的目标布局。
路径费用函数:每一步的费用为 1,因此整个路径的费用是路径中的步数。
现在任意给定一个初始状态,要求找到一种搜索策略,用尽可能少的步数
得到上图的目标状态算法介绍
三、解决方案介绍
1.A*算法的一般介绍
A*〔A-Star)算法是一种静态路网中求解最短路最有效的方法。对于几
何路网来说,可以取两节点间欧几理德距离〔直线距离〕做为估价值,即
f g
n
sqrt
dx nx
*
dx nx
dy ny
*
dy ny
;
这样估价函数 f 在 g 值一定的情况下,会或多或少的受估价值 h 的制约,
节点距目标点近,h 值小,f 值相对就小,能保证最短路的搜索向终点的
方向进展。明显优于盲目搜索策略。
优选