main.cpp

八数码三种方法：广度

#include <iostream>
#include <vector>     
#include <list>     //STL  容器
#include <set>      //STL  容器 

using namespace std;

struct Node{
	char item[3][3];
	int x,y;	//保存空格坐标
	int parent; //父节点下标
	
	int depth;//用于深度优先  对应节点深度
	int gn,hn,fn; //用于A算法  对应 g(n)  h(n)  f(n)
};


Node start;		//起始状态
Node object;	//目标状态
int MaxDepth=10;   //深度优先的深度

void BFS(const Node& start,const Node& object);   // 宽度优先
void DFS(const Node& start,const Node& object);    //深度优先
void A(const Node& start,const Node& object);      //A算法搜索
void Print(const Node& node) ;       // 显示
int h(const Node& node,const Node& object);     //启发函数，以错放的棋子数来计算启发函数

enum {U,R,D,L};

void main()
{
	//初始状态初始化
	start.item[0][0]='2';start.item[0][1]='8';start.item[0][2]='3';
	start.item[1][0]='1';start.item[1][1]='6';start.item[1][2]='4';
	start.item[2][0]='7';start.item[2][1]='0';start.item[2][2]='5';
	start.x=2;start.y=1;      //  对应 0 所在的位置  即空格所在的位置
	start.parent=-1;
	//目标状态初始化
	object.item[0][0]='1';object.item[0][1]='2';object.item[0][2]='3';
	object.item[1][0]='8';object.item[1][1]='0';object.item[1][2]='4';
	object.item[2][0]='7';object.item[2][1]='6';object.item[2][2]='5';
	object.x=1;object.y=1;      //  对应 0 所在的位置
	object.parent=-1;

	object.fn=0;

	start.gn=0;
	start.hn=h(start,object);       
	start.fn=start.gn+start.hn;
	
	cout<<"起始状态:"<<endl;
	Print(start);
	cout<<endl;
	cout<<"目标状态:"<<endl; 
	Print(object);
	cout<<endl;
    
	int choose;
	cout<<"选择搜索方法：    "<<endl;
    cout<<"1.宽度优先搜索   2.深度优先搜索    3.A算法  "<<endl;
	cin>>choose;
	if(choose==1)
		BFS(start,object);
	else if(choose==2) 
		DFS(start,object);
	else if(choose==3)
		A(start,object);
	else
		cout<<"你的选择无效，请重新输入!"<<endl;
}




int h(const Node& node,const Node& object)          //以错放的棋子数来计算启发函数
{
	int cost=0;
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			if(node.item[i][j]!=object.item[i][j]) cost++;
			return cost;
}



bool Issame(const Node& node1,const Node& node2)	//判断两局面是否相等
{
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			if(node1.item[i][j]!=node2.item[i][j]) return false;
			return true;
}



void Print(const Node& node)  //输出该状态
{
	for(int i=0;i<3;++i)
	{
		for(int j=0;j<3;++j)
			cout<<node.item[i][j]<<"	  ";
		cout<<endl;
	}
}

Node Move(Node node,int movement)  //将当前状态移动生成新状态返回。 movement 取值为: UP,RIGHT,DOWN,LEFT，表示将空格上，右，下，左移动
{
	int x=node.x;
	int y=node.y;
	
	if(movement==U)
	{
		if(x<=0)
		{
			node.x=-1; //返回错误值
			return node;
		}
		else
		{
			char ch=node.item[x][y];
			node.item[x][y]=node.item[x-1][y];
			node.item[x-1][y]=ch;
			node.x=x-1;
			return node;
		}
	}
	else if(movement==R)
	{
		if(y>=2)
		{
			node.x=-1;    //返回错误值
			return node;
		}
		else
		{
			char ch=node.item[x][y];
			node.item[x][y]=node.item[x][y+1];
			node.item[x][y+1]=ch;
			node.y=y+1;
			return node;
		}
	}
	else if(movement==D)
	{
		if(x>=2)
		{
			node.x=-1;      //返回错误值
			return node;
		}
		else
		{
			char ch=node.item[x][y];
			node.item[x][y]=node.item[x+1][y];
			node.item[x+1][y]=ch;
			node.x=x+1;
			return node;
		}
	}
	else if(movement==L)
	{
		if(y<=0)
		{
			node.x=-1;         //返回错误值
			return node;
		}
		else
		{
			char ch=node.item[x][y];
			node.item[x][y]=node.item[x][y-1];
			node.item[x][y-1]=ch;
			node.y=y-1;
			return node;
		}
		
	}
	else 
	{
		node.x=-1;         //返回错误值
		return node;
	}
	
}

