《用A星算法解决八数码问题(共12页).docx》由会员分享，可在线阅读，更多相关《用A星算法解决八数码问题(共12页).docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上A*算法解决八数码问题1 问题描述1.1什么是八数码问题八数码游戏包括一个33的棋盘，棋盘上摆放着8个数字的棋子，留下一个空位。与空位相邻的棋子可以滑动到空位中。游戏的目的是要达到一个特定的目标状态。标注的形式化如下：123456781.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 ) = 1 = Cost ( m, n ) 满足单调限制条件。2算法介绍2.1 A*算法的一般介绍A*（A-Star)是一种静态路网中求解最短路最有Astar算法在静态路网中的应用效的方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt(d
4、x-nx)*(dx-nx)+(dy-ny)*(dy-ny)；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。2.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设
5、置为X的父亲;更新OPEN表中的估价值; /取最小路径的估价值 if(X inCLOSE) if( X的估价值小于CLOSE表的估价值 )把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)保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径
6、；3算法实现3.1实验环境与问题规模对于数码问题，每个结点有个数字和一个空格，可以将空格看成，那么一共有个数字，位的int可以表示* 109 ，可以用一个整数表示一个结点对应的信息。计算一个整数中（即空格）的位置比较耗时间，用一个整数存储当前结点的位置，还要存储对应的 g , h 值以及该结点由哪个结点扩展来的信息。本实验用C+编写源程序，环境选用Visual Studio 2005。程序采用文本输入输出，输入文件为astar.in，A*算法输出文件为astar.out，可以用记事本打开。输入格式为一个测试用例由两个中间由一空行隔开的数码格局组成，输出为对应测试用例的走法路径及相关统计信息，程
7、序假定输入数据符合要求，未做检查。3.2数据结构3.2.1 open表的数据结构表示 考虑对open表的操作，每次需要得到所有待扩展结点中 f 值最小的那个结点，用堆进行实现，可以达到O ( log ( heapSize ) ) 时间复杂度。3.2.2 closed表的数据结构表示 closed表存储已扩展的结点间的扩展关系，主要用于输出路径。考虑结点扩展的操作，设待扩展的结点为m，由它扩展生成的结点为n1, n2, 。结点m扩展完成后被放到closed表中，放入后它在closed表中位置不发生变化，可以将n1, n2, 的前驱结点置为m在closed表中的位置，当n1, n2, .中有结点设
8、为n1被扩展放入closed表时，n1的前驱刚好已经存储好。下面说明closed表中任意一个结点都存储有它的前驱结点的信息，考虑closed表中任意一个结点，如果它是初始结点，它没有前驱结点，如果不是根结点，扩展该结点时它的前驱结点已经记录。从而在closed表中形成扩展关系的树状结构。因为只需要前驱结点的下标位置，可以用数组实现，每个结点记录整数表示的数码格局和它的前驱结点的下标，输出路径时，根据前驱结点形成到达根结点的链条，递归输出即可。3.2.3 解决结点重复扩展问题 对于一个结点有多种方式到达该结点，这样就可能多次将它加入open表中，而启发函数满足单调限制条件，后来达到该结点的路径不
9、再是更优的，可以不予考虑。扩展某结点时先看该结点是否已经扩展过，如果扩展过则略过。实现的可以线形遍历closed表，但效率不高时间复杂度为O ( closedSize)，考虑每个结点可以用一个整数标识，用二叉平衡查找树可以得到更好的时间复杂度O ( log (closedSize) ) ，程序中用基于红黑树思想的set实现。3.3 实验结果输入数据（0表示空格）步数扩展结点数生成结点数搜索用时(毫秒)3 1 2 4 0 5 6 7 8251103 1 2 4 7 5 6 8 04172803 7 2 8 1 5 4 6 0无解1 2 3 4 5 6 7 8 0227943120192266参考
10、文献王勋，凌云，费玉莲.2005.人工智能导论.北京：科学出版社广树建，王钰淇.2008.新编C/C+程序设计教程.广州：华南理工大学出版社王文杰，史忠植.2007.人工智能原理辅导与练习.北京：清华大学出版社出附录源代码及其注释源代码及测试数据/* 算法： A* 是否最优解：是 启发函数： 每一个数字位与目标中该数字位的距离，满足单调限制。说明：A*算法是启发式搜索算法，搜索时充分利用当前状态距目标距离远近的启发信息，选取当前未扩展结点中估价函数最小的进行扩展，生成结点数少，搜索空间较小，实现稍复杂， 备注： 程序未对输入数据进行检查*/#pragma warning(disable:478
11、6)#include #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 = ;const int MAXCHAR =
12、 100;char bufMAXCHARMAXCHAR;/open表item openMAXSTEPS;int steps = 0;/closed表，已查询状态只要知道该状态以及它由哪个结点扩展而来即可，用于输出路径/每次只需得到对应f值最小的待扩展结点，用堆实现提高效率pair closedMAXSTEPS;/读入，将8数码矩阵格局转换为整数表示bool read(pair &state) if (!gets(buf0) return false; if (!gets(buf1) return false; if (!gets(buf2) return false; assert(strle
13、n(buf0) = 5 & strlen(buf1) = 5 & strlen(buf2) = 5); state.first = 0; for (int i = 0, p = 1; i 3; +i) for (int j = 0; j 6; j += 2) if (bufij = ) state.second = i * 3 + j / 2; else state.first += p * (bufij - 0); p *= 10; return true;/*int calculate(int current, int target) int cnt = 0; for (int i = 0
14、; i 9; +i) if (current % 10 != 0)& (current % 10) != (target % 10) +cnt; current /= 10; target /= 10; return cnt;*/计算当前结点距目标的距离int calculate(int current, int target) int c9, t9; int i, cnt = 0; for (i = 0; i 9; +i) ccurrent % 10 = ttarget % 10 = i; current /= 10; target /= 10; for (i = 1; i b.g + b.
15、h; ;/将整数形式表示转换为矩阵表示输出void pr(int state) memset(buf, , sizeof(buf); for (int i = 0; i 3; +i) for (int j = 0; j = 0 & a = 0 & b 3);/递归输出搜索路径void path(int index) if (index = 0) pr(closedindex.first); puts(); return; path(closedindex.second); pr(closedindex.first); puts(); +steps;int main() unsigned int
16、 t1 = clock(); freopen(astar.in, r, stdin); freopen(astar2.out, w, stdout); setstates; 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
17、, , , , , ; 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(star
18、t.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 (he
19、ad.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.st
20、ate % 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 (en
21、d = 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专心-专注-专业