main.cpp

用C++解决人工智能中经典的强盗和商人过河的问题

#include <iostream>
using namespace std;
/************************************************************************/
/* 三个土匪，三个强盗在河岸A，要到河岸B。                               */
/* 条件1：河的任一一边，如果有商人，则商人数必须大于等于土匪人数		*/
/* 条件2：有一条船可行驶于河上，但改船最多可载人2人						*/
/************************************************************************/
struct Gan_BusiNode 
{
	char ShoreA[2];//0为土匪的人数，1为商人的人数。
	char ShoreB[2];//0为土匪的人数，1为商人的人数。
	char BoatPos;//船当前在河的哪一边
	Gan_BusiNode * pChildNode[5];
	bool isActive;//节点是否符合条件1
};
struct NodeStack
{
	Gan_BusiNode *pNeededNode;
	NodeStack *pNext;
};
/************************************************************************/
/* 函数：检测所提供的节点是否符合条件1                                  */
/* 参数：GBNode为所检测的状态节点										*/
/* 返回值：如果为true，则表示节点pGBNode符合条件1，如果为false，则不符合	*/
/************************************************************************/
bool isAcceptable(Gan_BusiNode *pGBNode)
{
	if((pGBNode->ShoreA[1]>0&&pGBNode->ShoreA[0]>pGBNode->ShoreA[1])||(pGBNode->ShoreB[1]>0&&pGBNode->ShoreB[0]>pGBNode->ShoreB[1]))
		return false;
	return true;
}
/************************************************************************/
/* 函数：做赋值运算，将pOriNode的内容赋给pDesNode，不包括指针值和船信息 */
/* 参数：pDesNode为被赋值的节点指针，pOriNode为含有值得节点指针			*/
/************************************************************************/
void Evaluate(Gan_BusiNode *pDesNode,Gan_BusiNode *pOriNode)
{
	pDesNode->BoatPos=pOriNode->BoatPos;
	pDesNode->isActive=true;
	for(int i=0;i<2;i++)
	{
		pDesNode->ShoreA[i]=pOriNode->ShoreA[i];
		pDesNode->ShoreB[i]=pOriNode->ShoreB[i];
	}
}
/************************************************************************/
/* 函数：判断是否节点为最终的节点状态                                   */
/* 参数：pNode为所被检测的节点指针										*/
/* 返回值：如果为最终节点状态，返回true，否则返回false					*/
/************************************************************************/
bool isEqualtoDes(Gan_BusiNode * pNode)
{
	if(pNode->ShoreA[0]==0&&pNode->ShoreA[1]==0&&pNode->ShoreB[0]==3&&pNode->ShoreB[1]==3)
		return true;
	return false;
}
/************************************************************************/
/* 函数：清空节点的子节点指针为NULL                                     */
/* 参数：pNode为节点指针												*/
/************************************************************************/
void EmptyChildPointer(Gan_BusiNode *pNode)
{
	for(int i=0;i<5;i++)
		pNode->pChildNode[i]=NULL;
}
/************************************************************************/
/* 函数：移动商人和土匪到河的另一边                                     */
/* 参数：busiman为移动的商人的人数，gangster为移动的土匪的人数,pNode为	*/
/*		 当前状态的节点,pChildNode为所找子节点指针						*/
/************************************************************************/
void MovePerson(int busiman,int gangster,Gan_BusiNode *pCurNode,Gan_BusiNode *pChildNode)
{
	EmptyChildPointer(pChildNode);
	Evaluate(pChildNode,pCurNode);
	if (pCurNode->BoatPos=='A')
	{
		pChildNode->ShoreA[0]-=gangster;
		pChildNode->ShoreA[1]-=busiman;
		pChildNode->ShoreB[0]+=gangster;
		pChildNode->ShoreB[1]+=busiman;
		pChildNode->BoatPos='B';
	}
	else
	{
		pChildNode->ShoreB[0]-=gangster;
		pChildNode->ShoreB[1]-=busiman;
		pChildNode->ShoreA[0]+=gangster;
		pChildNode->ShoreA[1]+=busiman;
		pChildNode->BoatPos='A';
	}
}
/************************************************************************/
/* 函数：递归删除树结构                                                 */
/* 参数：pRootNode为临时的父节点										*/
/************************************************************************/
void DestroyTree(Gan_BusiNode *pParNode)
{
	if(pParNode==NULL)
		return;
	else
	{
		DestroyTree(pParNode->pChildNode[0]);
		DestroyTree(pParNode->pChildNode[1]);
		DestroyTree(pParNode->pChildNode[2]);
		DestroyTree(pParNode->pChildNode[3]);
		DestroyTree(pParNode->pChildNode[4]);
		delete pParNode;
	}
}
/************************************************************************/
/* 函数：根据提供的节点指针构建该节点的子节点                           */
/* 参数：pCurNode为提供的节点，pRootNode为整个结构的根节点				*/
/* 返回值：如果为true，表示3个商人都到达河对岸，否则为false				*/
/************************************************************************/
bool BuildChildStruct(Gan_BusiNode *pCurNode)//,Gan_BusiNode *pRootNode)
{
	int gang;
	int busi;
	int time=0;
	Gan_BusiNode *pTmpNode=NULL;
	for(gang=0;gang<3;gang++)
		for(busi=0;busi<3;busi++)
			if((gang!=0||busi!=0)&&busi+gang<=2)
			{
				if(pCurNode->BoatPos=='A')
				{
					if(gang<=pCurNode->ShoreA[0]&&busi<=pCurNode->ShoreA[1])
					{
						pTmpNode=new Gan_BusiNode;
						MovePerson(busi,gang,pCurNode,pTmpNode);
						if(!isAcceptable(pTmpNode))
						{
							delete pTmpNode;
							continue;
						}
						pCurNode->pChildNode[time]=pTmpNode;
						pTmpNode->BoatPos='B';
						if(isEqualtoDes(pTmpNode))
							return true;
						time++;
					}
				}
				else
				{
					if(gang<=pCurNode->ShoreB[0]&&busi<=pCurNode->ShoreB[1])
					{
						pTmpNode=new Gan_BusiNode;
						MovePerson(busi,gang,pCurNode,pTmpNode);
						if(!isAcceptable(pTmpNode))
						{
							delete pTmpNode;
							continue;
						}
						pCurNode->pChildNode[time]=pTmpNode;
						pTmpNode->BoatPos='A';
						time++;
					}
				}
			}
	if(time==0)
		pCurNode->isActive=false;
	return false;
}
/************************************************************************/
/* 函数：将树中所有激活的也节点入栈                                     */
/* 参数：pRootNode为树的根节点指针										*/
/* 返回值：返回值为所有激活叶节点的栈的栈顶指针							*/
/************************************************************************/
NodeStack *PushActiveToStack(Gan_BusiNode * pRootNode)
{
	NodeStack *pTopStack;//临时存储搜索过程中的节点的栈指针
	Gan_BusiNode *pTmpNode;
	NodeStack *pTmpStack;
	NodeStack *pStack;
	NodeStack *pActiveNodeStack=NULL;//存储树中为激活状态的叶节点的指针
	Gan_BusiNode *pCurNode=pRootNode;
	pTopStack=new NodeStack;
	pTopStack->pNeededNode=pRootNode;
	pTopStack->pNext=NULL;
	int timer=0;
	while(1)
	{
		if(timer==5)
		{
			if(pTopStack->pNext==NULL)
			{
				pTmpNode=pTopStack->pNeededNode;
				if(pTmpNode->isActive&&pTmpNode->pChildNode[0]==NULL&&pTmpNode->pChildNode[1]==NULL&&pTmpNode->pChildNode[2]==NULL&&pTmpNode->pChildNode[3]==NULL&&pTmpNode->pChildNode[4]==NULL)
				{
					pTmpStack=new NodeStack;
					pTmpStack->pNext=pActiveNodeStack;
					pTmpStack->pNeededNode=pTmpNode;
					pActiveNodeStack=pTmpStack;
				}
				delete pTopStack;
				break;
			}
			pTmpStack=pTopStack;
			pTopStack=pTopStack->pNext;
			if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[0])
				timer=1;
			else
				if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[1])
					timer=2;
				else
					if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[2])
						timer=3;
					else
						if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[3])
							timer=4;
						else
							if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[4])
							{
								pTmpNode=pTmpStack->pNeededNode;
								if(pTmpNode->isActive&&pTmpNode->pChildNode[0]==NULL&&pTmpNode->pChildNode[1]==NULL&&pTmpNode->pChildNode[2]==NULL&&pTmpNode->pChildNode[3]==NULL&&pTmpNode->pChildNode[4]==NULL)
								{
									pStack=new NodeStack;
									pStack->pNext=pActiveNodeStack;
									pStack->pNeededNode=pTmpNode;
									pActiveNodeStack=pStack;
								}
								delete pTmpStack;
								continue;
							}
			pTmpNode=pTmpStack->pNeededNode;
			if(pTmpNode->isActive&&pTmpNode->pChildNode[0]==NULL&&pTmpNode->pChildNode[1]==NULL&&pTmpNode->pChildNode[2]==NULL&&pTmpNode->pChildNode[3]==NULL&&pTmpNode->pChildNode[4]==NULL)
			{
				pStack=new NodeStack;
				pStack->pNext=pActiveNodeStack;
				pStack->pNeededNode=pTmpNode;
				pActiveNodeStack=pStack;
			}
			delete pTmpStack;
		}
		pTmpStack=new NodeStack;
		pTmpStack->pNeededNode=NULL;
		pTmpStack->pNext=NULL;
		if(pTopStack->pNeededNode->pChildNode[timer])
		{
			pTmpStack->pNeededNode=pTopStack->pNeededNode->pChildNode[timer];
			timer=0;
		}
		else
		{
			delete pTmpStack;
			timer++;
			continue;
		}
		pTmpStack->pNext=pTopStack;
		pTopStack=pTmpStack;
	}
	return pActiveNodeStack;
}
/************************************************************************/
/* 函数：施放栈中的内容                                                 */
/* 参数：pTopStack为栈顶指针											*/
/************************************************************************/
void DestroyStack(NodeStack *pTopStack)
{
	NodeStack *pTmpStack;
	while(pTopStack)
	{
		pTmpStack=pTopStack;
		pTopStack=pTopStack->pNext;
		delete pTmpStack;
	}

}

