AStar算法解决八数码问题.doc

《AStar算法解决八数码问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、江南大学物联网工程学院实验报告课程名称人工智能实验名称A*算法解决8数码问题实验日期2018.3.20班级计科1501姓名周启航学号一、实验目的：修改A*算法，使之能解决N*N矩阵八数码问题问题描述：八数码难题：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0可自己随机设定，使用的操作有:空格上移，空格左移，空格右移，空格下移。二、算法描述：1.状态描述八数码的任何一种摆法就是一个状态，所有摆法即为状态集S，他们构成了一个状态空间，其大小为9包括8个数码和一个空格，每个数码就是一个

2、分离的独立的子空间，其所在位置为x：i/3，y：i%3.相应的操作算子就是数码的移动即：将空格向上移UP、将空格向下移DOWN、将空格向左移LEFT、将空格向右移RIGHT，经过一些操作算子后达到目标状态。2.启发函数设计启发函数为现在的状态中各位置与目标状态各位置数码值不同的个数，例如：现在状态：w=,目标状态为：t=，则h（n）=2.3.规则的判断条件把未扩展的状态存入open表，排序后取出优先状态扩展搜索，将扩展后的存入closed表，循环执行直到扩展出目标状态。4.算法流程图1.核心代码操作算子：intsolve(

3、)//搜索过程{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(x>0){//空格向上移p.s=cur.s;swap(p.s[ops],p.s[ops-3]);if(!mp[p.s]){p.d=cur

4、.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(x0){//空格向左移p.s=

5、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(y

6、p]=p.s;father[top]=r;mp[p.s]=1;}}}return-1;//搜索失败}主函数：intmain(){cout<<"请输入棋盘大小N*NN:";cin>>N;cout<<"请输入测试的组数:";inttt;//测试的组数cin>>tt;for(intk=1;k<=tt;k++){cout<<"Case"<>t;p.s="";cout<<"请输入初始状态:";for(i=0;i

7、r(j=0;j>a;//输入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<<"无解！";}else{intc=-1;while(id>=0){//把stack中存的节点按次序放入到record中record[++c]=stack[id];id=father

8、[id];}cout<<"原图："<=0;i--){cout<<"Step"<