。。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表的估价值 ) { 把 n 设置为 X 的父亲 ; 更新 OPEN表中的估价值 ; //取最小路径的估价值 } } if(X inCLOSE) { if( X的估价值小于 CLOSE表的估价值 ) { 把 n 设置为 X 的父亲 ; 更新 CLOSE表中的估价值 ; 把 X 节点放入 OPEN //取最小路径的估价值 } } if(X not inboth) { 把 n 设置为 X 的父亲 ; 求 X 的估价值 ; 并将 X 插入 OPEN表中; //还没有排序 } 。。3 }//end for 将 n 节点插入 CLOSE表中; 按照估价值将 OPEN表中的节点排序 ; // 实际上是比较 OPEN表内节点f 的大小，从最小路径的节点向下进行。}//end while(OPE...