bool exist(const list<Node>& open,const vector<Node>& closed,const Node& node) //在open，closed表中查询是否已经存在node状态,用于宽度和广度搜索
{
	for(list<Node>::const_iterator it=open.begin();it!=open.end();++it)         // 遍历器
	{	
		if(Issame((*it),node)) return 1;		
	}
	
	for(vector<Node>::const_iterator it1=closed.begin();it1!=closed.end();++it1)           // 遍历器
	{
		if(Issame((*it1),node)) return 1;			
	}
	return 0;
}

int exist1(set<Node>& open,vector<Node>& closed,const Node& node) //在open，closed表中查询是否已经存在node状态，用于A算法搜索
{
	for(set<Node>::iterator it=open.begin();it!=open.end();++it)
	{	
		if(Issame((*it),node)) 
		{
			if(node.fn<(*it).fn) //当前的f值小于已有的f值
			{
				(*it).gn=node.gn;
				(*it).hn=node.hn;
				(*it).fn=node.fn;
				(*it).parent=node.parent;				
			}
			return 1;		
		}
	}
	for(vector<Node>::iterator it1=closed.begin();it1!=closed.end();++it1)
	{
		if(Issame((*it1),node)) 
		{
			if(node.fn<(*it1).fn)  //当前的f值小于已有的f值  
			{
				(*it1).gn=node.gn;
				(*it1).hn=node.hn;
				(*it1).fn=node.fn;
				(*it1).parent=node.parent;
				
				open.insert((*it1)); //移回open表
			}
			return 2;			
		}
	}

	open.insert(node);
	return 0;
}

void BFS(const Node& start,const Node& object)   //宽度优先搜索
{
	
	list<Node> open;
	vector<Node> closed;
	vector<int> result;
	
	open.push_back(start);       //open表中加入初始状态
	
	while(!open.empty())
	{
		Node out=open.front();      //得到open表的第一个元素
		open.pop_front();            //从open表中弹出第一个元素
		
		if(Issame(out,object))       // 判断是否为目标状态
		{
			int i=out.parent;
			while(i!=-1)
			{
				result.push_back(i);
				i=closed[i].parent;
			}
			break;
		}
		
		closed.push_back(out);            //放入closed表
		
		Node Upnode=Move(out,U);          //上移
		if(Upnode.x!=-1)       //没有越界
		{
			if(!exist(open,closed,Upnode))
			{
				Upnode.parent=closed.size()-1;
				open.push_back(Upnode);
			}
		}
		
		Node Rightnode=Move(out,R);       //右移
		if(Rightnode.x!=-1)        //没有越界
			
		{
			if(!exist(open,closed,Rightnode))
			{
				Rightnode.parent=closed.size()-1;
				open.push_back(Rightnode);
			}
		}
		
		Node Downnode=Move(out,D);         //下移
		if(Downnode.x!=-1)        //没有越界   
		{
			if(!exist(open,closed,Downnode))
			{
				Downnode.parent=closed.size()-1;
				open.push_back(Downnode);
			}
		}
		
		Node Leftnode=Move(out,L);        // 左移
		if(Leftnode.x!=-1)           //没有越界
		{
			if(!exist(open,closed,Leftnode))
			{
				Leftnode.parent=closed.size()-1;
				open.push_back(Leftnode);
			}
		}
		
	}
	
	cout<<"宽度优先搜索:"<<endl;
	for(int i=result.size()-1;i>=0;--i)
	{
		Print(closed[result[i]]);
		cout<<endl;
	}
	
	Print(object);
	cout<<"宽度优先搜索结束!"<<endl;
}

