main.cpp

八数码的

#include <iostream>
#include <vector>
#include <set>
using namespace std;

enum {UP,RIGHT,DOWN,LEFT};

struct Node{
	char board[3][3];
	int x,y;	//空格坐标
	int parent; //父节点下标
	int gn,hn,fn; // g(n),h(n),f(n)
};

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

int h(const Node& node) //计算结点 h(n)的值,运  用的课件上跟随数字的方法
{
	int u=0,v=0,tempu,tempv;
	int cost=0;
	if(node.board[1][1]!='0') cost+=1;
	do{
		tempu=u;
		tempv=v;
		if(u==0)
		{
			if(v<2)
			{
				v+=1;
			}
			else 
			{
				u+=1;
			}
		}
		else if(v==2)
		{
			if(u<2) 
			{
				u+=1;
			}
			else 
			{
				v-=1;
			}
		}
		else if(u==2)
		{
			if(v>0) 
			{
				v-=1;
			}
			else 
			{
				u-=1;
			}
		}
		else if(v==0)
		{
			if(u>0)
			{
				u-=1;
			}
			else v+=1;
		}
		if(node.board[tempu][tempv]!=target.board[tempu][tempv]) cost+=2;
	}while(!(u==0&&v==0));
	return cost;
}
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;
	target.fn=0;

	start.gn=0;
	start.hn=h(start);       
	start.fn=start.gn+start.hn;
}

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;}
	
}

int exist(set<Node>& open,vector<Node>& closed,const Node& node) //在open，closed表中查询是否已经存在node状态
{
	for(set<Node>::iterator it=open.begin();
		it!=open.end();++it)
	{	
		if(equal((*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 it=closed.begin();it!=closed.end();++it)
	{
		if(equal((*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;
				
				open.insert((*it)); //移回open表
			}
			return 2;			
		}
	}

	open.insert(node);
	return 0;
}

void A(const Node& start,const Node& target)
{
	set<Node> open;
	vector<Node> closed;
	vector<int> result;

	open.insert(start);

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

		if(equal(out,target))	//找到目标状态
		{
			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);				//计算h(n)
				outm.fn=outm.gn+outm.hn;		//计算f(n)
				exist(open,closed,outm);		
			}
		}
		
	}
	cout<<"A算法搜索:"<<endl;
	for(int i=result.size()-1;i>=0;--i)
	{
		display(closed[result[i]]);
		cout<<endl;
	}
	display(target);
	cout<<endl;
	cout<<"搜索结束!"<<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;
}

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