AStar算法解决八数码问题(8页).doc

《AStar算法解决八数码问题(8页).doc》由会员分享，可在线阅读，更多相关《AStar算法解决八数码问题(8页).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-AStar算法解决八数码问题一、实验目的：修改A*算法，使之能解决N*N矩阵八数码问题问题描述：八数码难题：在33方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0可自己随机设定，使用的操作有:空格上移，空格左移，空格右移，空格下移。二、 算法描述：1. 状态描述 八数码的任何一种摆法就是一个状态，所有摆法即为状态集S，他们构成了一个状态空间，其大小为9包括8个数码和一个空格，每个数码就是一个分离的独立的子空间，其所在位置为x：i/3，y：i%3.相应的操作算子就是数码的移动即：将空格向上移UP、将空格向下移DOWN、将空格向左移LEFT、将空格向右移RIGH

2、T，经过一些操作算子后达到目标状态。2. 启发函数设计启发函数为现在的状态中各位置与目标状态各位置数码值不同的个数，例如：现在状态：w=123456780,目标状态为：t=123456708，则h（n）=2.3. 规则的判断条件把未扩展的状态存入open表，排序后取出优先状态扩展搜索，将扩展后的存入closed表，循环执行直到扩展出目标状态。4. 算法流程图5. 核心代码操作算子：int solve()/搜索过程P cur;P p;while(!open.empty()cur=open.top(); /open表open.pop();if(cur.s=t) return cur.id;/达到目

3、标状态，返回当前节点的idint x,y;int ops=0;while(cur.sops!=0) ops+;x=ops/N,y=ops%N; /空格所在位置int r=cur.id;if(x0) /空格向上移p.s=cur.s;swap(p.sops,p.sops-3);if(!mpp.s)p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack+top=p.s;fathertop=r;mpp.s=1;if(x0) /空格向左移p.s=cur.s;swap(p.sops,p.sops-1);if(!mpp.s)p.d=cur.d+1,p.

4、w=calw(p.s),p.id=top+1;open.push(p);stack+top=p.s;fathertop=r;mpp.s=1;if(yN-1) /空格向右移p.s=cur.s;swap(p.sops,p.sops+1);if(!mpp.s)p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack+top=p.s;fathertop=r;mpp.s=1;return -1;/搜索失败主函数：int main()coutN;couttt;for(int k=1;k=tt;k+)coutCase k:n;int i,j;char a

5、;coutt;p.s=;cout请输入初始状态:n;for(i=0;iN;i+)for(j=0;ja; /输入08数码p.s+=a;p.d=0,p.w=calw(p.s),p.id=0;father0=-1;mpp.s=1;stack0=p.s;open.push(p);/往open表中加入初始状态节点int id=solve();/调用搜索过程if(id=-1)cout=0)/把stack中存的节点按次序放入到record中record+c=stackid;id=fatherid;cout原图：endl;print(c); /输出初始节点cout=0;i-)coutStep c-i:n;/输

6、出当前搜索步骤print(i);/输出当前搜索的节点cout移动结束！n;mp.clear();while(!open.empty() open.pop();top=0;coutendl;system(pausen);return 0;三、实验结果： 四、实验心得：只是做了简单修改，只能解决些简单的问题，过于复杂的还不能实现，不过还是体会到了A*算法的厉害，也见识到了人工智能的神奇，会继续努力学习。教师评价 优良 中及格不及格教师签名日期-第 - 9 - 页江南大学物联网工程学院实验报告课程名称 人工智能 实验名称 A*算法解决8数码问题 实验日期 2018.3.20 班级 计科1501 姓名 周启航 学号 1030415127