eight.cpp

一个简单的用A*算法实现8数码问题的人工智能程序

#include <stdio.h>
#include <math.h>

#define dx(i) (((i)==0)-((i)==1))		//便于以后做循环，用一个i的函数来表示移动	
#define dy(i) (((i)==2)-((i)==3))		//0表示右移一格，1表示左移一格	
#define inside(x) ((x)>=0 && (x)<=2)	//2表示下移一格，3表示上移一格

struct node			//建立结点结构			
{
	int map[9];			
	int valuence;			
	node * parent;			
	node * next;			
};
node *popen,*pclose=NULL;

int distance(int ix, int iy, int jx, int jy )  //计算2个点i,j之间的距离权值
{
	return abs(ix-jx)+abs(iy-jy);
}

int exchange(int zerox,int zeroy,int map[],int x,int y,int mpi[])//把2个点做替换
{																 //即结点的移动，0为空格
	int n,i,j,k;												 //zerox,zeroy为0的坐标，map[]为数字
	i=zerox+3*zeroy;											 //位置，mpi[]为移动后
	j=x+3*y;
	for (k=0;k<9;k++)
	{
		mpi[k]=map[k];
	}
	n=map[j];
	mpi[i]=map[j];
	mpi[j]=0;
	return n;
}

int beginvalue(int begin[] ,int end[])		//计算初始状态权值
{
	int i,j,value,ix,iy,jx,jy;
	value=0;
	for(i=0;i<9;i++)
	{
		for(j=0;j<9;j++)
		{
			if(begin[i]==end[j])
			{
				iy=i/3;
				ix=i%3;
				jy=j/3;
				jx=j%3;
				if(begin[i])
					value=value+distance(ix, iy, jx, jy);
			}
		}
	}
	return value;
}

void insert(node * nnode,node ** list)		     //结点插入
{
	node * j;
	j=*list;
	*list=nnode;
	nnode->next=j;
}

void pdelete(node * nnode ,node **prev)		    //结点删除
{
	*prev=nnode->next;
}

int findzero(int map[])					//寻找0结点
{
	int i,n;
	for(i=0;i<9;i++)
		if(map[i]==0)
			n=i;
		return n;
}

void outputmap(int map[])				//输出一步的数字格
{
	int i,j,k;
	for( j=0;j<3;j++)
	{
		for( i=0;i<3;i++)
		{
			k=3*j+i;
			if(map[k])
				printf("%d ",map[k]);		
			else printf("  ");					
		}
		printf("\n");
	}
	printf("\n");
}

void main()
{
	int i,j,ix,iy,jx,jy,k;
	int begin[9],end[9];
	printf("请输入初始态(每输入一个按一下回车,空的用0表示)\n");//数据输入
	for(i=0;i<9;i++)
	{
		scanf("%d",&end[i]);
	}
	printf("请输入终止态(每输入一个按一下回车,空的用0表示)\n");
	for(i=0;i<9;i++)
	{
		scanf("%d",&begin[i]);
	}

	int u,v,beginnum,endnum,p,q;                        //该部分为判断给出的初始终止状态是否存在解
	u=0;v=0;k=0;beginnum=0;endnum=0;p=0;q=0;			  //即判断逆序数是否同为奇偶
	for(u=0;u<9;u++)									  //beginnum、endnum分别为初始和终止状态的逆序数
		for(v=u+1;v<9;v++)
		{
			if(begin[u]&&begin[v]&&begin[u]>begin[v])
				beginnum++;
			if(end[u]&&end[v]&&end[u]>end[v])
				endnum++;
		}
	p=beginnum%2;
	q=endnum%2;
	if(p!=q)
	{
		printf("该状态为无解\n");
		return;
	}

	popen=new node;									//起始状态节点放入open
	popen->valuence=beginvalue(begin ,end);			//初始化
	popen->parent=0;
	for(i=0;i<9;i++)
	{
		popen->map[i]=begin[i];
	}
	popen->next=0;
	node *minnode,**prev,**minprev;	
	
	while(popen)
	{
		int min=1000;
		node *n;
		for(n=popen,prev=&popen;n;prev=&n->next,n=n->next)	//选出权值最小的结点放入CLOSED
			if(n->valuence<min)
			{
				minprev=prev;
				min=n->valuence;
				minnode=n;
			}
			pdelete(minnode,minprev);  //从OPEN中删除
			insert(minnode,&pclose);	//CLOSED中插入
			if(min==0)					//如果权值到0，则转向输出步				
				goto output;			
			int m,zerox,zeroy;
			m=findzero(minnode->map);	//找出0结点
			zerox=m%3;
			zeroy=m/3;
			
			for(i=0;i<4;i++)			//找出0结点可以移动的方向				
			{
				if(inside(zerox+dx(i)) && inside(zeroy+dy(i)))		
				{
					int mp[9],movex;
					movex=exchange(zerox,zeroy,minnode->map,zerox+dx(i),zeroy+dy(i),mp);
											   //移动0结点和MOVEX结点的位置，并返回movex
					for(n=pclose;n;n=n->next)  //判断新找到的数字格是否已在CLOSE表中出现
					{
						for(j=0;j<9;j++)
						{
							if(n->map[j]!=mp[j])
								goto out1;  //没有出现则则跳出该判断循环
						}
						goto out2;   //若出先则GOTO OUT2继续下一个移动的查找
out1:;
					}
					
					
					node * newnode=new node;		
					for(j=0;j<9;j++)
					{
						newnode->map[j]=mp[j];
						if(mp[j]==0)    //计算0结点的位置
						{
							ix=j%3;
							iy=j/3;
						}
						if(end[j]==movex)//计算已移动点的位置
						{
							jx=j%3;
							jy=j/3;
						}
					}
					newnode->parent=minnode;
					
					newnode->valuence=minnode->valuence-distance(ix,iy,jx,jy)+distance(zerox,zeroy,jx,jy);
										   //新结点的权为原权值减去移动前数字权再加上移动后数字权
					insert(newnode,&popen);//将新移动得到的结点放入OPEN
					
				}
out2:;
	 
			}
			
			
	}
	printf("该状态为无解");   //搜索完所有结点，得OPEN为空时，无解
	return;
output:
	i=0;
	for(;minnode;minnode=minnode->parent,i++)     //因为输出为逆序，所以输如的END作为初始状态，
		outputmap(minnode->map);
	printf("%d步内可求得解\n",i-1);			      //begin作为终止状态
}