AStar算法解决八数码问题

江南大学物联网工程学院实验报告课程名称人工智能实验名称A*算法解决8数码问题实验日期2018.3.20班级计科1501姓名周启航学号1030415127一、实验目的：修改A*算法，使之能解决N*N矩阵八数码问题问题描述：八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0可自己随机设定，使用的操作有:空格上移，空格左移，空格右移，空格下移。二、算法描述：1.状态描述八数码的任何一种摆法就是一个状态，所有摆法即为状态集S，他们构成了一个状态空间，其大小为9包括8个数码和一个空格，每个数码就是一个分离的独立的子空间，其所在位置为x：i/3，y：i%3.相应的操作算子就是数码的移动即：将空格向上移UP、将空格向下移DOWN、将空格向左移LEFT、将空格向右移RIGHT，经过一些操作算子后达到目标状态。2.启发函数设计启发函数为现在的状态中各位置与目标状态各位置数码值不同的个数，例如：现在状态：w=123456780,目标状态为：t=123456708，则h（n）=2.3.规则的判断条件把未扩展的状态存入open表，排序后取出优先状态扩展搜索，将扩展后的存入closed表，循环执行直到扩展出目标状态。4.算法流程图5.核心代码操作算子：intsolve()//搜索过程{Pcur;Pp;while(!open.empty()){cur=open.top();//open表open.pop();if(cur.s==t)returncur.id;//达到目标状态，返回当前节点的idintx,y;intops=0;while(cur.s[ops]!='0')ops++;x=ops/N,y=ops%N;//空格所在位置intr=cur.id;if(x0){//空格向上移p.s=cur.s;swap(p.s[ops],p.s[ops-3]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}if(xN-1){//空格向下移p.s=cur.s;swap(p.s[ops],p.s[ops+3]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}if(y0){//空格向左移p.s=cur.s;swap(p.s[ops],p.s[ops-1]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}if(yN-1){//空格向右移p.s=cur.s;swap(p.s[ops],p.s[ops+1]);if(!mp[p.s]){p.d=cur.d+1,p.w=calw(p.s),p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=1;}}}return-1;//搜索失败}主函数：intmain(){cout请输入棋盘大小N*N\nN:;cinN;cout请输入测试的组数:\n;inttt;//测试的组数cintt;for(intk=1;k=tt;k++){coutCasek:\n;inti,j;chara;cout请输入目的状态：\n;cint;p.s=;cout请输入初始状态:\n;for(i=0;iN;i++){for(j=0;jN;j++){cina;//输入0～8数码p.s+=a;}}p.d=0,p.w=calw(p.s),p.id=0;father[0]=-1;mp[p.s]=1;stack[0]=p.s;open.push(p);//往open表中加入初始状态节点intid=solve();//调用搜索过程if(id==-1){cout无解！\n;}else{intc=-1;while(id=0){//把stack中存的节点按次序放入到record中record[++c]=stack[id];id=father[id];}cout原图：endl;print(c);//输出初始节点cout移动过程:\n\n;for(i=c-1;i=0;i--){coutStepc-i:\n;//输出当前搜索步骤print(i);//输出当前搜索的节点}cout移动结束！\n;}mp.clear();while(!open.empty())open.pop();top=0;coutendl;}system(pause\n);return0;}三、实验结果：四、实验心得：只是做了简单修改，只能解决些简单的问题，过于复杂的还不能实现，不过还是体会到了A*算法的厉害，也见识到了人工智能的神奇，会继续努力学习。教师评价优良中及格不及格教师签名日期