eight.cpp

八数码问题

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<string>
#include<ctime>
using namespace std;

struct eight                  //八数码结点;
{
	string item;             //用来储存八数码数据,其中'0'代表空格，格式如"123804765";
	int pos;                 //item中'0'的位置;
	int f;                  //评价函数值;
	int h;                   //启发函数值;
	int d;                   //节点深度;

};





eight initial;            //初始八数码节点；
eight goal;               //目标八数码节点;
multimap<int,eight> open;  //open表
vector<eight> closed;     //closed表
map<string,int> minnum;
int m[4]={-3,-1,1,3};     //'0'移动的方向“上，左，右，下”
int mm[9]={0,1,2,5,8,7,6,3,0}; 
map<string,bool>visited;  //判断节点是否已被扩展过
map<string,string> father; //储存节点的父节点
int (*h)(eight x);         //启发函数



bool IsGoal(eight x)      //判断是否到达目标状态
{   
	for(int i=0;i<9;i++)
		if(x.item[i]!=goal.item[i]) {return false;break;}

    return true;
}

int  Solved(string x)    //求出x的逆序数；
{   int count=0;
	for(int i=8;i>=0;i--){
        for(int j=0;j<i;j++)
		{
			if(x[i]>x[j]&&x[j]!='0') count++;
		}
	}
	return count;
}

int Get_h(eight x)    //启发函数1，不在位的将牌个数

{
	int count=0;
	for(int i=0;i<9;i++)
	{
		if(x.item[i]!=goal.item[i])
			count++;}
	if(x.pos==goal.pos) return count;
	else return count-1;
	
}

int Get_h2(eight x)      //启发函数2，每个将牌与目标位置之间的距离
{
	int count=0;
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			if(x.item[i]!=0) {if(x.item[i]==goal.item[j]) count=count+abs(i/3-j/3)+abs(i%3-j%3);}
		}
	}
	return count;
}

int Get_h3(eight x)     //启发函数3
{
	int count=0;
	if(x.item[4]!=0) count=count+1;
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<8;j++)
		{
			if(x.item[mm[i]]==goal.item[mm[j]])
			{
				if(x.item[mm[i+1]]!=goal.item[mm[j+1]])
				count=count+2;
			}
		}
	}
  
	count=count*3+Get_h2(x);
	return count;
}



void addopen(eight x) //把节点加进open表
{
	open.insert(make_pair(x.f,x));
	
	
}

void addclose(eight x) //把节点加进closed表
{
	closed.push_back(x);
}


void Remove()       //在open中移除x；
{
	multimap<int,eight>::iterator ir=open.begin();
	open.erase(ir);
}


void expand(eight x)  //扩展x结点
{   
	int opos=x.pos;
	char temp;
	

	for(int i=0;i<4;i++)
	{
		       eight tmp=x;
			  
			   
               int newposi=opos/3+m[i]/3;
			   int newposj=opos%3+m[i]%3;

			   if(newposi>=0 && newposi<=2 && newposj>=0 && newposj<=2)
			   {
			 int  newpos=newposi*3+newposj;
		       temp=tmp.item[opos];
				tmp.item[opos]=tmp.item[newpos];
				tmp.item[newpos]=temp;
				
				tmp.pos=newpos;
				if(visited[tmp.item]==false) father[tmp.item]=x.item;
				
				tmp.h=h(tmp);
				tmp.d=x.d+1;
				tmp.f=tmp.h+tmp.d;
				
		
				if(visited[tmp.item]==false) {addopen(tmp);visited[tmp.item]=true;}
			   }
	}
}

void print()                 //打印结果
{   
	string fatherstr=father[goal.item];
	vector<string>resualt;

	resualt.push_back(goal.item);
	
	while(fatherstr!="N")
	{
		resualt.push_back(fatherstr);
		fatherstr=father[fatherstr];
	}
    
	cout<<"**********************************************";
	cout<<endl;
	cout<<"完成的步数为："<<resualt.size()-1<<endl;
	for(int i=resualt.size()-1;i>=0;i--){

	for(int j=0;j<9;j++)
		{
		if(j%3==0) cout<<endl;
		cout<<resualt[i][j]<<" ";
		}
		cout<<endl;
		cout<<"----------------------------------";

}
	resualt.clear();
	open.clear();
	closed.clear();
	visited.clear();
	father.clear();
}
//*********************************************主函数***************************************************************
int main()

{    
	int k;
	
	
	while(true)
	{
		cout<<"输入0退出,其它继续:";
	cin>>k;
	  if(k==0) break;
		clock_t   start,   finish;
    double     duration;

    start=clock();

	string tmp1,tmp2;
	
	cout<<"********选择启发函数h**********"<<endl;
	cout<<"1.不在位的将牌个数(Get_h)"<<endl;
	cout<<"2.每个将牌与目标位置之间的距离(Get_h2)"<<endl;
	cout<<"3.h(n)=p(n)+3s(n)(Get_h3)"<<endl;
	cout<<"请选择(1 or 2  or 3):";
	char ch;
	cin>>ch;
	if(ch=='1'){h=Get_h;cout<<"********选择了启发函数1，开始测试......*********"<<endl;}
	if(ch=='2') {h=Get_h2;cout<<"********选择了启发函数2，开始测试......*********"<<endl;}
	if(ch=='3') {h=Get_h3;cout<<"********选择了启发函数3，开始测试......*********"<<endl;}

	

	cout<<"输入初始状态:"<<endl;
	cin>>tmp1;

	cout<<"输入目标状态:"<<endl;
	cin>>tmp2;
    int r1=Solved(tmp1);
	int r2=Solved(tmp2);
	if((r1%2==0 &&r2%2!=0)||(r1%2!=0 &&r2%2==0)){cout<<"初始状态与目标状态逆序数奇偶性不一致，无解"<<endl;;continue;}
	initial.item=tmp1;
	father[initial.item]="N";
	for(int i=0;i<9;i++)
		if(tmp1[i]=='0') initial.pos=i;
	
	goal.item=tmp2;
	goal.pos=4;

	

	initial.h=Get_h(initial);
	initial.d=0;
	initial.f=initial.h+initial.d;
	eight n;
	
	
	visited[initial.item]=true;
	addopen(initial);
	
	
	while(true){
	n=open.begin()->second;          //取open中的第一个元素
	if(IsGoal(n)) break;             //判断是否为目标状态
	Remove();                        //删除open中第一个元素
    addclose(n);                     //加入closed表
    expand(n);                       //扩展n
}

print();                             //打印结果
cout<<endl;
cout<<"*****************************************";
finish=clock();
    duration   =   (double)(finish   -   start);
	cout<<endl;
	cout<<"所用时间为："<<(float)(duration/1000000)<<endl;
	}
return 1;
}