a_al.cpp

九宫图A*算法。根据高等教育出版社出版的人工智能书籍

//=================================
//A*全局最佳优先算法
//h(n)取不在位的棋子数
//=================================
#include<iostream>
#include<fstream>
#include<sstream>
#include<malloc.h>
#include<stdlib.h>
using namespace std;
//----------------------------------
typedef int Mat[3][3];//定义3*3数组类型
Mat mark,destination;
int p=0,num=0;
int o=1;//o为当前open表所用空间数
int sum=0;//当前扩展出的节点总数
typedef struct Node{
	int number;//节点号
	Mat c;//存储每一步的结点矩阵
	int noway[4];//可以走的路线l,u,r,d
	int father;//指向父亲节点
	int f,g;//g为节点深度，f为节点总代价
}Node,*e_node;//结点结构
typedef struct path{
	Mat d;//存储矩阵
	int tag;
}path,*e_path;//路径结构
e_node closed=(e_node)malloc((4000)*sizeof(Node));
e_node open=(e_node)malloc((4000)*sizeof(Node));
e_path paths=(e_path)malloc((1000)*sizeof(path));
e_node pcom,pclo;
e_node popen=open;//指向open表的指针
e_node pclosed=closed;//指向closed表的指针
int slove(Mat a);//判断是否有解
void change(Mat a,Mat b);//完成两个数组的赋值（将数组b的值赋给数组a）
void input();//从文件读入初始状态
void output();//将解路径输出到文件
void print(Mat a);//显示输出
int compare(Mat a,Mat b);//判断两矩阵a和b是否相等
void judge(e_node a);//判断移动路线并计算节点的f值
int com_father(e_node a);//与open表里的节点进行比较，并根据情况修改父亲节点指针
void make_equal(e_node a,e_node b);//将节点b中所有的值赋给a中相对应的属性
void movl(e_node a);//将0左移
void movr(e_node a);//将0右移
void movd(e_node a);//将0下移
void movu(e_node a);//将0上移
void move(e_node a);//将closed表里a处以后的节点往前移一位
void pickout(int x);//从closed表里取出节点号为x的节点，并将pclo指向该节点
void update_open();//将open表里的各节点按f值从小到大排序
//----------------------------------
void main(){	
	input();
	e_node aid;
	change(popen->c,mark);
	popen->father=-1;
	popen->g=0;
	popen->number=sum;
	judge(popen);
	make_equal(pclosed,popen);
	if(!slove(popen->c))
	{
		cout<<"此初始节点到目标节点没有解路径!"<<endl;
		return;
	}
	for(int i=0;i<=sum;i++)
	{
		if(o>=4000)
		{
			for(int j=0;j<4000;j++)
			{
				if(compare(popen->c,destination))
					popen++;
				else
					goto find;
			}
			cout<<"分配的open表空间已用完!"<<endl;
			cout<<"已扩展出"<<sum<<"个节点,未能找到目标节点!"<<endl;
			return;
		}

		if(!compare(popen->c,destination))
		{
find:		int res=popen->number;
			while(res>=0)
			{
				pickout(res);
				change(paths[p].d,pclo->c);
				paths[p].tag=res;
				res=pclo->father;
				num++;
				p++;
			}
			output();
			return;
		}
		else
		{
			//update_open();
			/*========分解节点=============*/
			pclosed++;
			if(popen->noway[0])
			{
				movl(popen);
			}
			if(popen->noway[1])
			{
				movu(popen);
			}
			if(popen->noway[2])
			{
				movr(popen);
			}
			if(popen->noway[3])
			{
				movd(popen);
			}
			update_open();
			o--;
			make_equal(pclosed,popen);
		}
	}
}
//----------------------------------
int slove(Mat a)
{
	int k=0,count=0;
	int intial[8];
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(a[i][j]!=0)
			{
				intial[k]=a[i][j];
				k++;
			}
			else
				continue;
		}
	}
	for(k=k-1;k>0;k--)
	{
		for(int kk=0;kk<=k;kk++)
		{
			if(intial[kk]<intial[k])
			{
				count++;
			}
			else
				continue;
		}
	}
	if(count%2)
		return 1;
	else
		return 0;
}
//----------------------------------
void input()
{
	ifstream startin("start.txt");
	int sj,si=0;
	for(string ss;getline(startin,ss);)
	{
		sj=0;
		istringstream sin(ss);
		for(int ia;sin>>ia;)
		{	
			mark[si][sj]=ia;
			sj++;
		}
		si++;
	}
	ifstream endin("end.txt");
	int ei=0,ej;
	for(string es;getline(endin,es);)
	{
		ej=0;
		istringstream sin(es);
		for(int ib;sin>>ib;)
		{	
			destination[ei][ej]=ib;
			ej++;
		}
		ei++;
	}
}
//----------------------------------
int compare(Mat a,Mat b)
{
	int i,j,k=0;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(a[i][j]!=b[i][j]&&b[i][j]!=0)
				k++;
		}
	}
	return k;
}
//----------------------------------
void make_equal(e_node a,e_node b)
{
	change(a->c,b->c);
	a->f=b->f;
	a->father=b->father;
	a->g=b->g;
	for(int i=0;i<4;i++)
	    a->noway[i]=b->noway[i];
	a->number=b->number;
}
//----------------------------------
void movl(e_node a)
{
	sum++;
	Node middle;
	e_node mid=&middle;
	e_node po=open,pc=closed;
	po+=o;
	pc+=sum;
	change(mark,a->c);
	int i=0,j;
	for(;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(mark[i][j]==0)
				goto movl;
		}
	}
