用A星算法解决八数码问题
12页1、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 到目标节点
2、最佳路径的估计代价。保证找到最短路径(最优解)的条件,关键在于估价函数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 stat
3、e; 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
《用A星算法解决八数码问题》由会员飞***分享,可在线阅读,更多相关《用A星算法解决八数码问题》请在金锄头文库上搜索。
人教版一年级下册数学第二单元20以内的退位减法测试卷精品【考试直接用】
人教版一年级下册数学第二单元20以内的退位减法测试卷(实用)word版
人教版一年级下册数学第二单元20以内的退位减法测试卷及答案(夺冠)
人教版一年级下册数学第二单元20以内的退位减法测试卷(典型题)
人教版一年级下册数学第二单元20以内的退位减法测试卷精品(a卷)
人教版一年级下册数学第二单元20以内的退位减法测试卷及答案【精品】
部编版二年级上册道德与法治期中测试卷 (考试直接用)
部编版二年级上册道德与法治期中测试卷 带答案(培优)
部编版二年级上册道德与法治期中测试卷 含答案(精练)
部编版二年级上册道德与法治期中测试卷 及答案【各地真题】
部编版二年级上册道德与法治期中测试卷 及完整答案【名校卷 】
部编版二年级上册道德与法治期中测试卷 【考点精练】
部编版三年级上册道德与法治期末测试卷 (重点)
部编版三年级上册道德与法治期末测试卷 (模拟题)word版
部编版三年级上册道德与法治期末测试卷 附答案(预热题)
部编版三年级上册道德与法治期末测试卷 附参考答案(b卷 )
部编版三年级上册道德与法治期末测试卷 答案下载
部编版三年级上册道德与法治期末测试卷 含答案【夺分金卷 】
部编版三年级上册道德与法治期末测试卷 含完整答案【网校专用】
部编版三年级上册道德与法治期末测试卷 及答案(最新)
2024-03-21 1页
2024-03-21 1页
2024-03-15 2页
2024-03-01 2页
2024-03-01 2页
2024-02-28 118页
2024-02-28 152页
2024-02-28 87页
2024-02-28 92页
2024-02-28 96页