八数码问题(A*&&双向BFS)---zoj_1217

题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=217

      首先说一下八数码问题的可解性。

       1.互换2个非零位置，状态的逆序奇偶性将保持不变。

       2.互换0和另一个非零位置，状态的逆序奇偶性将发生颠倒。

       3.因此，如果目标状态和起始状态的逆序奇偶性相同，问题可解，否则不可解。所以对于八数码问题的一个目标状态有9!/2种可解状态

       逆序奇偶性可以这样来求，将状态转化了数列，然后去掉X位，然后对于每一位，计算在它之前小于它的个数，每一位对应的值之和就是逆序奇偶数。

      A*算法具体不多说了，它的精髓在于f(n)=g(n)+h(n),中估值函数h(n)的设计。值的注意的是：

      如果估价值h(n)<= n（到目标节点的实际步长），这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。

　　如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

     因此在实际使用的时候应该更具需要来设计h(n)

     在zoj_1217中，为了不TLE，选择h(n)=20*dis(欧几里德距离)，但是得不到最优解

zoj_1217:

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
#include<string>
#include<math.h>
#include<iostream>
using namespace std;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
string path[4]={"d","r","u","l"};
int dp[10]={1,1,2,6,24,120,720,5040,40320,362880};
int final[9]={1,2,3,4,5,6,7,8,0};
bool hashtable[362885];
class state
{
public:
	int a[9],exp,zero,dept;
	string path;
	state(){};
	state(int num[9])
	{
		for(int i=0;i<9;++i)
			a[i]=num[i];
	}
	void swapn(int c)
	{	
		swap(a[zero],a[c]);
	}
};
struct cmp   
{   
    bool operator()(const state x,const state y)   
    {   
        return x.exp>y.exp;   
    }   
};
int getHash(int code[9])
{
	int sum=0;
	bool flag[9];
	int k;
	memset(flag,false,sizeof(flag));
	for(int i=0;i<9;++i)
	{
		k=0;
		for(int j=code[i]+1;j<9;++j)
		{
			if(!flag[j])
				++k;
		}
		sum+=k*dp[8-i];
		flag[code[i]]=true;
	}
	return 362879-sum;
}
int Eudis(int a[9])
{
	int dis=0;
	for(int i=0;i<9;++i)
	{
		for(int j=0;j<9;++j)
		{
			if(a[i]==final[j])
			{
				dis+=fabs(1.0*(i/3-j/3))+fabs(1.0*(i%3-j%3));
				break;
			}	
		}
	}
	return dis/2;	
}
state ans;
bool bfs(state ori)
{
	priority_queue<state,vector<state>,cmp >open;
	//queue<state>open;
	open.push(ori);
	while(!open.empty())
	{
		state t=open.top();
		open.pop();
		if(Eudis(t.a)==0)
		{
			ans=t;
			return true;
		}
		for(int i=0;i<4;++i)
		{
			int row=t.zero/3;
			int col=t.zero%3;
			int arow=row+next[i][1];
			int acol=col+next[i][0];
			if(arow<3&&arow>=0&&acol<3&&acol>=0)
			{
				int sw=arow*3+acol;
				state tmp=t;
				tmp.swapn(sw);
				tmp.zero=sw;
				int hcode=getHash(tmp.a);
				if(hashtable[hcode])
					continue;
				hashtable[hcode]=true;
				int dis=50*Eudis(tmp.a);
				++tmp.dept;
				tmp.exp=dis+tmp.dept;
				tmp.path+=path[i];
				open.push(tmp);		
			}			
		}
	}	
	return false;
}
void test(bool flag[9],int b,int num[9])
{
	if(b>8)
	{
		printf("%d\n",getHash(num));
		return;
	}
	for(int i=0;i<9;++i)
	{
		if(!flag[i])
		{
			flag[i]=true;
			num[b]=i;
			test(flag,b+1,num);
			flag[i]=false;
		}
	}
}
bool isSolveable (int statue[9])  
{  
   	int num=0;
	for (int i=1;i<=8;++i)  
    	{  
        	if(statue[i]==0)
			continue;
		for(int j=0;j<i;++j)  
        	{  
            		if(statue[j]==0)
				continue;
			if(statue[i]>statue[j]) 
				++num;  
        	}  
    	}  
    	if (num%2==1) return false;  
    	return true;  
}  