movl:mark[i][j]=mark[i][j-1];
	mark[i][j-1]=0;
	change(mid->c,mark);
	mid->father=a->number;
	mid->g=a->g+1;
	mid->number=sum;
	judge(mid);
	mid->noway[2]=0;
	if(com_father(mid))
	{
		int x=com_father(mid);
		if(x==1)
		{
			if(pcom->f > mid->f)
			{
				mid->number=pcom->number;
				make_equal(pcom,mid);
			}
			else
				sum--;
		}
		else
		{
			if(pclo->f > mid->f)
			{
				mid->number=pclo->number;
				move(pclo);
				make_equal(po,mid);
			}
			else
				sum--;
		}
	}
	else
	{
		make_equal(po,mid);
		o++;
	}
}
//-----------------------------------
void movr(e_node a)
{
	sum++;
	Node middle;
	e_node mid=&middle;
	e_node po=open,pc=closed;
	po+=o;
	pc+=sum;
	change(mark,a->c);
	int i=0,j;
	for(;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(mark[i][j]==0)
				goto movr;
		}
	}
movr:
	mark[i][j]=mark[i][j+1];
	mark[i][j+1]=0;
	change(mid->c,mark);
	mid->father=a->number;
	mid->g=a->g+1;
	mid->number=sum;
	judge(mid);
	mid->noway[0]=0;
	if(com_father(mid))
	{
		int x=com_father(mid);
		if(x==1)
		{
			if(pcom->f > mid->f)
			{
				mid->number=pcom->number;
				make_equal(pcom,mid);
			}
			else
				sum--;
		}
		else
		{
			if(pclo->f > mid->f)
			{
				mid->number=pclo->number;
				move(pclo);
				make_equal(po,mid);
			}
			else
				sum--;
		}
	}
	else
	{
		make_equal(po,mid);
		o++;
	}
}
//----------------------------------
void movd(e_node a)
{
	sum++;
	Node middle;
	e_node mid=&middle;
	e_node po=open,pc=closed;
	po+=o;
	pc+=sum;
	change(mark,a->c);
	int i=0,j;
	for(;i<3;++i)
	{
		for(j=0;j<3;++j)
		{
			if(mark[i][j]==0)
				goto movd;
		}
	}
movd:
	mark[i][j]=mark[i+1][j];
	mark[i+1][j]=0;
	change(mid->c,mark);
	mid->father=a->number;
	mid->g=a->g+1;
	mid->number=sum;
	judge(mid);
	mid->noway[1]=0;
	if(com_father(mid))
	{
		int x=com_father(mid);
		if(x==1)
		{
			if(pcom->f > mid->f)
			{
				mid->number=pcom->number;
				make_equal(pcom,mid);
			}
			else
				sum--;
		}
		else
		{
			if(pclo->f > mid->f)
			{
				mid->number=pclo->number;
				move(pclo);
				make_equal(po,mid);
			}
			else
				sum--;
		}
	}
	else
	{
		make_equal(po,mid);
		o++;
	}
}
//---------------------------------
void movu(e_node a)
{
	sum++;
	Node middle;
	e_node mid=&middle;
	e_node po=open,pc=closed;
	po+=o;
	pc+=sum;
	change(mark,a->c);
	int i=0,j;
	for(;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(mark[i][j]==0)
				goto movu;
		}
	}
