main.cpp

根据人工智能中双向搜索的方法对8数码的问题进行解决

		{
			pCurNode->pChildNode[1]=pChildTemp;
			if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
				return pChildTemp;
		}
		pChildTemp=new NumNodeInfo;
		InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
		if(isExistedNode(pChildTemp,pSelfTreeRootNode))
			delete pChildTemp;
		else
		{
			pCurNode->pChildNode[2]=pChildTemp;
			if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
				return pChildTemp;
		}
		pChildTemp=new NumNodeInfo;
		InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
		if(isExistedNode(pChildTemp,pSelfTreeRootNode))
			delete pChildTemp;
		else
		{
			pCurNode->pChildNode[3]=pChildTemp;
			if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
				return pChildTemp;
		}
		return NULL;
	}
	
}
/************************************************************************/
/* 函数：从树的根节点便利，寻找在原树和目标树中都存在的节点，并把       */
/*		 整个路径中的节点入栈。根节点为栈底                             */
/* 参数：pDoubleNode为重复出现在2棵树中的节点，pTreeRootNode为树的      */
/*       根节点,pBottomStack为存储原树路径中节点的栈底                  */
/************************************************************************/
NodeStack * SearchNodeFromTree(NumNodeInfo *pDoubleNode,NumNodeInfo *pTreeRootNode)
{
	int tmp=0;
	NodeStack *pCurStack;
	NodeStack *pTempStack;
	NodeStack *pStacktmp=NULL;
//	NodeStack *pBottomStack;
	pCurStack=new NodeStack;	
	pCurStack->pNeededNode=pTreeRootNode;
	pCurStack->pNext=NULL;
	pTempStack=pCurStack;
	while(1)
	{
		if(isEqualNode(pCurStack->pNeededNode,pDoubleNode))
			break;
		if(tmp==4)
		{
			pTempStack=pCurStack;
			pCurStack=pTempStack->pNext;
			if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[0])
				tmp=1;
			else
				if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[1])
					tmp=2;
				else
					if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[2])
						tmp=3;
					else
						if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[3])
						{
							delete pTempStack;
							continue;
						}
			delete pTempStack;

		}
		pStacktmp=new NodeStack;
		pStacktmp->pNeededNode=NULL;
		pStacktmp->pNext=NULL;
		
		if(pCurStack->pNeededNode->pChildNode[tmp])
		{
			pStacktmp->pNeededNode=pCurStack->pNeededNode->pChildNode[tmp];
			tmp=0;
		}
		else
		{
			delete pStacktmp;
			tmp++;
			continue;
		}
		pStacktmp->pNext=pCurStack;
		pCurStack=pStacktmp;
	}
	return pCurStack;
}
/************************************************************************/
/* 函数：清除树结构                                                     */
/* 参数：pTreeRootNode为树的根节点										*/
/* 返回值：																*/
/************************************************************************/
bool TreeDestroy(NumNodeInfo *pTreeRootNode)
{
	if(pTreeRootNode==NULL)
		return true;
	else
		if(TreeDestroy(pTreeRootNode->pChildNode[0])&&TreeDestroy(pTreeRootNode->pChildNode[1])&&TreeDestroy(pTreeRootNode->pChildNode[2])&&TreeDestroy(pTreeRootNode->pChildNode[3]))
		{
			delete pTreeRootNode;
			return true;
		}
}
/************************************************************************/
/* 函数：清除栈结构                                                     */
/* 参数：pTopStack为栈底指针											*/
/************************************************************************/
void StackDestroy(NodeStack *pTopStack)
{
	NodeStack *pTmpStack;
	while(pTopStack)
	{
		pTmpStack=pTopStack;
		pTopStack=pTopStack->pNext;
		delete pTmpStack;
	}
}
/************************************************************************/
/* 函数：将树的所有最深的叶节点入栈                                     */
/* 参数：pTopStack所入的栈指针，pRootNode所搜索的树的根节点				*/
/************************************************************************/
NodeStack * PushToStack(NumNodeInfo *pRootNode)
{
	
	int tmp=0;
	NumNodeInfo *pTmpNode;
	NodeStack *pCurStack;
	NodeStack *pTempStack;
	NodeStack *pStacktmp=NULL;
	NodeStack *pTopStack=NULL;
	//自定义一个栈，用于存放遍历叶节点时的节点信息
	pCurStack=new NodeStack;
	pCurStack->pNeededNode=pRootNode;
	pCurStack->pNext=NULL;
	pTempStack=pCurStack;
	while(1)
	{
		
		if(tmp==4)
		{
			if(pCurStack->pNext==NULL)
			{
				pTmpNode=pCurStack->pNeededNode;
				if(pTmpNode->isActive&&pTmpNode->pChildNode[0]==NULL&&pTmpNode->pChildNode[1]==NULL&&pTmpNode->pChildNode[2]==NULL&&pTmpNode->pChildNode[3]==NULL)
				{
					pStacktmp=new NodeStack;
					pStacktmp->pNext=pTopStack;
					pStacktmp->pNeededNode=pTmpNode;
					pTopStack=pStacktmp;
				}
				delete pCurStack;
				break;
			}
			pTempStack=pCurStack;
			pCurStack=pTempStack->pNext;
			if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[0])
				tmp=1;
			else
				if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[1])
					tmp=2;
				else
					if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[2])
						tmp=3;
					else
						if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[3])
						{
							pTmpNode=pTempStack->pNeededNode;
							if(pTmpNode->isActive&&pTmpNode->pChildNode[0]==NULL&&pTmpNode->pChildNode[1]==NULL&&pTmpNode->pChildNode[2]==NULL&&pTmpNode->pChildNode[3]==NULL)
							{
								pStacktmp=new NodeStack;
								pStacktmp->pNext=pTopStack;
								pStacktmp->pNeededNode=pTmpNode;
								pTopStack=pStacktmp;
							}
							delete pTempStack;
							continue;
						}
			pTmpNode=pTempStack->pNeededNode;
			if(pTmpNode->isActive&&pTmpNode->pChildNode[0]==NULL&&pTmpNode->pChildNode[1]==NULL&&pTmpNode->pChildNode[2]==NULL&&pTmpNode->pChildNode[3]==NULL)
			{
				pStacktmp=new NodeStack;
				pStacktmp->pNext=pTopStack;
				pStacktmp->pNeededNode=pTmpNode;
				pTopStack=pStacktmp;
			}
			delete pTempStack;
					
		}
		pStacktmp=new NodeStack;
		pStacktmp->pNeededNode=NULL;
		pStacktmp->pNext=NULL;
		
		if(pCurStack->pNeededNode->pChildNode[tmp])
		{
			pStacktmp->pNeededNode=pCurStack->pNeededNode->pChildNode[tmp];
			tmp=0;
		}
		else
		{
			delete pStacktmp;
			tmp++;
			continue;
		}
		pStacktmp->pNext=pCurStack;
		pCurStack=pStacktmp;
	
	}
	return pTopStack;	
}
/************************************************************************/
/* 函数：寻找节点的父节点                                               */
/* 参数：pCurNode为当前节点，pParNode为传出的当前节点的父节点,			*/
/*		 pTreeRootNode为当前节点所在树的根节点					        */
/************************************************************************/
NumNodeInfo * SearchParNode(NumNodeInfo *pCurNode,NumNodeInfo *pTreeRootNode)
{
	NumNodeInfo *pParNode;
	if(pCurNode==pTreeRootNode)
	{
		pParNode=NULL;
		return pParNode;
	}
	int tmp=0;
	//NumNodeInfo *pTmpNode;
	NodeStack *pCurStack;
	NodeStack *pTempStack;
	NodeStack *pStacktmp=NULL;

	//自定义一个栈，用于存放遍历叶节点时的节点信息
	pCurStack=new NodeStack;
	pCurStack->pNeededNode=pTreeRootNode;
	pCurStack->pNext=NULL;
	pTempStack=pCurStack;
	int i;
	for(i=0;i<4;i++)
		if(pCurStack->pNeededNode->pChildNode[i]==pCurNode)
		{
			pParNode=pCurStack->pNeededNode;
			StackDestroy(pCurStack);
			return pParNode;
		}
	while(1)
	{
		
		if(tmp==4)
		{
			pTempStack=pCurStack;
			pCurStack=pTempStack->pNext;
			if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[0])
				tmp=1;
			else
				if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[1])
					tmp=2;
				else
					if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[2])
						tmp=3;
					else
						if(pTempStack->pNeededNode==pCurStack->pNeededNode->pChildNode[3])
						{
							delete pTempStack;
							continue;
						}
						delete pTempStack;
						
		}
		pStacktmp=new NodeStack;
		pStacktmp->pNeededNode=NULL;
		pStacktmp->pNext=NULL;
		
		if(pCurStack->pNeededNode->pChildNode[tmp])
		{
			pStacktmp->pNeededNode=pCurStack->pNeededNode->pChildNode[tmp];
			for(i=0;i<4;i++)
				if(pCurStack->pNeededNode->pChildNode[i]==pCurNode)
				{
					pParNode=pCurStack->pNeededNode;
					StackDestroy(pCurStack);
					return pParNode;
				}
			tmp=0;
		}
		else
		{
			delete pStacktmp;
			tmp++;
			continue;
		}
		pStacktmp->pNext=pCurStack;
		pCurStack=pStacktmp;
		
	}
		
}
int main()
{
	int i,j;
	//定义2棵树的根节点
	NumNodeInfo *pOriTreeRootNode,*pDesTreeRootNode;
	//对输入获取用户的原状态和目标状态
	cout<<"请输入初始状态，空格为0"<<endl;
	pOriTreeRootNode=new NumNodeInfo;
	pOriTreeRootNode->isActive=true;
	for(i=0;i<4;i++)
		pOriTreeRootNode->pChildNode[i]=NULL;
	for(i=0;i<SqureEdge;i++)
		for(j=0;j<SqureEdge;j++)
			cin>>pOriTreeRootNode->NumEle[i][j];
	cout<<"输入的初始状态为："<<endl;
	for(i=0;i<SqureEdge;i++)
	{
		for(j=0;j<SqureEdge;j++)
			cout<<pOriTreeRootNode->NumEle[i][j]<<" ";
		cout<<endl;
	}
	cout<<endl<<"请输入目标状态，空格为0"<<endl;
	pDesTreeRootNode=new NumNodeInfo;
	pDesTreeRootNode->isActive=true;
	for(i=0;i<4;i++)
		pDesTreeRootNode->pChildNode[i]=NULL;
	for(i=0;i<SqureEdge;i++)
		for(j=0;j<SqureEdge;j++)
			cin>>pDesTreeRootNode->NumEle[i][j];
	cout<<"输入的目标状态为："<<endl;
	for(i=0;i<SqureEdge;i++)
	{
		for(j=0;j<SqureEdge;j++)
			cout<<pDesTreeRootNode->NumEle[i][j]<<" ";
		cout<<endl;
	}

	if(isEqualNode(pOriTreeRootNode,pDesTreeRootNode))
	{
		cout<<endl<<"无需走动"<<endl;
		return 0;

	}

	int RevNum1=0,RevNum2=0;
	int m,n;
	int ii,jj;
	for(i=0;i<SqureEdge;i++)
		for(j=0;j<SqureEdge;j++)
		{
			if(j<-1)
			{
				m=i;
				n=j+1;
			}
			else
			{
				m=i+1;
				n=0SqureEdge;
			}
			for(ii=m;ii<SqureEdge;ii++)
			{
				if(ii!=m)
					n=0;
				for(jj=n;jj<SqureEdge;jj++)
					if(pDesTreeRootNode->NumEle[i][j]>pDesTreeRootNode->NumEle[ii][jj]&&pDesTreeRootNode->NumEle[i][j]!='0'&&pDesTreeRootNode->NumEle[ii][jj]!='0')
						RevNum1++;
			}
		}
	for(i=0;i<SqureEdge;i++)
		for(j=0;j<SqureEdge;j++)
		{
			if(j<SqureEdge-1)
			{
				m=i;
				n=j+1;
			}
			else
			{
				m=i+1;
				n=0;
			}
			for(ii=m;ii<SqureEdge;ii++)
			{
				if(ii!=m)
					n=0;
				for(jj=n;jj<SqureEdge;jj++)
					if(pOriTreeRootNode->NumEle[i][j]>pOriTreeRootNode->NumEle[ii][jj]&&pOriTreeRootNode->NumEle[i][j]!='0'&&pOriTreeRootNode->NumEle[ii][jj]!='0')
						RevNum2++;
			}
		}
	if((RevNum1%2!=0&&RevNum2==0)||(RevNum1%2==0&&RevNum2%2!=0))
	{
		cout<<endl<<"无解"<<endl;
		return 0;
	}
	NumNodeInfo *pParNode=NULL;//当前节点的父节点的指针
	NumNodeInfo *pDoubleNode=NULL;//在两棵树中都出现的节点指针
//	NumNodeInfo *pCurOriNode,*pCurDesNode;
//	pCurOriNode=pOriTreeRootNode;
//	pCurDesNode=pDesTreeRootNode;
	//在建树时所使用的栈
	NodeStack *pCurStack=NULL;
	NodeStack *pTmpStack=NULL;
	//建立树结构
	while(1)
	{
		pCurStack=PushToStack(pOriTreeRootNode);	
		while(pCurStack!=NULL)
		{
			pParNode=SearchParNode(pCurStack->pNeededNode,pOriTreeRootNode);
			pDoubleNode=BuildChildNode(pCurStack->pNeededNode,pParNode,pOriTreeRootNode,pDesTreeRootNode);
			if(pDoubleNode!=NULL)
				break;
			pTmpStack=pCurStack;
			pCurStack=pCurStack->pNext;
			delete pTmpStack;
		}
		if(pDoubleNode!=NULL)
			break;
		pCurStack=PushToStack(pDesTreeRootNode);	
		while(pCurStack!=NULL)
		{
			pParNode=SearchParNode(pCurStack->pNeededNode,pDesTreeRootNode);
			pDoubleNode=BuildChildNode(pCurStack->pNeededNode,pParNode,pDesTreeRootNode,pOriTreeRootNode);
			if(pDoubleNode!=NULL)
				break;
			pTmpStack=pCurStack;
			pCurStack=pCurStack->pNext;
			delete pTmpStack;
		}
		if(pDoubleNode!=NULL)
			break;		
	}

	NodeStack *pSaveStack1=NULL,*pSaveStack2=NULL;
	pSaveStack1=SearchNodeFromTree(pDoubleNode,pOriTreeRootNode);
	pSaveStack2=SearchNodeFromTree(pDoubleNode,pDesTreeRootNode);
	pTmpStack=pSaveStack1;
	pSaveStack1=pSaveStack1->pNext;
	delete pTmpStack;
	while(pSaveStack1)
	{
		pTmpStack=pSaveStack1;
		pSaveStack1=pSaveStack1->pNext;
		pTmpStack->pNext=pSaveStack2;
		pSaveStack2=pTmpStack;
	}

	cout<<endl;
	cout<<"结果为："<<endl;
	int Num=1;
	while(pSaveStack2!=NULL)
	{
		cout<<Num<<endl;
		for(i=0;i<SqureEdge;i++)
		{
			for(j=0;j<SqureEdge;j++)
				cout<<pSaveStack2->pNeededNode->NumEle[i][j]<<" ";
			cout<<endl;
		}
		Num++;
		cout<<endl;
		pTmpStack=pSaveStack2;
		pSaveStack2=pSaveStack2->pNext;
		delete pTmpStack;
	}
	TreeDestroy(pOriTreeRootNode);
	TreeDestroy(pDesTreeRootNode);
	return 0;
}
//测试
//初始状态：
//1 4 8
//2 5 7
//0 3 6
//目标状态:
//1 2 3
//4 5 6
//7 8 0