用A星算法解决八数码问题

A*算法解决八数码问题1 问题描述1.1 什么是八数码问题 八数码游戏包括一个3× 3 的棋盘，棋盘上摆放着8 个数字的棋子，留下一个空位。与空位相邻的棋子可以滑动到空位中。游戏的目的是要达到一个特定的目标状态。标注的形式化如下：1 2 3 4 5 6 7 8 1.2 问题的搜索形式描述 状态 ：状态描述了8 个棋子和空位在棋盘的9 个方格上的分布。初始状态 ：任何状态都可以被指定为初始状态。操作符 ：用来产生4 个行动（上下左右移动）。目标测试 ：用来检测状态是否能匹配上图的目标布局。路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态。1.3 解决方案介绍1.3.1 算法思想估价函数是搜索特性的一种数学表示，是指从问题树根节点到达目标节点所要耗费的全部代价的一种估算，记为f(n)。估价函数通常由两部分组成，其数学表达式为f(n)=g(n)+h(n) 其中 f(n) 是节点 n 从初始点到目标点的估价函数，g(n) 是在状态空间中从初始节点到n 节点的实际代价，h(n) 是从 n 到目标节点最佳路径的估计代价。保证找到最短路径（最优解）的条件，关键在于估价函数h(n) 的选取。估价值h(n)实际值 , 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。搜索中利用启发式信息，对当前未扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。1.3.2 启发函数进一步考虑当前结点与目标结点的距离信息，令启发函数h ( n )为当前 8 个数字位与目标结点对应数字位距离和（不考虑中间路径），且对于目标状态有h ( t ) = 0，对于结点 m 和 n （n 是 m 的子结点）有 h ( m ) h ( n ) #include #include #include #include #include #include using namespace std;/* item记录搜索空间中一个结点state 记录用整数形式表示的8 数码格局blank 记录当前空格位置，主要用于程序优化，扩展时可不必在寻找空格位置g, h 对应 g(n), h(n) pre 记录当前结点由哪个结点扩展而来*/ struct item int state; int blank; int g; int h; int pre; ; const int MAXSTEPS = 100000; const int MAXCHAR = 100; char bufMAXCHARMAXCHAR; /open表item openMAXSTEPS; int steps = 0; /closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径/ 每次只需得到对应f 值最小的待扩展结点，用堆实现提高效率pair closedMAXSTEPS; / 读入，将8 数码矩阵格局转换为整数表示bool read(pair if (!gets(buf1) return false; if (!gets(buf2) return false; assert(strlen(buf0) = 5 state.first = 0; for (int i = 0, p = 1; i b.g + b.h; ; / 将整数形式表示转换为矩阵表示输出void pr(int state) memset(buf, ' ', sizeof(buf); for (int i = 0; i = 0 char tmp100; int i, x, y, a, b, nx, ny, end, next, index, kase = 0; pair start, target; item head; /4个方向移动时的偏移量const int xtran4 = -1, 0, 1, 0; const int ytran4 = 0, 1, 0, -1; const int p = 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000; while (read(start) unsigned int t2 = clock(); printf(“Case %d:nn“, +kase); gets(tmp); read(target); gets(tmp); / 初始化 open表，将初始状态加入open0.state = start.first; open0.h = calculate(start.first, target.first); open0.blank = start.second; open0.pre = -1; open0.g = 0; index = 0; states.insert(start.first); / 提取 open 表中 f 值最小元素放入closed表，并对该结点进行扩展for (end = 1; end > 0; +index) assert(index < MAXSTEPS); / 临时存储head = open0; / 放入 closed表记录当前格局和由哪个结点扩展而来（该结点肯定已在 closed表中）closedindex.first = open0.state; closedindex.second = open0.pre; / 从 open 表中删除该结点pop_heap(open, open + end, cmp(); -end; / 得到结果，递归输出路径if (head.state = target.first) path(index); break; x = head.blank / 3; y = head.blank % 3; for (i = 0; i < 4; +i) nx = x + xtrani; ny = y + ytrani; if (suit(nx, ny) a = head.blank; b = nx * 3 + ny; / 调换十进制表示整数对应两个数字位next = head.state + (head.state % pa + 1) / pa - (head.state % pb + 1) / pb) * pb + (head.state % pb + 1) / pb - (head.state % pa + 1) / pa) * pa; / 判断是否已经扩展过if (states.find(next) = states.end() states.insert(next); openend.pre = index; openend.blank = b; openend.state = next; openend.h = calculate(next, target.first); openend.g = head.g + 1; +end; push_heap(open, open + end, cmp(); if (end <= 0) puts(“No solution“); else printf(“Num of steps: %dn“, steps); printf(“Num of expanded: %dn“, index); printf(“Num of generated: %dn“, index + end); printf(“Time consumed: %dnn“, clock() - t2); states.clear(); steps = 0; printf(“Total time consumed: %dn“, clock() - t1); return 0; 系统中间及最终输出结果输入 3 1 2 4 0 5 6 7 8 输入 3 1 2 4 7 5 6 8 0 输入 3 7 2 8 1 5 4 6 0 输入 1 2 3 4 5 6 7 8 0