cpp1.cpp

启发式搜索见cpp1.C文件

#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <fstream.h>

#define SIZE 2000
#define N    9

struct ECnode
{
	int a[N];
	int step;
};

int NiXuShu(int S[],int n)  //计算数组的逆序数
{
	int sum,t;
	sum=0;
	for(int i=0;i<n;i++)
	{
		if(S[i]!=0)
		{
			t=0;
			for(int j=0;j<i;j++)
				if(S[j]>S[i]) t++;
            sum+=t;
		}
	}
	return sum;
}

int SpacePosition(int S[],int n)    //空格的位置
{
	for(int i=0;i<n;i++)
	{
		if(S[i]==0) return i;
	}
	return -1;
}

int NotOnPosition(int S[],int G[],int n) //不在位的个数
{
	int t=0;
	for(int i=0;i<n;i++)
	{
		if(S[i]!=0&&S[i]!=G[i]) t++;
	}
	return t;
}

int SEqualsG(int S[],int G[],int n)  //二数组是否相等
{
	for(int i=0;i<n;i++)
	{
		if(S[i]!=G[i]) return 0;
	}
	return 1;
}

void CopyArray(int S[],int G[],int n) //拷贝数组 
{
	for(int i=0;i<n;i++)
	{
		G[i]=S[i];
	}
}

int IsStepValid(int S[],int n,int direction,int sp)  //这一步是否有效
{
	int flag=0;
	switch(direction)
	{
	case 1:
		if(sp!=0 && sp!=3 && sp!=6 )  flag=1;
		break;
	case 2:
		if(sp!=0 && sp!=1 && sp!=2 )  flag=1;
    	break;
	case 3:
		if(sp!=2 && sp!=5 && sp!=8 )  flag=1;
		break;
	case 4:
		if(sp!=6 && sp!=7 && sp!=8 )  flag=1;
		break;
	}
	return flag;
}

void Move(int S[],int n,int direction,int sp)  //位置移动
{  
	int temp;

	switch(direction)
	{
	case 1:
		if(sp!=0 && sp!=3 && sp!=6 )
		{
			temp=S[sp]; S[sp]=S[sp-1]; S[sp-1]=temp;
		}
		break;
	case 2:
		if(sp!=0 && sp!=1 && sp!=2 ) 
        {
			temp=S[sp]; S[sp]=S[sp-3]; S[sp-3]=temp;
		}
    	break;
	case 3:
		if(sp!=2 && sp!=5 && sp!=8 )
		{
			temp=S[sp]; S[sp]=S[sp+1]; S[sp+1]=temp;
		}
		break;
	case 4:
		if(sp!=6 && sp!=7 && sp!=8 )
		{
			temp=S[sp]; S[sp]=S[sp+3]; S[sp+3]=temp;
		}
		break;
	}
}

int IsStateExist(int newstate[],ECnode queue[],int front,int rear)
{                                             //该状态是否存在 
	for( int i=front;i!=rear;i=(i+1)%SIZE )
	{
		if( SEqualsG(queue[i].a,newstate,N) ) return 1;
	}
	return 0;
}

void Print(int S[],int n)  //打印数组
{
	for(int i=0;i<n;i++)
	{
		cout<<S[i]<<" ";
		if((i+1)%3==0) cout<<endl;
	}
}

void PrintLevel(ostream &out,ECnode queue[],int front,int rear,int G[])
{                                            //打印一层的状态
    for(int i=0;i<3;i++)
	{
		for(int j=front;j!=rear;j=(j+1)%SIZE)
		{
			int nop=NotOnPosition(queue[j].a,G,N);
			for(int k=0;k<3;k++)
		    	out<<queue[j].a[i*3+k]<<" ";
			if(i==1)  out<<"("<<nop<<")  ";
			else      out<<"     ";
		}
		out<<endl;
	}
	out<<endl;
}

