《用A星算法解决八数码问题》由会员分享，可在线阅读，更多相关《用A星算法解决八数码问题（12页珍藏版）》请在金锄头文库上搜索。
1、A*算法解决八数码问题1 问题描述1.1 什么是八数码问题 八数码游戏包括一个3 3 的棋盘，棋盘上摆放着8 个数字的棋子，留下一个空位。与空位相邻的棋子可以滑动到空位中。游戏的目的是要达到一个特定的目标状态。标注的形式化如下：1 2 3 4 5 6 7 8 1.2 问题的搜索形式描述 状态 ：状态描述了8 个棋子和空位在棋盘的9 个方格上的分布。初始状态 ：任何状态都可以被指定为初始状态。操作符 ：用来产生4 个行动（上下左右移动）。目标测试 ：用来检测状态是否能匹配上图的目标布局。路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。现在任意给定一个初始状态，要求找到一种搜索策
2、略，用尽可能少的步数得到上图的目标状态。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)实际值 , 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。搜索中利用启发式信息，对当前未
3、扩展结点根据设定的估价函数值选取离目标最近的结点进行扩展，从而缩小搜索空间，更快的得到最优解，提高效率。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 数码
4、格局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表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径/
5、 每次只需得到对应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
6、= 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) unsign
7、ed 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 值最小元素放入cl
8、osed表，并对该结点进行扩展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) p
9、ath(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
10、.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“)
11、; 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
