用A算法解决八数码问题 精品资料

仅供学习与交流，如有侵权请联系网站删除 谢谢2 用A*算法解决八数码问题 一、 题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。 二、 问题的搜索形式描述 状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。 初始状态：任何状态都可以被指定为初始状态。 操作符：用来产生4个行动（上下左右移动）。 目标测试：用来检测状态是否能匹配上图的目标布局。 路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。 现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍 三、 解决方案介绍 1.A*算法的一般介绍 A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即 **fgnsqrtdxnxdxnxdynydyny；

这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。 精品资料

仅供学习与交流，如有侵权请联系网站删除 谢谢3 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表的估价值 ) 精品资料 仅供学习与交流，如有侵权请联系网站删除 谢谢4 {把n设置为X的父亲; 更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值} } if(X not inboth) {把n设置为X的父亲; 求X的估价值; 并将X插入OPEN表中; //还没有排序} }//end for 将n节点插入CLOSE表中; 按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。 }//end while(OPEN!=NULL) 保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径. 四、 源程序 #include #include #include

using namespace std;

constint ROW = 3; constint COL = 3; constint MAXDISTANCE = 10000; constint MAXNUM = 10000; 精品资料 仅供学习与交流，如有侵权请联系网站删除 谢谢5

int abs(int a) { if (a>0) return a; else return -a; }

typedefstruct _Node{ int digit[ROW][COL]; intdist; // 距离 intdep; // 深度 int index; // 索引值 } Node; Node src, dest; vectornode_v; // 储存节点 boolisEmptyOfOPEN() { //判断Open表是否空 for (inti = 0; iif (node_v[i].dist != MAXNUM) return false; } return true; } boolisEqual(int index, int digit[][COL]) {//判断节点是否与索引值指向的节点相同 for (inti = 0; i< ROW; i++) for (int j = 0; j < COL; j++) { if (node_v[index].digit[i][j] != digit[i][j]) return false; } 精品资料 仅供学习与交流，如有侵权请联系网站删除 谢谢6 return true; }

ostream& operator<<(ostream&os, Node& node) { for (inti = 0; i< ROW; i++) { for (int j = 0; j < COL; j++) os

void PrintSteps(int index, vector&rstep_v){//输出步骤 rstep_v.push_back(node_v[index]); index = node_v[index].index; while (index != 0) { rstep_v.push_back(node_v[index]); index = node_v[index].index; }

for (inti = rstep_v.size() - 1; i>= 0; i--) cout<< "Step " <<}

void Swap(int& a, int& b) { //交换 int t; t = a; a = b; 精品资料 仅供学习与交流，如有侵权请联系网站删除 谢谢7 b = t; }

void Assign(Node& node, int index) {//获取节点 for (inti = 0; i< ROW; i++) for (int j = 0; j < COL; j++) node.digit[i][j] = node_v[index].digit[i][j]; }

intGetMinNode() {//获取启发值最小的节点 intdist = MAXNUM; intloc; // the location of minimize node for (inti = 0; iif (node_v[i].dist == MAXNUM) continue; else if ((node_v[i].dist + node_v[i].dep) loc = i; dist = node_v[i].dist + node_v[i].dep; } }

returnloc; }

boolisExpandable(Node& node) {//判断是否可扩展 for (inti = 0; iif (isEqual(i, node.digit)) return false; } 精品资料 仅供学习与交流，如有侵权请联系网站删除 谢谢8 return true; }

int Distance(Node& node, int digit[][COL]) {//计算距离 int distance = 0; bool flag = false; for(inti = 0; i< ROW; i++) for (int j = 0; j < COL; j++) for (int k = 0; k < ROW; k++) { for (int l = 0; l < COL; l++) { if (node.digit[i][j] == digit[k][l]) { distance += abs(i - k) + abs(j - l); flag = true; break; } else flag = false; } if (flag) break; } return distance; }

intMinDistance(int a, int b) {//二者取小 return (a < b ? a : b); }

void ProcessNode(int index) {//展开节点