宽度优先搜索解决八数码问题.doc

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

1、解八数码问题：任意输入两个九宫格作为初始状态和目标状态，用宽度优先搜索求解。#include#include#include#include#includeusingnamespacestd;classNineNode{public:intnine[3][3];//九宫格intparent;//父节点，根节点的父节点为-1inti;//空白所在行intj;//空白所在列stringstep;//从上一节点移动至此节点所需操作};boolhavesolution(Nin

2、eNodestart,NineNodeend);boolmatch(NineNodenode1,NineNodenode2);boolishave(dequeopenQueue,vectorclosedList,NineNodenode);intmain(){inti,j;dequeopenQueue;//open队列vectorclosedList;//closed列表stackmovepath;//移动步骤栈NineNodeinitilNode,l

3、astNode;//初始节点和目标节点cout<<"请输入初始节点状态:";/*输入初始节点状态开始*/for(i=0;i<3;i++)for(j=0;j<3;j++){cin>>initilNode.nine[i][j];if(0==initilNode.nine[i][j]){initilNode.i=i;initilNode.j=j;}}initilNode.parent=-1;/*输入初始节点状态结束*/cout<<"请输入目标节点状态:";/*输入目标节点状态开始*/for(i=0;i<3;i++)for(j=0;j<3;j++){ci

4、n>>lastNode.nine[i][j];if(0==lastNode.nine[i][j]){lastNode.i=i;lastNode.j=j;}}lastNode.parent=-1;/*输入目标节点状态结束*/if(havesolution(initilNode,lastNode)){intparent=-1;//parent指示父节点下标boolflag=false;//找到标志openQueue.push_back(initilNode);while((!openQueue.empty())&&(!flag)){NineNodet

5、emp;temp=openQueue.front();openQueue.pop_front();closedList.push_back(temp);parent=closedList.size()-1;if(match(temp,lastNode)){flag=true;break;}if(temp.j>0)//向左移动{NineNodeleft=temp;left.nine[temp.i][temp.j]=left.nine[temp.i][temp.j-1];left.nine[temp.i][temp.j-1]=0;left.paren

6、t=parent;left.i=temp.i;left.j=temp.j-1;left.step="向左移动";if(!ishave(openQueue,closedList,left))openQueue.push_back(left);}if(temp.i>0)//向上移动{NineNodeup=temp;up.nine[temp.i][temp.j]=up.nine[temp.i-1][temp.j];up.nine[temp.i-1][temp.j]=0;up.parent=parent;up.i=temp.i-1;up.j=temp.j

7、;up.step="向上移动";if(!ishave(openQueue,closedList,up))openQueue.push_back(up);}if(temp.j<2)//向右移动{NineNoderight=temp;right.nine[temp.i][temp.j]=right.nine[temp.i][temp.j+1];right.nine[temp.i][temp.j+1]=0;right.parent=parent;right.i=temp.i;right.j=temp.j+1;right.step="向右移动";if(!

8、ishave(openQueue,closedList,right))openQueue.push_back(right);}if(te