/************************************************************************/
/* 函数：从树中将到达最终状态的所有中间节点全部提取出来，并推入栈中     */
/* 参数：pRootNode为树的根节点											*/
/* 返回值：返回值为保存所有到达最终状态的中间节点的栈的栈顶指针			*/
/************************************************************************/
NodeStack *ExtractPathNode(Gan_BusiNode *pRootNode)
{
	NodeStack *pTopStack;//保存从根节点到最终节点的中间节点的栈顶指针
//	Gan_BusiNode *pTmpNode;//节点中间变量
	NodeStack *pTmpStack;//栈中间变量
//	Gan_BusiNode *pCurNode=pRootNode;//保存在搜索过程中的当前节点的指针
	pTopStack=new NodeStack;
	pTopStack->pNeededNode=pRootNode;
	pTopStack->pNext=NULL;
	int timer=0;
	while(1)
	{
		if(timer==5)
		{
			pTmpStack=pTopStack;
			pTopStack=pTopStack->pNext;
			if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[0])
				timer=1;
			else
				if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[1])
					timer=2;
				else
					if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[2])
						timer=3;
					else
						if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[3])
							timer=4;
						else
							if(pTmpStack->pNeededNode==pTopStack->pNeededNode->pChildNode[4])
							{
								timer=5;
								delete pTmpStack;
								continue;
							}
			delete pTmpStack;
		}
		pTmpStack=new NodeStack;
		pTmpStack->pNeededNode=NULL;
		pTmpStack->pNext=NULL;
		if(pTopStack->pNeededNode->pChildNode[timer]&&pTopStack->pNeededNode->pChildNode[timer]->isActive)
		{
			pTmpStack->pNeededNode=pTopStack->pNeededNode->pChildNode[timer];
			timer=0;
		}
		else
		{
			delete pTmpStack;
			timer++;
			continue;
		}
		pTmpStack->pNext=pTopStack;
		pTopStack=pTmpStack;
		if(isEqualtoDes(pTopStack->pNeededNode))
			return pTopStack;
	}
}
int main()
{
	//定义根节点
	Gan_BusiNode *pRootNode;
	pRootNode=new Gan_BusiNode;
	pRootNode->BoatPos='A';
	pRootNode->isActive=true;
	EmptyChildPointer(pRootNode);
	pRootNode->ShoreA[0]=3;
	pRootNode->ShoreA[1]=3;
	pRootNode->ShoreB[0]=0;
	pRootNode->ShoreB[1]=0;
	//定义存放树的叶节点的栈
	NodeStack *pTopNodeStack;
	NodeStack *pTmpStack;
	Gan_BusiNode *pTmpNode;
	bool isSucceeded=NULL;
	while(1)
	{
		pTopNodeStack=PushActiveToStack(pRootNode);
		while(pTopNodeStack)
		{
			pTmpNode=pTopNodeStack->pNeededNode;
			isSucceeded=BuildChildStruct(pTmpNode);
			pTmpStack=pTopNodeStack;
			pTopNodeStack=pTopNodeStack->pNext;
			delete pTmpStack;
			if(isSucceeded)
			{
				break;
			}
		}
		if(isSucceeded)
			break;
	}
	DestroyStack(pTopNodeStack);
	NodeStack *pTopTmpStack=NULL;
	pTopTmpStack=ExtractPathNode(pRootNode);
	pTopNodeStack=NULL;
	while(pTopTmpStack)
	{
		pTmpStack=pTopTmpStack;
		pTopTmpStack=pTopTmpStack->pNext;
		pTmpStack->pNext=pTopNodeStack;
		pTopNodeStack=pTmpStack;
	}
	while(pTopNodeStack)
	{
		cout<<"gangster   : "<<(int)pTopNodeStack->pNeededNode->ShoreA[0]<<" ---> "<<(int)pTopNodeStack->pNeededNode->ShoreB[0]<<endl;
		cout<<"businessman: "<<(int)pTopNodeStack->pNeededNode->ShoreA[1]<<" ---> "<<(int)pTopNodeStack->pNeededNode->ShoreB[1]<<endl;
		cout<<endl<<endl;
		pTmpStack=pTopNodeStack;
		pTopNodeStack=pTopNodeStack->pNext;
		delete pTmpStack;
	}
	DestroyTree(pRootNode);
	return 0;
}