ljy.cpp

这是一个人工智能里的八数码搜索程序

#include<iostream.h>
#include<time.h>
#include<stdio.h>
#include<malloc.h>
typedef struct open                //定义open表的接点
{
	int f,g,h;
	int num[9];
	struct closed *parent;
	struct open *next;
}open;
typedef struct closed              //定义closed表的接点
{
	int f,g,h;
	int n;
	int num[9];
	struct closed *parent;
	struct closed *next;
}closed;
open *pop,*p,*last;               //open表的头指针、工作指针、尾指针
open *sg;                         //sg为目标接点
closed *head1,*p1,*last1;         //closed表的头指针、工作指针、尾指针
open *Init();                     //设置初始状态和目标状态
int  Search();                    //进行盲目的广度优先搜索
void Output();                    //如果搜索成功,Search()调用Output()输出搜索结果
void change(int i,int j,open *c); //交换位置             
void Expand();                    //Search()函数调Expand(),将扩展接点放到open表的尾部
void Sort();                      //对open表中的接点排序
void main()
{
    Init();
	long beginTime =clock();//获得开始时间，单位为毫秒
	int j=Search();
	if(j==0)
	{
        cout<<"搜索fail"<<endl;
		cout<<"没有从初始状态到目标状态的解路径"<<endl;
	}	
	long endTime=clock();//获得结束时间
       cout<<"beginTime:"<<beginTime<<endl;
       cout<<"endTime:"<<endTime<<endl;
       cout<<"endTime-beginTime:"<<endTime-beginTime<<endl;
	   cout<<"搜索时间为："<<endTime-beginTime<<" ms"<<endl<<endl;
}