movu:
	mark[i][j]=mark[i-1][j];
	mark[i-1][j]=0;
	change(mid->c,mark);
	mid->father=a->number;
	mid->g=a->g+1;
	mid->number=sum;
	judge(mid);
	mid->noway[3]=0;
	if(com_father(mid))
	{
		int x=com_father(mid);
		if(x==1)
		{
			if(pcom->f > mid->f)
			{
				mid->number=pcom->number;
				make_equal(pcom,mid);
			}
			else
				sum--;
		}
		else
		{
			if(pclo->f > mid->f)
			{
				mid->number=pclo->number;
				move(pclo);
				make_equal(po,mid);
			}
			else
				sum--;
		}
	}
	else
	{
		make_equal(po,mid);
		o++;
	}
}
//-----------------------------------
void move(e_node a)
{
	for(;pclo<pclosed-1;pclo++)
		make_equal(pclo,pclo+1);
	pclosed--;
}
//-----------------------------------
int com_father(e_node a)
{
	pcom=open;
	pcom++;
	for(int i=1;i<o;i++)
	{
		if(!compare(pcom->c,a->c))
			return 1;
	}
	for(pclo=closed;pclo<pclosed;pclo++)
		if(!compare(pclo->c,a->c))
			return 2;
	return 0;
}
//-----------------------------------
void update_open()
{
	Node middle;
	e_node mid=&middle;
	e_node po,pnext;
	int i,j=1;
	while(j)
	{
		po=open;
		po++;
		pnext=po+1;
		j=0;
		for(i=1;i<o-1;i++)
		{
            if(po->f>pnext->f)
			{
                make_equal(mid,po);
				make_equal(po,pnext);
				make_equal(pnext,mid);
				j++;
			}//if
			po++;
			pnext++;
		}//for
	}//while(j)
	po=open;
	pnext=po+1;
	for(i=0;i<o-1;i++)
	{
		make_equal(po,pnext);
        po++;
		pnext++;
	}
}
//-----------------------------------
void pickout(int x)
{
	pclo=closed;
	for(;pclo<pclosed;pclo++)
		if(pclo->number==x)
			return;
}
//-----------------------------------
void judge(e_node a)
{
	int i,j;
	for(i=0;i<3;i++)
	{
		for(j=0;j<3;j++)
		{
			if(a->c[i][j]==0)
				goto movtag;
		}
	}
movtag:
	switch(i)//确定行号
	{
		case 0:
			{
				a->noway[3]=1;
				a->noway[1]=0;
				break;
			}
		case 2:
			{
				a->noway[1]=1;
				a->noway[3]=0;
				break;
			}
		default:
			{
				a->noway[1]=1;
				a->noway[3]=1;
				break;
			}
	}
	switch(j)//确定列号
	{
		case 0:
			{
				a->noway[2]=1;
				a->noway[0]=0;
				break;
			}
		case 2:
			{
				a->noway[0]=1;
				a->noway[2]=0;
				break;
			}
		default:
			{
				a->noway[2]=1;
				a->noway[0]=1;
				break;
			}
	}
	a->f=a->g+compare(a->c,destination);//计算f值
}
//---------------------------------------
void change(Mat a,Mat b)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			a[i][j]=b[i][j];
		}
}
//---------------------------------------
void output()
{
	ofstream out("path.txt");
	out<<"一共扩展出"<<sum<<"个结点"<<endl;
	for(p=num-1;p>=0;p--)
	{
		out<<"结点"<<paths[p].tag<<endl;
		int j,i=0;
		for(;i<3;i++)
		{
			for(j=0;j<3;j++)
			{
				out<<paths[p].d[i][j]<<" ";
			}
			out<<endl;
		}
		out<<"  ↓"<<endl;
	}
	out<<"正确的解路径"<<endl;
	out<<endl<<"解路径步数为"<<num<<endl;
}