main.cpp

人工智能

#include <iostream>
#include <vector>
#include <queue>
#include <list>

using namespace std;

enum {UP,RIGHT,DOWN,LEFT};

struct Node{
	char board[3][3];
	int x,y;	//空格坐标
	int parent; //父节点下标
};

Node start;		//起始状态
Node target;	//目标状态

void init()
{
	start.board[0][0]='2';start.board[0][1]='8';start.board[0][2]='3';
	start.board[1][0]='1';start.board[1][1]='6';start.board[1][2]='4';
	start.board[2][0]='7';start.board[2][1]='0';start.board[2][2]='5';
	start.x=2;start.y=1;  //修改矩阵时空格坐标也要修改
	start.parent=-1;
	
	target.board[0][0]='1';target.board[0][1]='2';target.board[0][2]='3';
	target.board[1][0]='8';target.board[1][1]='0';target.board[1][2]='4';
	target.board[2][0]='7';target.board[2][1]='6';target.board[2][2]='5';
	target.x=1;target.y=1;
	target.parent=-1;
}

bool equal(const Node& node1,const Node& node2)	//判断两局面是否相等
{
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			if(node1.board[i][j]!=node2.board[i][j]) return false;
		return true;
}
void display(const Node& node)  //输出局面
{
	for(int i=0;i<3;++i)
	{
		for(int j=0;j<3;++j)
			cout<<node.board[i][j]<<"	  ";
		cout<<endl;
	}
}

Node Move(Node node,int dir)  //将当前状态移动生成新状态返回。 dir 取值为: UP,RIGHT,DOWN,LEFT，表示将空格上，右，下，左移动
{
	int x=node.x;
	int y=node.y;
	
	if(dir==UP)
	{
		if(x<=0)
		{
			node.x=-1; //返回错误值，不能移动
			return node;
		}
		else
		{
			char t=node.board[x][y];
			node.board[x][y]=node.board[x-1][y];
			node.board[x-1][y]=t;
			node.x=x-1;
			return node;
		}
	}
	else if(dir==RIGHT)
	{
		if(y>=2)
		{
			node.x=-1; //返回错误值，不能移动
			return node;
		}
		else
		{
			char t=node.board[x][y];
			node.board[x][y]=node.board[x][y+1];
			node.board[x][y+1]=t;
			node.y=y+1;
			return node;
		}
	}
	else if(dir==DOWN)
	{
		if(x>=2)
		{
			node.x=-1; //返回错误值，不能移动
			return node;
		}
		else
		{
			char t=node.board[x][y];
			node.board[x][y]=node.board[x+1][y];
			node.board[x+1][y]=t;
			node.x=x+1;
			return node;
		}
	}
	else if(dir==LEFT)
	{
		if(y<=0)
		{
			node.x=-1; //返回错误值，不能移动
			return node;
		}
		else
		{
			char t=node.board[x][y];
			node.board[x][y]=node.board[x][y-1];
			node.board[x][y-1]=t;
			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(equal((*it),node)) return 1;		
	}
	for(vector<Node>::const_iterator it=closed.begin();it!=closed.end();++it)
	{
		if(equal((*it),node)) return 1;			
	}
	return 0;
}

void BFS(const Node& start,const Node& target)
{
	cout<<"起始状态:"<<endl;
	display(start);
	cout<<endl;
	cout<<"目标状态:"<<endl;
	display(target);
	cout<<endl;

	list<Node> open;
	vector<Node> closed;
	vector<int> result;

	open.push_back(start);
	
	while(!open.empty())
	{
		Node out=open.front();
		open.pop_front();
		if(equal(out,target)) 
		{
			int i=out.parent;
			while(i!=-1)
			{
				result.push_back(i);
				i=closed[i].parent;
			}
			break;
		}
		closed.push_back(out);
		Node outUp=Move(out,UP);
		if(outUp.x!=-1)
		{
			if(!exist(open,closed,outUp))
			{
				outUp.parent=closed.size()-1;
				open.push_back(outUp);
			}
		}
		Node outRight=Move(out,RIGHT);
		if(outRight.x!=-1)
		{
			if(!exist(open,closed,outRight))
			{
				outRight.parent=closed.size()-1;
				open.push_back(outRight);
			}
		}
		Node outDown=Move(out,DOWN);
		if(outRight.x!=-1)
		{
			if(!exist(open,closed,outDown))
			{
				outDown.parent=closed.size()-1;
				open.push_back(outDown);
			}
		}
		Node outLeft=Move(out,LEFT);
		if(outLeft.x!=-1)
		{
			if(!exist(open,closed,outLeft))
			{
				outLeft.parent=closed.size()-1;
				open.push_back(outLeft);
			}
		}

	}
	cout<<"宽度优先搜索:"<<endl;
	for(int i=result.size()-1;i>=0;--i)
	{
		display(closed[result[i]]);
		cout<<endl;
	}
	
	display(target);
	cout<<"宽度优先搜索结束!"<<endl<<endl;
}

void main()
{
	init();
	BFS(start,target);
}