void DFS(const Node& start,const Node& object)         //深度优先搜索
{
	
	list<Node> open;	//open表
	vector<Node> closed; //closed表
	vector<int> result;  
	
	open.push_back(start);
	
	while(!open.empty())
	{
		Node out=open.back();//取最先进来的结点
		open.pop_back();
		if(Issame(out,object)) 
		{
			int i=out.parent;
			while(i!=-1)
			{
				result.push_back(i);
				i=closed[i].parent;
			}
			break;
		}
		if(out.depth>=MaxDepth) continue;
		closed.push_back(out);
		Node outUp=Move(out,U);
		if(outUp.x!=-1)
		{
			if(!exist(open,closed,outUp))
			{
				outUp.parent=closed.size()-1;
				outUp.depth=out.depth+1;
				open.push_back(outUp);
			}
		}
		Node outRight=Move(out,R);
		if(outRight.x!=-1)
		{
			if(!exist(open,closed,outRight))  
			{
				outRight.parent=closed.size()-1;
				outRight.depth=out.depth+1;
				open.push_back(outRight);
			}
		}
		Node outDown=Move(out,D);
		if(outRight.x!=-1)
		{
			if(!exist(open,closed,outDown))
			{
				outDown.parent=closed.size()-1;
				outDown.depth=out.depth+1;
				open.push_back(outDown);
			}
		}
		Node outLeft=Move(out,L);
		if(outLeft.x!=-1)
		{
			if(!exist(open,closed,outLeft))
			{
				outLeft.parent=closed.size()-1;
				outLeft.depth=out.depth+1;
				open.push_back(outLeft);
			}
		}
		
	}
	
	cout<<"最大深度为"<<MaxDepth<<"的深度优先搜索:"<<endl;
	if(result.size()>0)
	{
		for(int i=result.size()-1;i>=0;--i)
		{
			Print(closed[result[i]]);
			cout<<endl;
		}
		
		Print(object);
		cout<<"深度优先搜索结束!"<<endl<<endl;
	}
	else cout<<"最大深度为"<<MaxDepth<<"的深度优先搜索无解!"<<endl;;
	
}




void A(const Node& start,const Node& object)    //A算法搜索
{
	set<Node> open;        
	vector<Node> closed;
	vector<int> result;
	open.insert(start);


	while ( !open.empty() )
	{
		Node out=(*open.begin());

		if(Issame(out,object))	//找到目标状态
		{
			int i=out.parent;
			while(i!=-1)
			{
				result.push_back(i);
				i=closed[i].parent;
			}
			break;
		}

		open.erase(open.begin());  //第一个元素除去
		closed.push_back(out);     //加入到closed表

		for(int i=0;i<4;++i)
		{
			Node outm=Move(out,i);
			if(outm.x!=-1) //能这样扩展
			{
				outm.parent=closed.size()-1;   //记录父指针
				outm.gn=out.gn+1;				//计算g(n)
				outm.hn=h(outm,object);
				outm.fn=outm.gn+outm.hn;		//计算f(n)
				exist1(open,closed,outm);		
			}
		}
		
	}
	cout<<"A算法搜索:"<<endl;
	for(int i=result.size()-1;i>=0;--i)
	{
		Print(closed[result[i]]);
		cout<<endl;
	}
	Print(object);
	cout<<endl;
	cout<<"A搜索结束!"<<endl<<endl;
}


bool operator<(const Node& node1,const Node& node2)
{
	if(node1.fn<node2.fn)
		return 1;
	else if(node1.fn==node2.fn)
	{
		if(node1.gn<node2.gn) return 1;
		else return 0;
	}
	else return 0;
}