int main()
{
	//bool ff[9];
	//int nn[9];
	//memset(ff,false,sizeof(ff));
	//memset(nn,false,sizeof(nn));
	//test(ff,0,nn);
	//int a[9]={0,1,2,3,4,5,6,7,8};
	//int b[9]={8,7,6,5,4,3,2,1,0};
	//printf("%d\n",getHash(b));
	freopen("e:\\zoj\\zoj_1217.txt","r",stdin);
	while(1)
	{
		memset(hashtable,0,sizeof(hashtable));
		int flag=0;
		int num[9];
		int zero;
		char c;
		for(int i=0;i<9;++i)
		{
			if(scanf(" %c",&c)==EOF)
				return 0;
			if(c=='x')
			{	
				zero=flag;
				num[flag++]=0;
			}
			if(c<='9'&&c>='1')
				num[flag++]=c-48;
			if(flag>=9)
				break;	
		}
		state ori(num);
		ori.exp=20*Eudis(num);
		ori.zero=zero;
		ori.dept=0;
		int hcode=getHash(num);
		hashtable[hcode]=true;
		if(!isSolveable(num))
			printf("unsolvable\n");
		else
		{		
		bool f=bfs(ori);
		int l=ans.path.length();
		for(int i=0;i<l;++i)
			printf("%c",ans.path[i]);
		puts("");
		}
	}
}

 双向BFS：

 

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
string path[4]={"d","r","u","l"};
string path2[4]={"u","l","d","r"};
int dp[10]={1,1,2,6,24,120,720,5040,40320,362880};
int final[9]={1,2,3,4,5,6,7,8,0};
int hashtable[362885];
class state
{
public:
	int a[9],zero;
	string path;
	state(){};
	state(int num[9])
	{
		for(int i=0;i<9;++i)
			a[i]=num[i];
	}
	void swapn(int c)
	{	
		swap(a[zero],a[c]);
	}
};
state x,y;
state sl[362885];
int getHash(int code[9])
{
	int sum=0;
	bool flag[9];
	int k;
	memset(flag,false,sizeof(flag));
	for(int i=0;i<9;++i)
	{
		k=0;
		for(int j=code[i]+1;j<9;++j)
		{
			if(!flag[j])
				++k;
		}
		sum+=k*dp[8-i];
		flag[code[i]]=true;
	}
	return 362879-sum;
}
bool check(state a,state b)
{
	bool flag=true;
	for(int i=0;i<9;++i)
	{
		if(a.a[i]!=b.a[i])
		{
			flag=false;
			break;
		}
	}
	return flag;
}
bool bfs(state ori,state fin)
{
	queue<state>open,open2;
	open.push(ori);
	open2.push(fin);
	int hcode,fcode;
	state tmp,tmp2,t1,t2;
	while(1)
	{
		if(!open.empty())
		{
			t1=open.front();
			open.pop();
			for(int i=0;i<4;++i)
			{
				int row=t1.zero/3;
				int col=t1.zero%3;
				int arow=row+next[i][1];
				int acol=col+next[i][0];
				if(arow<3&&arow>=0&&acol<3&&acol>=0)
				{
					int sw=arow*3+acol;
					tmp=t1;
					tmp.swapn(sw);
					tmp.zero=sw;
					tmp.path+=path[i];
					hcode=getHash(tmp.a);
					if(hashtable[hcode]==1)
						continue;
					if(hashtable[hcode]==2)
					{
						x=tmp;
						y=sl[hcode];
						return true;
					}
					hashtable[hcode]=1;
					sl[hcode]=tmp;
					open.push(tmp);		
				}			
			}
		}
		if(!open2.empty())
		{
			t2=open2.front();
			open2.pop();
			for(int i=0;i<4;++i)
			{
				int row=t2.zero/3;
				int col=t2.zero%3;
				int arow=row+next[i][1];
				int acol=col+next[i][0];
				if(arow<3&&arow>=0&&acol<3&&acol>=0)
				{
					int sw=arow*3+acol;
					tmp2=t2;
					tmp2.swapn(sw);
					tmp2.zero=sw;
					tmp2.path+=path2[i];
					fcode=getHash(tmp2.a);
					if(hashtable[fcode]==2)
						continue;
					if(hashtable[fcode]==1)
					{
						y=tmp2;
						x=sl[fcode];
						return true;
					}
					hashtable[fcode]=2;
					sl[fcode]=tmp2;
					open2.push(tmp2);		
				}			
			}	
		}
	}	
	return false;
}
bool isSolveable (int statue[9])  
{  
   	int num=0;
	for (int i=1;i<=8;++i)  
    	{  
        	if(statue[i]==0)
			continue;
		for(int j=0;j<i;++j)  
        	{  
            		if(statue[j]==0)
				continue;
			if(statue[i]>statue[j]) 
				++num;  
        	}  
    	}  
    	if (num%2==1) return false;  
    	return true;  
}  

int main()
{
	freopen("e:\\zoj\\zoj_1217.txt","r",stdin);
	while(1)
	{
		memset(hashtable,0,sizeof(hashtable));
		int flag=0;
		int num[9];
		int zero;
		char c;
		for(int i=0;i<9;++i)
		{
			if(scanf(" %c",&c)==EOF)
				return 0;
			if(c=='x')
			{	
				zero=flag;
				num[flag++]=0;
			}
			if(c<='9'&&c>='1')
				num[flag++]=c-48;
			if(flag>=9)
				break;	
		}
		state ori(num);
		ori.zero=zero;
		state fin(final);
		fin.zero=8;
		int ocode=getHash(num);
		int fcode=getHash(final);
		hashtable[ocode]=1;
		hashtable[fcode]=2;
		sl[ocode]=ori;
		sl[fcode]=fin;
		if(!isSolveable(num))
			printf("unsolvable\n");
		else
		{		
			if(check(ori,fin))
				puts("");
			bool f=bfs(ori,fin);
			int l=x.path.length();
			for(int i=0;i<l;++i)
				printf("%c",x.path[i]);
			l=y.path.length();
			for(int i=l-1;i>=0;--i)
				printf("%c",y.path[i]);
			puts("");
		}
	}
}