1 用 A*算法解决八数码问题一、题目：八数码问题也称为九宫问题
在3×3 的棋盘，有八个棋子，每个棋子上标有 1 至 8 的某一数字， 不同棋子上标的数字不相同
棋盘上还有一个空格， 与空格相邻的棋子可以移到空格中
要解决的问题是： 任意给出一个初始状态和一个目标状态， 找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤
二、问题的搜索形式描述状态：状态描述了8 个棋子和空位在棋盘的9 个方格上的分布
初始状态：任何状态都可以被指定为初始状态
操作符：用来产生4 个行动（上下左右移动）
目标测试：用来检测状态是否能匹配上图的目标布局
路径费用函数： 每一步的费用为 1，因此整个路径的费用是路径中的步数
现在任意给定一个初始状态， 要求找到一种搜索策略， 用尽可能少的步数得到上图的目标状态算法介绍三、解决方案介绍1
A* 算法的一般介绍A*（A-Star) 算法是一种静态路网中求解最短路最有效的方法
对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即**fg nsqrtdxnxdxnxdynydyny；这样估价函数 f 在 g 值一定的情况下，会或多或少的受估价值h 的制约，节点距目标点近， h 值小， f 值相对就小，能保证最短路的搜索向终点的方向进行
明显优于盲目搜索策略
2 A star算法在静态路网中的应用2
算法伪代码创建两个表， OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点
算起点的估价值，将起点放入OPEN表
while(OPEN
=NULL) { 从 OPEN表中取估价值 f 最小的节点 n; if(n节点 ==目标节点 ) {break;} for( 当前节点 n 的每个子节点 X) { 算 X 的估价值 ; if(X in OPEN) { if( X的估价值小于 OPEN表的估价值 )