open *Init()
{
	pop=(open*)malloc(sizeof(open));
	cout<<"八数码A*算法。"<<endl;
	cout<<"请输入初始状态："<<endl;
	cin>>pop->num[0]>>pop->num[1]>>pop->num[2];
	cin>>pop->num[3]>>pop->num[4]>>pop->num[5];
	cin>>pop->num[6]>>pop->num[7]>>pop->num[8];
    last=pop;
	last->next=NULL;
	last->parent=NULL;
	sg=(open*)malloc(sizeof(open));
	cout<<"请输入目标状态："<<endl;
    cin>>sg->num[0]>>sg->num[1]>>sg->num[2];
	cin>>sg->num[3]>>sg->num[4]>>sg->num[5];
	cin>>sg->num[6]>>sg->num[7]>>sg->num[8];
	sg->parent=NULL;
	sg->next=NULL;
	int m=0;
	for(int i=0;i<=8;i++)
	{
		if(pop->num[i]!=sg->num[i])
			m++;
	}
	pop->f=m;
	pop->h=m;
	pop->g=0;
	return pop;
}
int Search()
{
	    int a=0;
	    head1=(closed *)malloc(sizeof(closed));
		head1->num[0]=0;
		head1->num[1]=0;
		head1->num[2]=0;
		head1->num[3]=0;
		head1->num[4]=0;
		head1->num[5]=0;
		head1->num[6]=0;
		head1->num[7]=0;
		head1->num[8]=0;
		last1=head1;
		last1->next=NULL;
		last1->parent=NULL;
		pop->parent=head1;
    while(pop!=NULL&&last1->n<1000)
	{
		Sort();
		p1=(closed *)malloc(sizeof(closed));
		p1->num[0]=pop->num[0];
		p1->num[1]=pop->num[1];
		p1->num[2]=pop->num[2];
		p1->num[3]=pop->num[3];
		p1->num[4]=pop->num[4];
		p1->num[5]=pop->num[5];
		p1->num[6]=pop->num[6];
		p1->num[7]=pop->num[7];
		p1->num[8]=pop->num[8];
		p1->f=pop->f;
		p1->g=pop->g;
		p1->h=pop->h;
		last1->next=p1;
		last1=last1->next;
		last1->n=++a;
		last1->next=NULL;
		last1->parent=pop->parent;
		pop->parent=NULL;
		 
		if( last1->num[0]==sg->num[0]&&
			last1->num[1]==sg->num[1]&&
			last1->num[2]==sg->num[2]&&
			last1->num[3]==sg->num[3]&&
			last1->num[4]==sg->num[4]&&
			last1->num[5]==sg->num[5]&&
			last1->num[6]==sg->num[6]&&
			last1->num[7]==sg->num[7]&&
			last1->num[8]==sg->num[8]  )
		{
			cout<<"搜索success"<<endl;
			while(pop!=NULL)
			{
				open*q=pop;
				pop=pop->next;
				free(q);
			}
			Output();
			return (1);
		}
		else
		{
			int i;
			for(i=0;last1->num[i]!=0;i++)
			{;}
			switch(i)
			{
			case 0:
				p=(open*)malloc(sizeof(open));
				change(0,1,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(0,3,p);
				Expand();
				break;
			case 1:
				p=(open*)malloc(sizeof(open));
		    	change(1,0,p);
				Expand();
				p=(open*)malloc(sizeof(open));
		    	change(1,2,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(1,4,p);
				Expand();
				break;
			case 2:
				p=(open*)malloc(sizeof(open));
				change(2,1,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(2,5,p);
				Expand();
				break;
			case 3:
				p=(open*)malloc(sizeof(open));
				change(3,0,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(3,4,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(3,6,p);
				Expand();
				break;
			case 4:
				p=(open*)malloc(sizeof(open));
				change(4,3,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(4,1,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(4,5,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(4,7,p);
				Expand();
				break;
			case 5:
				p=(open*)malloc(sizeof(open));
				change(5,4,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(5,2,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(5,8,p);
				Expand();
				break;
			case 6:
				p=(open*)malloc(sizeof(open));
				change(6,3,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(6,7,p);
				Expand();
				break;
			case 7:
				p=(open*)malloc(sizeof(open));
				change(7,6,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(7,4,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(7,8,p);
				Expand();
				break;
			case 8:
				p=(open*)malloc(sizeof(open));
				change(8,7,p);
				Expand();
				p=(open*)malloc(sizeof(open));
				change(8,5,p);
				Expand();
			}
		}
		open *q;
		q=pop;
        pop=pop->next;
		free(q);
	}
    return (0);
}

void Expand()
{       closed *r;
        r=head1;
		while(r!=NULL)
		{
	    	if(p->num[0]==r->num[0]&&
		       p->num[1]==r->num[1]&&
		       p->num[2]==r->num[2]&&
	      	   p->num[3]==r->num[3]&&
       		   p->num[4]==r->num[4]&&
		       p->num[5]==r->num[5]&&
		       p->num[6]==r->num[6]&&
		       p->num[7]==r->num[7]&&
		       p->num[8]==r->num[8]  )
			{
			  free(p);
		      break;
			}			
		    else
			
			   r=r->next;
			
		}
		if(r==NULL)
		{
			last->next=p;
			last=last->next;
			last->next=NULL;
			last->parent=last1;
			last->g=last1->g+1;
			int m=0;
	        for(int i=0;i<=8;i++)
			{
	        	if(last->num[i]!=sg->num[i])
		    	m++;
			}
			last->h=m;
			last->f=last->g+last->h;
		}
}
void Output()
{
	int b=0;
	int d=last1->n;
	closed *r;
	r=last1;
	open *head2,*p2;
	head2=NULL;
	while(r!=head1)
	{
		b++;
		p2=(open*)malloc(sizeof(open));
		p2->num[0]=r->num[0];
		p2->num[1]=r->num[1];
		p2->num[2]=r->num[2];
		p2->num[3]=r->num[3];
		p2->num[4]=r->num[4];
		p2->num[5]=r->num[5];
		p2->num[6]=r->num[6];
		p2->num[7]=r->num[7];
		p2->num[8]=r->num[8];
		p2->next=head2;
		head2=p2;
		r=r->parent;
	}
	while(head1!=NULL)
	{
		closed*q=head1;
		head1=head1->next;
		free(q);
	}
	cout<<"从初始状态到目标状态路径上的结点为："<<endl;
	while(head2!=NULL)
    {
		cout<<head2->num[0]<<head2->num[1]<<head2->num[2]<<endl;
		cout<<head2->num[3]<<head2->num[4]<<head2->num[5]<<endl;
		cout<<head2->num[6]<<head2->num[7]<<head2->num[8]<<endl;
		cout<<endl;
		p2=head2;
		head2=head2->next;
        free(p2);
	}
	cout<<"节点总数为："<<d<<endl;
	cout<<"搜索深度为："<<--b<<endl<<endl;
}

void Sort()
{
	open *r;
	r=(open*)malloc(sizeof(open));
	for(open*s=pop;s!=NULL;s=s->next)
	{
		for(open*t=s->next;t!=NULL;t=t->next)
		{
		    if(s->f>t->f)
			{
				r->f=t->f;
				r->g=t->g;
				r->h=t->h;
				r->parent=t->parent;
				r->num[0]=t->num[0];
				r->num[1]=t->num[1];
				r->num[2]=t->num[2];
				r->num[3]=t->num[3];
				r->num[4]=t->num[4];
				r->num[5]=t->num[5];
				r->num[6]=t->num[6];
				r->num[7]=t->num[7];
				r->num[8]=t->num[8];
				t->f=s->f;
				t->g=s->g;
				t->h=s->h;
				t->parent=s->parent;
				t->num[0]=s->num[0];
				t->num[1]=s->num[1];
				t->num[2]=s->num[2];
				t->num[3]=s->num[3];
				t->num[4]=s->num[4];
				t->num[5]=s->num[5];
				t->num[6]=s->num[6];
				t->num[7]=s->num[7];
				t->num[8]=s->num[8];
				s->f=r->f;
				s->h=r->h;
				s->g=r->g;
				s->parent=r->parent;
				s->num[0]=r->num[0];
				s->num[1]=r->num[1];
				s->num[2]=r->num[2];
				s->num[3]=r->num[3];
				s->num[4]=r->num[4];
				s->num[5]=r->num[5];
				s->num[6]=r->num[6];
				s->num[7]=r->num[7];
				s->num[8]=r->num[8];
			}
		}
	}
}
			
void change(int i,int j,open *c)
{  
	c->num[i]=last1->num[j];
	c->num[j]=last1->num[i];
	for(int k=0;k<9;k++)
	{
		if(k==i||k==j)  continue;
		c->num[k]=last1->num[k];
	}
}