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