重排九宫格

重排九宫格问题一．问题描述在3*3的方格棋盘上放置分别标有数字1,2,3,4,5,6,7,8的8张牌，初始状态为s0，目标状态为sg，可使用的算符有空格左移，空格上移，空格右移和空格下移，即它们只允许把位于空格左，上，右，下边的牌移入空格。要求寻找从初始状态到目的状态的路径。二．算法描述（1）把初始节点S0放入OPEN表。（2）如果OPEN表为空，则问题无解，退出。（3）把OPEN表的第一个节点取出放入CLOSE表（记为节点n）。（4）考察节点n是否为目标节点。若是，则求得了问题的解，退出。（5）若节点n不可扩展，则转第2步。（6）扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。三.实验结果四.实验结果分析应用广度优先搜索可得到如上图所示的从初始状态到目标状态的路径。广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。但只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。五．源代码#includeiostreamusingnamespacestd;#includeclasses.hcharelement::ebegin[3][3]={{2,8,3},{1,0,4},{7,6,5}};charelement::dest[3][3]={{1,2,3},{8,0,4},{7,6,5}};doubleelement::k=1;//ifyouchangethekval,youmaygetdifferentresult.intmain(){listelementopen,close;//thesearetwolistthatholdsthetreenode.elementebegin(element::ebegin);mygraphG(&ebegin);//step1open.pushtop(&ebegin);//G.add(&ebegin);--theconstructionfunctiondiditverywell.while(1){//step2if(open.getnum()==0){coutThisquestionhasnosolution.endl;break;}/*if(close.getnum()362880){coutoutofbounderrorendl;break;}*///coutopen.getnum():close.getnum()endl;//step3element*n;close.pushend(n=open.pop());//step4if(element::reach(n)){coutsolutiongot:;G.drawtree(n);coutTotalsteps:n-layerendl;break;}//step5element*M[4];//extendthenodeM[0]=n-goup();M[1]=n-godown();M[2]=n-goleft();M[3]=n-goright();inti;for(i=0;i4;i++){if(M[i]==NULL)continue;if(!G.exist(M[i])){//aG.add(M[i],n);//M[i]-draw();if(!open.exist(M[i])&&!close.exist(M[i]))open.pushbyforder(M[i]);}else{//b&cG.changeparent(M[i],n);}}//7orderhasbeeendownininserting.//8whenwereachedhere,wewillgotothefront.}system(pause);return0;}classes.hstructpoint{intx;inty;point(intpx,intpy){x=px;y=py;}};classelement{public:charm[3][3];staticchardest[3][3];staticcharebegin[3][3];intlayer;staticdoublek;intf_val;element(chars[3][3],intl=0){layer=l+1;for(inti=0;i3;i++){for(intj=0;j3;j++){m[i][j]=s[i][j];}}this-f();}pointgetpos(){for(inti=0;i3;i++){for(intj=0;j3;j++){if(m[i][j]==0)returnpoint(i,j);}}system(echounable&pause);}intf(){intg=0;for(inti=0;i3;i++){for(intj=0;j3;j++){if(m[i][j]==dest[i][j]){g+=0;}else{g+=1;}}}f_val=(int)(layer+k*g);returnf_val;}element*goup(){pointp=this-getpos();if(p.x0){element*pnew=newelement(m,layer);pnew-m[p.x][p.y]=pnew-m[p.x-1][p.y];pnew-m[p.x-1][p.y]=0;returnpnew;}returnNULL;}element*godown(){pointp=this-getpos();if(p.x2){element*pnew=newelement(m,layer);pnew-m[p.x][p.y]=pnew-m[p.x+1][p.y];pnew-m[p.x+1][p.y]=0;returnpnew;}returnNULL;}element*goleft(){pointp=this-getpos();if(p.y0){element*pnew=newelement(m,layer);pnew-m[p.x][p.y]=pnew-m[p.x][p.y-1];pnew-m[p.x][p.y-1]=0;returnpnew;}returnNULL;}element*goright(){pointp=this-getpos();if(p.y2){element*pnew=newelement(m,layer);pnew-m[p.x][p.y]=pnew-m[p.x][p.y+1];pnew-m[p.x][p.y+1]=0;returnpnew;}returnNULL;}staticboolreach(element*p){for(inti=0;i3;i++){for(intj=0;j3;j++){if(p-m[i][j]!=dest[i][j])returnfalse;}}returntrue;}voiddraw(){coutendl;for(inti=0;i3;i++){cout'|';for(intj=0;j3;j++){cout(int)m[i][j]'';}cout'|'endl;}}boolequals(constelement*p){for(inti=0;i3;i++){for(intj=0;j3;j++){if(p-m[i][j]!=this-m[i][j])returnfalse;}}returntrue;}};templateclassTclasslist{structnode{T*ptr;node*next;};node*base;//stackbasepointernode*top;//stacktoppointerintm_num;public:list(){m_num=0;base=top=NULL;}boolpushtop(T*tp){if(base==NULL){base=top=(node*)malloc(sizeof(node));base-next=NULL;}else{node*tmp;tmp=(node*)malloc(sizeof(node));tmp-next=top;top=tmp;}top-ptr=tp;m_num++;returntrue;}boolpushbyforder(T*tp){if(base==NULL){base=top=(node*)malloc(sizeof(node));base-next=NULL;top-ptr=tp;}else{node*tmp,*find=top;tmp=(node*)malloc(sizeof(node));tmp-ptr=tp;while(find!=NULL){if(tmp-ptr-f_valfind-ptr-f_val){tmp-next=find-next;find-next=tmp;if(find==top){top=tmp;}break;}find=find-next;}if(find==NULL){base-next=tmp;tmp-next=NULL;base=tmp;}}m_num++;returntrue;}boolpushend(T*p){if(base==NULL){base=top=(node*)malloc(sizeof(node));base-next=NULL;}else{node*tmp;tmp=(node*)malloc(sizeof(node));base-next=tmp;tmp-next=NULL;base=tmp;}base-ptr=p;m_num++;returntrue;}T*pop(){if(m_num==0){returnNULL;}else{T*tmp;node*tobedel=top;tmp=top-ptr;top=top-next;if(top==NULL){base=NULL;}deletetobedel;m_num--;returntmp;}}intgetnum(){returnm_num;}T*operator[](intindex){node*tmp=top;while(index0)index--,(tmp=tmp-next);returntmp-ptr;}boolexist(T*p){node*tmp=top;while(NULL!=tmp){if(tmp-ptr-equals(p))returntrue;tmp=tmp-next;}returnfalse;}};classmygraph{//structgnode{element*ptr;gnode*father;//listgnodechild;thisitemisnolongerneeded--,bymydesign};gnoderoot;gnode**gnodelist;。intnnodelist;public:mygraph(element*p){root.ptr=p;root.father=NULL;gnodelist=(gnode**)malloc(sizeof(gnode*)*10240);gnodelist[0]=&root;nnodelist=1;}voidadd(element*pchild,element*pparent){boolfind=false;inti=0;for(i=0;innodelist;i++){if(pparent==gnodelist[i]-ptr){find=true;break;}}if(!find){system(echolistErr:No_parent_found&pause);}gnodelist[nnodelist]=(gnode*)malloc(sizeof(gnode));gnodelist[nnodeli