野人过河宽度优先算法

#includevector#includealgorithm#includestdio.h#includestdlib.husingnamespacestd;#defineMAXM3#defineMAXC3typedefstructNode{intM,C,B;intparent;//记录父节点在tree中的下标}Node;vectorNodeopen;vectorNodeclose;vectorNodetree;Nodeboat[5]={{0,1,1},{0,2,1},{1,1,1},{1,0,1},{2,0,1}};voidshow_open(){//显示open表vectorNode::iteratorite;ite=open.end()-1;for(;ite=open.begin();ite--){printf((%d,%d,%d)\n,(*ite).M,(*ite).C,(*ite).B);if(ite==open.begin())break;}}voidshow_close(){//显示close表vectorNode::iteratorite;ite=close.begin();for(;iteclose.end();ite++){printf((%d,%d,%d)\n,(*ite).M,(*ite).C,(*ite).B);}}booloperator==(Nodea,Nodeb){return(a.M==b.M&&a.C==b.C&&a.B==b.B);}boolexit_open(Nodep){//判断节点是否存在open表中if(find(open.begin(),open.end(),p)==open.end())returnfalse;elsereturntrue;}boolexit_close(Nodep){//判断节点是否存在close表中if(find(close.begin(),close.end(),p)==close.end())returnfalse;elsereturntrue;}voidadd_open(Nodep){//open表添加//open.insert()open.push_back(p);}voidadd_close(Nodep){//close表添加close.push_back(p);}voidout_open(){//open表删除//open.pop_front();open.erase(open.begin());}booljudge_Node(Nodep){//判断状态p是否合法if(p.MMAXM||p.CMAXC||p.M0||p.C0)//不在范围内。不合法returnfalse;/*if(((p.M=p.C)&&(MAXM-p.M=MAXC-p.C))||(p.M==MAXM)||(p.M==0))returntrue;returnfalse;*/elseif(p.M!=0&&p.Mp.C)//左岸传教士人数不为0并且小于野人数returnfalse;elseif(MAXM-p.M!=0&&MAXM-p.MMAXC-p.C)//右岸传教士人数不为0就算了居然比野人数少！！当然不行returnfalse;elsereturntrue;}voidexpand(Nodep){//对节点p进行扩展Nodeq;printf(------------------------------------------------------------------------------------\n);printf(\t\t\t对结点:);printf((%d%d%d)进行扩展\n,p.M,p.C,p.B);for(inti=0;i5;i++){if(p.B==1){//p船在左岸q.M=p.M-boat[i].M;q.C=p.C-boat[i].C;q.B=p.B-boat[i].B;}else{//p船在右岸q.M=p.M+boat[i].M;q.C=p.C+boat[i].C;q.B=p.B+boat[i].B;}if(judge_Node(q)&&!exit_open(q)&&!exit_close(q)){//避免死循环已经扩展过的结点不再扩展intpos=find(tree.begin(),tree.end(),p)-tree.begin();q.parent=pos;printf(扩展出新的子结点:);printf((%d,%d,%d)\n,q.M,q.C,q.B);add_open(q);tree.push_back(q);}else{printf(\t------节点(%d,%d,%d)不满足条件，扩展失败------\n,q.M,q.C,q.B);}}printf(\t\t=======================================================\n);add_close(p);printf(\t\t\t\t******open表状态******\n);show_open();printf(\t\t\t\t******close表状态******\n);show_close();printf(------------------------------------------------------------------------------------\n);}booldestination(Nodep){//判断p是否为目标节点if(p.M==0&&p.C==0&&p.B==0)returntrue;elsereturnfalse;}Nodesolve(){Nodep{3,3,1};open.push_back(p);//open.push_front(p);tree.push_back(p);charc;Nodex;while(open.size()!=0){x=open.front();//从open表中取出一个进行扩展if(destination(x))returnx;//如果是目标状态则结束out_open();//从open中删除expand(x);//扩展该结点//getchar();}//returnNULL;}voidpath(Nodep){vectorNodetemp;while(p.parent!=0){temp.push_back(p);p=tree[p.parent];}temp.push_back(p);vectorNode::iteratorite1=temp.end()-1;for(;ite1=temp.begin();ite1--){printf((%d,%d,%d)\n,(*ite1).M,(*ite1).C,(*ite1).B);if(ite1==temp.begin())break;}}intmain(){Nodegoal=solve();printf(求得传教士与野人过河问题状态空间的一个解为：\n);printf((3,3,1)\n);path(goal);}