AStar算法解决八数码问题

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

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

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

3、(!open.empty()){cur=open.top();//open表open.popO;if(cur.s==t)returncur.id;//达到目标状态，返回当前节点的idintx,y;intops=0;while(cur.s[opsj!=,0,)ops++;x=ops/N,y二ops%N;〃空格所在位置intr=cur.id;if(x>0){〃空格向上移p.s=cur.s;swap(p.s

4、ops社p.s

5、ops-3]);if(!mp[p.s]){p.d=cur.d+1、p.w二calw(p.s),p・id二top+1;open.push(p);sta

6、ck[++top]=p.s;father[top]=r;mp[p.s]=l;))if(x0){〃空格向左移p.s=cur.s;swap(p.s[ops],p.s[ops-l]);if(!mp[p.s]){p.d=cu匚d+1,p.w=calw(p.s),

7、p.id=top+1;open.push(p);stack[++top]=p.s;father[top]=r;mp[p.s]=l;)}if(y

8、t«H请输入测试的组数:“；inttt;〃测试的组数cin»tt;for(intk=l;k<=tt;k++){cout«"Case'^«k«":,^;inti,j；chara;coutvv”请输入目的状态：“；cin»t;p.s二"”；cout«H请输入初始状态:“；for(i=0;i

9、状态节点intid=solve();//调用搜索过程if(id==-l){cout«"无解！";}else{intc二1;while(id>=0){〃把stack中存的节点按次序放入到record中record[++c]=stack[id];id=father[id];}cout«H原图："«endl;print(c);〃输出初始节点cout«H移动过程:M;for(i=c-1;i>=0;i—){cout«HStep,,«c-i«,,:u;//输出当前搜索步骤prinl(i);//输出当前搜索的节点}cout«H移动结束!“；}mp.clear

10、();wh