P1379 八数码难题题目描述在3 × 3 3\times 33×3的棋盘上摆有八个棋子每个棋子上标有1 11至8 88的某一数字。棋盘中留有一个空格空格用0 00来表示。空格周围的棋子可以移到空格中。要求解的问题是给出一种初始布局初始状态和目标布局为了使题目简单,设目标状态为123804765 123804765123804765找到一种最少步骤的移动方法实现从初始布局到目标布局的转变。输入格式输入初始状态一行九个数字空格用0 00表示。输出格式只有一行该行只有一个数字表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。输入输出样例 #1输入 #1283104765输出 #14说明/提示样例解释图中展示了样例当中从初始状态到目标状态的一种方案共需要4 44步。并且可以证明不存在更优的策略。代码#includebits/stdc.husingnamespacestd;structcoor{intx,y;};//点的坐标structnode{string ss,//起始布局se123804765;//目标布局coor poss[9],//起始布局各数字的位置pose[9];//目标布局intid,//哈希值用于标记dis,//当下布局到目标布局的曼哈顿距离纵横差step,//当前已经移动的步数x,y;//当前布局0(空格)所在坐标node(){step0;se123804765;for(inti0;i9;i)pose[se[i]-0].xi/3,pose[se[i]-0].yi%3;//计算目标布局各数字坐标}voidset(string s){//初始化赋予初始布局sss;for(inti0;i9;i){poss[ss[i]-0].xi/3,poss[ss[i]-0].yi%3;//明确起始布局各数字坐标if(ss[i]0)xi/3,yi%3;//0(空格)所在坐标}m_id();m_dis();//计算哈希值和曼哈顿距离和}voidmove(intsx,intsy,intex,intey){//当前数字移到空格位置poss[ss[sx*3sy]-0].xex,poss[ss[sx*3sy]-0].yey,//当前数字的坐标变成空格的坐标poss[0].xsx,poss[0].ysy,//空格移到对应数字位置swap(ss[sx*3sy],ss[ex*3ey]);//对调字符串中0和当前数字的位置xsx,ysy;//空格的新位置m_id();m_dis();//step;}voidm_id(){//计算哈希值字符串转整数id0;for(inti0;i9;i)idid*10ss[i]-0;}voidm_dis(){//计算各数字到目标布局的曼哈顿距离和dis0;for(inti0;i9;i)disabs(poss[i].x-pose[i].x)abs(poss[i].y-pose[i].y);}booloperator(constnode b)const{returnstepdisb.stepb.dis;}//大顶堆默认现需要逆序所以相反成//a*算法的核心相对于宽搜、dijstra算法的区别//宽搜没有优先队列//dijkstra的优先队列只看已走了多少}sta1,sta2;//移动前后布局string s;priority_queuenodeq;//优先队列默认大顶堆现在是逆序小顶堆每次找最小成本状态unordered_setintvis;//用哈希值记住已遍历布局intsx,sy,ex,ey,d[4][2]{{0,-1},{-1,0},{0,1},{1,0}};intmain(){//freopen(data.cpp,r,stdin);cins;sta1.set(s);q.push(sta1);vis.insert(sta1.id);while(!q.empty()){sta1q.top();q.pop();if(sta1.dis0){coutsta1.step;return0;}sxsta1.x,systa1.y;for(inti0;i4;i){exsxd[i][0],eysyd[i][1];if(ex0||ex2||ey0||ey2)continue;sta2sta1;sta2.move(ex,ey,sx,sy);if(vis.count(sta2.id))continue;vis.insert(sta2.id);q.push(sta2);}}cout-1;return0;}搜索算法横向比较1968 年Hart、Nilsson、Raphael 三个人提出了a算法叫一类带启发式的最佳优先搜索算法。叫Algorithm A→ 就是「A 类算法」3星4星启发式搜索算法。几种搜索都是宽搜DFS标记遍历访问队列一直扩散搜索范围。走到哪算哪Dijkstra是用了优先队列优先选择已走步数最少的如果节点权值一样就退化成DFS。走最少的路但管不了方向。A的优先队列优先选择已走步数目标预估距离有方向。最最少的路而且直奔方向。