stackok.cpp

人工智能中的八数码问题：附有详细的注释 我们可以将八数码问题看成移动空格的问题.在不断的移动空格过程当中不断改变棋盘的布局,使之到达目标状态. 用一个open表(本程序采用序栈)的节点,从中选

#include "stack1.h"
#include<time.h>
stack  open,closed;//open表和 closed表
void swap(int &a,int &b)//交换两个整数
{
	int bak=a;  a=b;  b=bak;
}
int isok(int pos)//判断数码是否在棋盘内
{
	return pos>=0&&pos<size1*size1;
}
int isdiff(int ch[])//判断手工输入数码是否合法
{
	for(int i=0;i<size1*size1-1;i++)
		for(int j=i+1;j<size1*size1;j++)
			if(ch[i]==ch[j]||!isok(i)||!isok(j))
			  return 0;
   return 1;
}
void  init(int ch[],int flag)//初始化数码布局,分随机生成和手工输入两种
{
	if(flag)
	{
	   for(int i=0;i<size1*size1;i++)
		   ch[i]=i;
	         srand(time(0));
	           for(i=0;i<size1*size1;i++)
			   {
		           int temp=rand()%(size1*size1),temp1=rand()%(size1*size1);
		             if(temp!=temp1)
		               swap(ch[temp],ch[temp1]);
			   }
	       for(i=0;i<size1*size1;i++)
		   {
		      chbak[i]=ch[i];
		        chdes[i]=i;
		   }
	}
	else
	{
	        	cout<<"请输入目标状态:("<<size1*size1<<"个)"<<endl;
				   for( int j=0;j<size1*size1;j++)
					   cin>>chdes[j];
				   while(!(isdiff(chdes)))
				   {
					   cout<<"初始化错误,数据不合理!"<<endl;
					     cout<<"请输入目标状态:("<<size1*size1<<"个)"<<endl;
				          for( j=0;j<size1*size1;j++)
					         cin>>chdes[j];
				   }
				     cout<<"请输入初始状态:("<<size1*size1<<"个)"<<endl;
					   for(j=0;j<size1*size1;j++)
						   cin>>ch[j];
					         while(!(isdiff(ch)))
							 {
								 cout<<"初始化错误,数据不合理!"<<endl;
								  cout<<"请输入初始状态:("<<size1*size1<<"个)"<<endl;
					                for(j=0;j<size1*size1;j++)
						              cin>>ch[j];
							 }
					     for(j=0;j<size1*size1;j++)
							 chbak[j]=ch[j];
	}
}
int findnext(int pos,int step)//找到下一个合法的移动位置
{
  if(step>=0&&step<4)
  {
	switch(step)
	{
	case 0:
		if(isok(pos-size1))
			return pos-size1;
		return -1;
		 break;
	case 1:
		if(isok(pos+1)&&pos/size1==(pos+1)/size1)
			return pos+1;
		return -1;
		 break;
	case 2:
		if(isok(pos+size1))
			return pos+size1;
		return -1;
		break;
	case 3:
		if(isok(pos-1)&&pos/size1==(pos-1)/size1)
			return pos-1;
		return -1;
		break;
	}
  }
	return -1;
}
int getnum(int pos)//一个数码的错位距离和
{
	if(isok(pos))
	{
		for(int i=0;i<size1*size1;i++)
			if(chdes[i]==ch[pos])
			 return(abs(i/size1-pos/size1)+abs(i%size1-pos%size1));
	}
	return 0;
}
int getallnum()//所有数码的错位距离和,即h(n)
{
	int sum=0;
	   for(int i=0;i<size1*size1;i++)
		  sum+=getnum(i);
  return sum;
}
int findzero(int ch[])//找到空格的位置(这里是'0'的位置)
{
	for(int i=0;i<size1*size1;i++)
		if(ch[i]==0)
			return i;
	return -1;
}
void showparent(node *root)//递归方式显示结果路径
{
	if(root->pre!=-1)
	{
		showparent(&arr[root->pre]);
		root->show();cout<<"--第"<<root->precost+1<<"步--"<<endl;
	}	 
}
void showchar(int ch[])//显示一个状态
{
	for(int i=0;i<size1*size1;i++)
	{
		cout<<ch[i]<<"  ";
		 if((i+1)%size1==0)
			 cout<<endl;
	}
}
int  getpath(node *thisnode,int &sums)//递归方式搜索最优路径
{
	if(sums>=9*maxsize/10)//存储的空间不够用
	{
	 cout<<"应该是没有解路径,需要太多空间!(需存储 "<<jiecheng(size1*size1)<<"	个状态!)"<<endl;
		 return 0;
	}
	else
	{
		for(int i=0;i<size1*size1;i++)//恢复父节点的状态
			ch[i]=thisnode->ch1[i];
		 for(i=0;i<4;i++)//从四个方位搜索
		 {
			int pos1=findnext(thisnode->pos,i);//搜索的位置
			 if(pos1!=-1)//搜索的位置合法
			 { 
				 swap(ch[pos1],ch[thisnode->pos]);//移动数码
				 int hn=getallnum();//得到总的错位和
				  if(hn==0)//如果到达目标状态
				  {
					  cout<<"a solution is :"<<endl;
					      showchar(chbak);
	                         cout<<"--第1步--"<<endl;
					           showparent(thisnode);
					             showchar(chdes);
					    return 1;
				  }
				  else
					  if(hn>0)//如果没有到达目标状态
					  {
						  arr[sums].nextcost=hn;//将来的大概路程,即h(n)
						    arr[sums].precost=thisnode->precost+1;//已经走过的路程
						      arr[sums].pos=findzero(ch);//空格的位置
						  for(int j=0;j<size1*size1;j++)//当前的状态
							  arr[sums].ch1[j]=ch[j];
						         arr[sums].pre=thisnode->id;//父亲接点
						  if(!(open.cmp(&arr[sums])||closed.cmp(&arr[sums])))//如果子节点状态不存在open表和closed表中
						  {
							  open.insert(&arr[sums]);
						        sums++;
						  }
					  }
					  swap(ch[pos1],ch[thisnode->pos]);//恢复父亲节点的状态,以便向其他方向搜索
			 }
		}
		if(!open.isempty())//如果open表不空
		{
			node *tem=open.del();
			  closed.insert1(tem);
			   getpath(tem,sums);//递归搜索路径,用sums记录搜索的空间数
		}
		else
		{
			cout<<"没有解路径!"<<endl;
			return 0;
		}
	}
	return 0;
}
void  main()
{
	char cls[4]="cls",input='1';
	 int flag=1,sum=1;
	  author();
	 while(input>='1'&&input<='4')
	 {
		 open.clear();
		   closed.clear();
		    sum=1;
			 flag=1;
                  select();
		            cin>>input;
		if(input>='1'&&input<='4')
		{
			  switch(input)
			  {
			  case '1':
				  init(ch,1);
				  break;
			  case '2':
				  init(ch,0);
					   break;
			  case '3':
				  cout<<"请输入数码难题的规模(2--4)"<<endl;
				   cin>>size1;
				    while(!(size1>=2&&size1<=4))
					{
						cout<<"你输入的问题规模不适合于本程序!规模大小为:2~4"<<endl;
						 cin>>size1;
					}
					flag=2;
					break;
			  case '4':
				  system(cls);
				   author();
				  flag=2;
			  }
			  if(flag==1)
			  {
                  for(int i=0;i<maxsize;i++)
		            arr[i].id=i;
	                    arr[0].precost=0;arr[0].pre=-1;arr[0].pos=findzero(ch);arr[0].nextcost=getallnum();
	               for(i=0;i<size1*size1;i++)
		              arr[0].ch1[i]=ch[i];
	                       open.insert(&arr[0]);
			                node *p=open.del();
			                 closed.insert1(p);
			                   cout<<"目标状态:"<<endl;
			                     showchar(chdes);
			                        cout<<"初始状态:"<<endl;
			                          showchar(chbak);
			                 if(arr[0].nextcost>0)
			                    getpath(&arr[0],sum);
			                  else
				               cout<<"初始状态为目标状态！"<<endl;
			  }
		}
	 }
}