main.cpp

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

#include <iostream>
#define SqureEdge 3
using namespace std;
struct NumNodeInfo
{
	char NumEle[SqureEdge][SqureEdge];//由数字1、2、3、4、5、6、7、8、0构成，0代表空值
	NumNodeInfo *pChildNode[4];
	bool isActive;//是否激活
};
//栈用于存储最终搜寻到的路径中的节点指针
struct NodeStack
{
	NumNodeInfo *pNeededNode;
	NodeStack *pNext;
};
/************************************************************************/
/* 函数：初始化节点指针                                                 */
/* 参数：OriPosx,OriPoy为原节点的0的坐标,DesPosx,DesPosy                */
/*       为目标位置0的坐标,pOriNode为原节点指针,pDesNode为目标节点指针  */
/************************************************************************/
void InitNode(int OriPosx,int OriPosy,int DesPosx,int DesPosy,NumNodeInfo *pOriNode,NumNodeInfo *pDesNode)
{
	char temp;
	int i,j;
	for(i=0;i<4;i++)
		pDesNode->pChildNode[i]=NULL;
	pDesNode->isActive=true;
	for(i=0;i<SqureEdge;i++)
		for(j=0;j<SqureEdge;j++)
			pDesNode->NumEle[i][j]=pOriNode->NumEle[i][j];
	temp=pDesNode->NumEle[DesPosx][DesPosy];
	pDesNode->NumEle[DesPosx][DesPosy]=pDesNode->NumEle[OriPosx][OriPosy];
	pDesNode->NumEle[OriPosx][OriPosy]=temp;
}
/************************************************************************/
/* 函数：判断两个节点的内容是否一致                                     */
/* 参数：*/
/* 返回值：如果一致返回true，否则返回false                              */
/************************************************************************/
bool isEqualNode(NumNodeInfo *pNodeA,NumNodeInfo *pNodeB)
{
	int i,j;
	for(i=0;i<SqureEdge;i++)
		for(j=0;j<SqureEdge;j++)
			if(pNodeA->NumEle[i][j]!=pNodeB->NumEle[i][j])
				return false;
	return true;
}

/************************************************************************/
/* 函数：检测所要增加的节点是否已出现过                                 */
/* 参数：pTestNode为被检测的节点指针,pTreeParNode为树结构的父节点      */
/* 返回值：如果已出现过返回true，否则返回false                          */
/************************************************************************/
bool isExistedNode(NumNodeInfo *pTestNode,NumNodeInfo *pTreeParNode)
{
	if(pTreeParNode==NULL)
		return false;
	if(isEqualNode(pTestNode,pTreeParNode))
		return true;
	else
		if((pTreeParNode->pChildNode[0]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[0]))||(pTreeParNode->pChildNode[1]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[1]))
			||(pTreeParNode->pChildNode[2]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[2]))||(pTreeParNode->pChildNode[3]&&isExistedNode(pTestNode,pTreeParNode->pChildNode[3])))
			return true;
		else
			return false;
}


/************************************************************************/
/* 函数：构建当前节点的子节点                                           */
/* 参数：CurNode 为当前节点指针，ParNode为但钱节点的父节点指针,         */
/*       pSelfTreeRootNode为当前树的根节点,pNeighborTreeRootNode为同步的*/
/*       邻树的根节点                                                   */
/* 返回值：如果所增加的节点在邻树中存在,则返回共同存在的2个节点中的一个 */
/*         否则返回NULL													*/
/************************************************************************/
NumNodeInfo* BuildChildNode(NumNodeInfo *pCurNode,NumNodeInfo *pParNode,NumNodeInfo *pSelfTreeRootNode,NumNodeInfo *pNeighborTreeRootNode)
{
	char temp[SqureEdge][SqureEdge];
	int i,j;
	int posx,posy;
	for(i=0;i<SqureEdge;i++)
		for(j=0;j<SqureEdge;j++)
			if(pCurNode->NumEle[i][j]=='0')
			{
				posx=i;
				posy=j;
			}
	NumNodeInfo *pChildTemp;
	if(pParNode!=NULL)
	{
		for(i=0;i<SqureEdge;i++)
			for(j=0;j<SqureEdge;j++)
				temp[i][j]=pParNode->NumEle[i][j];
		if (posx==0&&posy==0)
		{
			if(temp[posx][posy+1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx+1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
		}
		if (posx==0&&posy==SqureEdge-1)
		{
			if(temp[posx][posy-1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx+1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
		}
		if (posx==SqureEdge-1&&posy==SqureEdge-1)
		{
			if(temp[posx-1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx][posy-1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
		}

		if (posx==SqureEdge-1&&posy==0)
		{
			if(temp[posx][posy+1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx-1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
		}


		if(posx==0)
		{
			if(temp[posx][posy-1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx+1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=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[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx][posy+1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
		}
		if(posy==0)
		{
			if(temp[posx-1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy+1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx][posy+1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx+1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx+1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=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[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
		}
		if(posx==SqureEdge-1)
		{
			if(temp[posx][posy-1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=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[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx-1][posy]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=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[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;
				return NULL;
			}
			if(temp[posx][posy+1]=='0')
			{
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx,posy-1,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[0]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				pChildTemp=new NumNodeInfo;
				InitNode(posx,posy,posx-1,posy,pCurNode,pChildTemp);
				if(isExistedNode(pChildTemp,pSelfTreeRootNode))
					delete pChildTemp;
				else
				{
					pCurNode->pChildNode[1]=pChildTemp;
					if(isExistedNode(pChildTemp,pNeighborTreeRootNode))
						return pChildTemp;
				}
				if(pCurNode->pChildNode[0]==NULL&&pCurNode->pChildNode[1]==NULL)
					pCurNode->isActive=false;