eightnum.cpp

人智经典算法的实现

//用A*算法求解八数码问题
#include   <iostream>
using namespace std;


int  count=0;
struct   Card
{
	int   h;                                    //用以记录节点的h值，启发函数h取“不在位的将牌数”
	int   g;                                   
	int   f;
	int   Cardnum[3][3];              //用以记录将牌的具体的数码分布，用一个二维数组实现
   Card * parent1;                       //指向父节点的指针
   Card * parent2;                  //用于将节点加入一个节点链表如open表中

};
int  A[4]={-1,1,0,0};                         //给出不同的移位方案
int  B[4]={0,0,-1,1};
int CardGoal[3][3]={{1,2,3}, {8,0,4}, {7,6,5}};   //给出目标状态的数码分布


int getH(Card  * p)              //得到某一状态的h(n)的值，即不在位将牌数
{
	int count=0;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			if(p->Cardnum[i][j]!=CardGoal[i][j])
				count++;
		}
	return count;
}

int   getLoc0_i(Card  * p)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(p->Cardnum[i][j]==0)
              	return i;
}

int   getLoc0_j (Card  * p)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(p->Cardnum[i][j]==0)
              	return j;
}

void  copy(Card * p,Card * q)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
		{
			p->Cardnum[i][j]=q->Cardnum[i][j];
		}
}

bool  equ(Card *p,Card *q)
{
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			if(p->Cardnum[i][j]!=q->Cardnum[i][j])
				return false;
	 return true;
}

int  exist(Card *p,Card * q)        //返回的整数值为p未扩展前的 f值
{
    Card  *s=q;
    while(s!=NULL)
		 {
		   if(equ(s,p))
				return  s->f;
		   else
			   s=s->parent2;
		 }
		 return 0;
}

Card* del(Card * p,Card *q)
{
	Card * s=q;
	if(q!=NULL)
	{
			if(equ(p,q))       //要删除的状态在链表结尾
			{
				q=q->parent2;
				return  q;
			}
			else{
						while(q->parent2!=NULL)
						 {
							 if(equ(p,q->parent2))
							 {
								 q->parent2=q->parent2->parent2;
								 return  q;
							 }
							 q=q->parent2;
						 }
						 q=s;//恢复q
        			}
	}
	else return  NULL;
}

Card *  insert(Card *  p,Card * q)
{
	Card * s=q;
	if(q!=NULL){
			if(q->f<=p->f )
					{
						p->parent2=q;
						q=p;
					}
			else{
							while(q->parent2!=NULL && q->parent2->f>=p->f )
							{
								q=q->parent2;
							}
							p->parent2=q->parent2;
							q->parent2=p;
			         }
							q=s;
		 }
	else      	{q=p; }  
	return q;
}

void  display(Card *p)  // 从末节点开始定义输出链表内容的子函数，用于做测试
{
	Card  *s=p;
	if(s==NULL)
		return ;
	else{
		while(s!=NULL){
			    cout<<endl;
				count++;
			     for(int i=0;i<3;i++)
					{ 
						for(int j=0;j<3;j++)
						    cout<<s->Cardnum[i][j]<<" ";
					        cout<<endl;
					}
				 s=s->parent1;
		}
	}
}
void  display2(Card *p)  // 从末节点开始定义输出链表内容的子函数，用于做测试
{
	Card  *s=p;
	if(s==NULL)
		return ;
	else{
		while(s!=NULL){
			    cout<<endl;
			     for(int i=0;i<3;i++)
					{ 
						for(int j=0;j<3;j++)
						    cout<<s->Cardnum[i][j]<<" ";
					        cout<<endl;
					}
				 s=s->parent2;
		}
	}
}

Card * getfirst(Card *p)
{
	Card *s=p;
	if(s==NULL)
		return NULL;
    else{
		while(s->parent2!=NULL)
		{
			s=s->parent2;
		}
		return s;
	}
}

bool  issuc(Card *p)
{
	 if(getH(p)==0)                  //不在位将牌数为0，说明找到目标节点
			   {
					return true;
			   }
	 return false;
}

void getGoal(Card * beg)                  //求解解路径的子函数
{
	   bool getanswer=false;                                               
	   Card * openLast=beg;
	   Card * closedLast=NULL;     
	   while(openLast!=NULL)
	   {//while
		   Card *nowP=getfirst(openLast);             //nowP指向当前要扩展的节点
		    if(issuc(nowP)){
				cout<<"下面是最短路径，这里的输出顺序为目标节点第一个输出，初始节点最后输出，即逆序。"<<endl;
										display(nowP);
										cout<<"以上输出为逆序输出，total steps:"<<count-1<<endl;
										getanswer=true;break;}
            //从open 链表中移出要扩展的节点
		   if(openLast->parent2==NULL) 
			{
				openLast=NULL;
			}
			else              
			{
				Card * back=openLast;
				while(back->parent2!=getfirst(openLast))
				{
					back=back->parent2;
				}
				back->parent2=NULL;
			}
		 //将要扩展的节点移入closed表,closed表是无序的
			{
				nowP->parent2=closedLast;
				closedLast=nowP;
			}
		//扩展节点nowP
			int i=getLoc0_i(nowP);  //得到将牌中0的位置
			int j=getLoc0_j(nowP);                                 
			for(int  k=0;k<4;k++)
			{
				if(( i+A[k]>=0)&&(i+A[k]<=2)&&(j+B[k]>=0)&&(j+B[k]<=2))    //移位有效
				{
					Card * newNode=new Card;
					copy(newNode,nowP);                                    
					newNode->Cardnum[i][j]=nowP->Cardnum[i+A[k]][j+B[k]];
					newNode->Cardnum[i+A[k]][j+B[k]]=0;   
					int g=(nowP->g)+1;        //计算新节点的耗散值
					int h=getH(newNode);
					int f=g+h;
					//分情况讨论是否、如何修改指针
								if(exist(newNode,openLast)!=0)         //节点已为open表中的节点
								{
									if(f<exist(newNode,openLast))
									{
										newNode->f=f;
										newNode->g=g;
										newNode->h=h;
										newNode->parent1=nowP;
										newNode->parent2=NULL;
										openLast=del(newNode,openLast);
										openLast=insert(newNode,openLast);
									}
								}
								else  if(exist(newNode,closedLast)!=0)     //节点已为closed表中的节点
								{
									if(f<exist(newNode,closedLast))
									{
										newNode->f=f;
										newNode->g=g;
										newNode->h=h;
										newNode->parent1=nowP;
										newNode->parent2=NULL;
										closedLast=del(newNode,closedLast);
										openLast=insert(newNode,openLast);
									}
								} 
								else												//节点没有出现过                                             
								{
									newNode->f=f;
									newNode->g=g;
									newNode->h=h;									
									newNode->parent1=nowP;
									newNode->parent2=NULL;
									openLast=insert(newNode,openLast); 
								}
				}//if
			}//for
	   }//while

	   if(getfirst(openLast)==NULL&&!getanswer)
	   {
		   //失败处理，退出循环
		   cout<<"no solution"<<endl;
	   }
}//getGoal
int main()
{
	Card *   card_in=new Card;             //给出输入的将牌的节点
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
	            cin>>card_in->Cardnum [ i ][ j ];
	card_in->parent1=NULL;
	card_in->parent2=NULL;
	card_in->h=getH(card_in);
	card_in->g=0;
	card_in->f=card_in->h;
	getGoal(card_in);
	int a;
	cout<<"请输入一个任意整数以结束程序运行"<<endl;
	cin>>a;
	return 0;
}