int FindBest(ECnode queue[],int front,int rear,int G[]) //找到最好的一个
{
	int t[N];
	int fn=N;
	while(front!=rear)
	{
		int sp=SpacePosition(queue[front].a,N);
		int pstep=queue[front].step;
        for(int i=1;i<=4;i++)
		{
			int flag=IsStepValid(queue[front].a,N,i,sp);
    		if(flag==1)
			{
		    	int cstep=i;
	    		if( !( (pstep==1 && cstep==3) || (pstep==2 && cstep==4)
			    	 ||(pstep==3 && cstep==1) || (pstep==4 && cstep==2)) )
				{
                    CopyArray(queue[front].a,t,N);
					Move(t,N,cstep,sp);
					int nop=NotOnPosition(t,G,N);
					if(nop<fn)	fn=nop;
				}
			}
		}
        front=(front+1)%SIZE;
	}
	return fn;
}

void GoOn(ECnode queue[],int &front,int &rear,int fn,int G[])//转到下一层状态
{
	int t[N];
	int end=rear;
	for(int j=front;j!=end;j=(j+1)%SIZE)
	{
		int sp=SpacePosition(queue[j].a,N);
		int pstep=queue[j].step;
		for(int i=1;i<=4;i++)
		{	
			int flag=IsStepValid(queue[j].a,N,i,sp);
    		if(flag==1)
			{
		    	int cstep=i;
	    		if( !( (pstep==1 && cstep==3) || (pstep==2 && cstep==4)
			    	 ||(pstep==3 && cstep==1) || (pstep==4 && cstep==2)) )
				{
                    CopyArray(queue[j].a,t,N);
					Move(t,N,cstep,sp);
					int nop=NotOnPosition(t,G,N);
					if( nop==fn&& !IsStateExist(t,queue,front,rear) )	
					{
						CopyArray(t,queue[rear].a,N);
					    queue[rear].step=cstep;
						rear=(rear+1)%SIZE;							
					}
				}
			}//flag
		}//i	
	}//j
	front=end;
}

void main()
{
	ofstream fin("tree.txt",ios::in | ios::out);

//	int S[]={6,2,7,5,4,1,3,8,0};
//	int S[]={4,6,2,1,7,5,3,8,0};
//	int S[]={0,1,2,3,4,8,7,5,6};
//	int S[]={1,2,3,4,8,0,7,5,6};
//	int S[]={1,0,2,8,5,4,7,6,3};

//	int S[]={1,2,3,8,4,7,6,5,0};//14
//	int S[]={1,2,3,8,4,7,6,0,5};//13
//	int S[]={1,2,3,8,4,7,0,6,5};//12
//	int S[]={1,2,3,8,4,0,7,6,5};//11
//	int S[]={1,2,3,8,0,4,7,6,5};//10
//	int S[]={1,2,3,0,8,4,7,6,5};//9
//	int S[]={1,2,0,3,8,4,7,6,5};//8
//	int S[]={1,0,2,3,8,4,7,6,5};//7
//	int S[]={0,1,2,3,8,4,7,6,5};//6

//	int S[]={1,2,4,3,0,8,7,6,5};//5
//	int S[]={1,2,3,0,4,8,7,6,5};//4 buxin
//	int S[]={1,2,0,3,8,4,7,6,5};//3
	int S[]={2,8,3,1,6,4,7,0,5};//2
//	int S[]={2,0,3,1,8,4,7,6,5};//1

	int G[]={1,2,3,8,0,4,7,6,5};

	ECnode queue[SIZE+1];
	int front=0;
	int rear=0;
	int fn;

	Print(S,N);
	cout<<NiXuShu(S,N)<<endl;
	getchar();
	if( (NiXuShu(S,N)+NiXuShu(G,N))%2!=0 )
	{
		cout<<"There is no way to get the aim!\n";
		exit(1);
	}

	CopyArray(S,queue[0].a,N);
	queue[0].step=0;
	rear++;
	int num=0;
	while( !SEqualsG(queue[front].a,G,N) )
	{
//		getchar();
		PrintLevel(fin, queue,front,rear,G);
		PrintLevel(cout,queue,front,rear,G);

        fn=FindBest(queue, front, rear,G);
	    GoOn(queue,front,rear,fn,G);

		if( (rear-front+SIZE)%SIZE>1600)
		{	cout<<"Too big!\n";	exit(1);	}
		num++;
	}
	PrintLevel(fin,queue,front,rear,G);
	PrintLevel(cout,queue,front,rear,G);
	cout<<num<<" finish"<<endl;
	fin.close();
//	cout<<num<<" finish! \n";

}