mco.cpp

人工智能中经典问题

/************************************************************************/
/* MCO.cpp																*/
/* Solution for the missionaries and cannibals problem					*/
/* Author: Zheng Zhong													*/
/* 2008-03-30                                                           */
/************************************************************************/
#include <iostream.h>
#include <stdio.h>
#include <math.h>
struct state{
	int nM;			//The missionaries on the left side
	int nC;			//The cannibals on the left side
	bool B;			//The boat is on the left side if B==TRUE
	state *par;		//The pointer of father of the  node
	int h;			//The value of the evaluation function
	bool visted;	//The node has been expanded if visted==TRUE
	int depth;		//The depth of the node
};
int find();
bool expand(state *now);
bool addNode(int x,int y,state * now);
bool addIt(state *it);
int calcu(state *it);
void printAnswer(state *toExpand);
void delet();
state *list[100000];
int nodeNum=1;
int m,c,boat,n=0;
void main()
{
	freopen("1.in","r",stdin);
	cout<<"Please Enter 3 numbers:"<<endl;
	cout<<"(the number of missionaries and cannibals and number of people boat can take)"<<endl;
	while(cin>>m>>c>>boat){
		nodeNum=1;
		cout<<endl;
		n++;
		cout<<"CASE "<<n<<":"<<endl;
	state *orginal=new state;
	state *toExpand;
	int tt;
	orginal->nM=m;
	orginal->nC=c;
	orginal->visted=0;
	orginal->par=0;
	orginal->B=1;
	orginal->depth=0;
	list[0]=orginal;
	while(1)
	{
		tt=find();
		if(tt<0) {
			delet();
			cout<<"no solution!"<<endl;
			break;
		}
		else toExpand=list[tt];
		if (toExpand->nC==0&&toExpand->nM==0&&toExpand->B==0)
		{
			break;
		}		
		expand(toExpand);
	}
	if(tt>=0) {
		printAnswer(toExpand);
		delet();
	}
	}
	
}
/***Delete all the memory that applied for dynamically**/
void delet()
{
	for (int i=0;i<nodeNum;i++)
	{
		delete list[i];
	}

}
/***Find the node that have the smallest evaluation value**/
int find()
{
	int k=0,temp=-1;
	int max=10000;
	for(k=0;k<nodeNum;k++)
	{
		if((list[k]->visted!=1)&&list[k]->h<max){
			temp=k;
			max=list[k]->h;
		}
	}
	return temp;
}
/*** Expand the node ***/
bool expand(state *now)
{
	bool flag=0;
	for (int i=0;i<=boat;i++)
		for(int j=0;i+j<=boat;j++)
		{
			
			if(addNode(i,j,now)) flag=1;
		}
	now->visted=1;
	return flag;

}
/******Add the node to the node list******/
bool addNode(int x,int y,state *now)
{
	state *next;
	bool flag=0;	
	if (now->B)//The boat is on the left side
	{
		if (((now->nM-x)>=0 &&(now->nC-y)>=0 )//Number of the people >=0
			&&(x+y>0)//At least one people to drive the boat
			//Missionaries and on the boat never eaten by cannibals
			&&(x==0 ||x>=y) 
			//Missionaries and on the left side never eaten by cannibals
			&& ((now->nM-x)==0||(now->nM-x)>=(now->nC-y))
			//Missionaries and on the right side never eaten by cannibals
			&&(((m-now->nM+x)==0)||(m-now->nM+x)>=(c-now->nC+y)))
		{
			next=new state;
			next->nM=now->nM-x;
			next->nC=now->nC-y;
			next->par=now;
			next->B=0;
			next->depth=now->depth+1;
			if(addIt(next)) flag=1;
		}
	}
	else{	//The boat is on the right side
		if (((now->nM+x)<=m)&&(now->nC+y)<=c //Number of the people >=0
			&&(x+y>0)//At least one people to drive the boat
			//Missionaries and on the boat never eaten by cannibals
			&&(x==0 ||x>=y) 
			////Missionaries and on the right side never eaten by cannibals
			&& ((m-now->nM-x)==0||(m-now->nM-x)>=(c-now->nC-y))
			//Missionaries and on the left side never eaten by cannibals
			&&(((now->nM+x)==0)||(now->nM+x)>=(now->nC+y)))
		{
			next=new state;
			next->nM=now->nM+x;
			next->nC=now->nC+y;
			next->par=now;
			next->B=1;
			next->depth=now->depth+1;
			if(addIt(next)) flag=1;
		}
	}
	return flag;
}
/***If the node is not in the list, add it into the list***/
bool addIt(state *it)
{
	for (int i=0;i<nodeNum;i++)
	{
		if(list[i]->nM==it->nM &&list[i]->nC==it->nC &&list[i]->B==it->B) 
			return 0;
	}
	it->h=calcu(it);
	list[nodeNum++]=it;
	return 1;
}

/*****Calculate the value of evaluation function*****/
int calcu(state *it) 
{
	if(it->B){
		return (int)ceil((2*(it->nM+it->nC)-(boat+1))/(double)(boat-1))+it->depth;
	}
	else return (int)ceil((2*(it->nM+it->nC))/(double)(boat-1))+it->depth;

}
/***Print the procedure of solving the problem**/ 
void printAnswer(state *toExpand){
	if(toExpand==0) return;
	state *t=toExpand->par;		
	printAnswer(t);
	cout<<"< "<<toExpand->nM<<" , "<<toExpand->nC<<" , "<<toExpand->B<<" >"<<endl;
}