mcprob.cpp

人工智能实验---求解传教士与野人问题,并画出状态图做动态演示.

// MCProb.cpp: implementation of the MCProb class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "MCProc.h"
#include "MCProb.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

MCProb::MCProb()
{

}

MCProb::~MCProb()
{
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>释放空间
	ReleaseG();
	ReleaseSpace(OPEN);
	ReleaseSpace(CLOSE);
}

void MCProb::Init()
{
	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>初始化数据
	G=NULL;
	OPEN=NULL;
	CLOSE=NULL;
	GCur=NULL;
	OCur=NULL;
	CCur=NULL;
	path=NULL;
	pOper=NULL;	
	ops=0;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>生成状态节点
State* MCProb::GenState(int m,int c,bool b,int cost,State* parent)
{
	State* pstate=new State;
	pstate->m=m;
	pstate->c=c;
	pstate->b=b;
	pstate->cost=cost;
	pstate->parent=parent;
	
	return pstate;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
//( m , c , b )=============>( i , j )
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
bool MCProb::exchange(int& i,int& j,int m,int c,bool b,int N)
{
	if(m<0 || m>N || c<0 || c>N)
		return 0;
	bool flag=1;
    i=b;
	if(b)
	{
		if(m==0)
		{
			j=c-1;
		}
		else if(m==c&&c!=0)
		{
            j=N+c-1;
		}
		else if(m==N)
		{
			j=N+N+c;
		}
		else
		{
			flag=0;
		}
	}
	else
	{
		if(m==N)
		{
            j=N+N+c;
		}
		else if(m==c&&c!=N)
		{
			j=N+c;
		}
		else if(m==0)
		{
			j=c-1;
		}
		else
		{
			flag=0;
		}
	}
	return flag;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>生成操作
int MCProb::GenOperators(Operator*& pOper,int N,int V)
{
	int i,j,t=0;
	int k=((N>=V)?V:N);
	int hk=k/2;
	int n=hk*(k-hk)+2*k;
	pOper=new Operator[n];
    for(i=1;i<=k;i++)
	{
		pOper[t].m=0;
		pOper[t].c=i;
		t++;
        pOper[t].m=i;
		pOper[t].c=0;
		t++;
	}
	for(i=1;i<=hk;i++)
	{
		for(j=i;j<=k-i;j++)
		{
            pOper[t].m=j;
			pOper[t].c=i;
			t++;
		}
	}
	return n;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>判断是否到达目标状态
bool MCProb::IsObjState(State* pstate)
{
	if(pstate->m!=0||pstate->c!=0||pstate->b!=0)
		return 0;
	return 1;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>判断是否父节点
bool MCProb::IsParent(State* n,int m,int c,bool b)
{
	while(n)
	{
		if(m==n->m&&c==n->c&&b==n->b)
		{
			return 1;
		}
		n=n->parent;
	}
	return 0;
}

//>>>>>>>>>>>>>>>>>>OPEN是否为空?
bool MCProb::IsEmpty(StatePoint* sp)
{
	if(sp)
	{
		return 0;
	}
	return 1;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>插入状态
void MCProb::InsertState(StatePoint*& phead,StatePoint*& pcur,State* pstate)
{
	StatePoint* pTemp=new StatePoint;
	pTemp->pstate=pstate;
	pTemp->next=NULL;
	if(phead==NULL)
	{
		pcur=phead=pTemp;
	}
	else
	{
		pcur->next=pTemp;
		pcur=pTemp;
	}
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>将OPEN的第一个节点弹出
State* MCProb::Move_First(StatePoint*& sp)
{
    StatePoint* pTemp=NULL;
	State* pstate=NULL;
	pTemp=sp;
	sp=sp->next;
	pstate=pTemp->pstate;
	delete pTemp;
	return pstate;
}

/**************************************************************
int n;传教士人数
int c;船的容量
过程:MCOprate找出解路径
返回值:找到解返回1,否则返回0
***************************************************************/

bool MCProb::MCOprate(int N,int V)
{
	int i,j,k,iOps;
	int m,c,cost;
	bool b;
	State* n=NULL;
	State* snew=NULL;
	State* s=NULL;
	bool flag=false;//指示是否有解
	//**************************************************初始化状态类型表
	StateType** statetype=new StateType*[2];//用于保存节点的种类stNEW,stOPEN,stCLOSE
	State*** pstate=new State**[2];//用于保存节点指针
	for(i=0;i<2;i++)
	{
		statetype[i]=new StateType[3*N];
		pstate[i]=new State*[3*N];
	}
	for(i=0;i<2;i++)
	{
		for(j=0;j<3*N;j++)
		{
            statetype[i][j]=stNEW;
			pstate[i][j]=NULL;
		}
	}	
	//**************************************************生成操作算子
	iOps=GenOperators(pOper,N,V);
	
	//**************************************************开始运算
	m=c=N;b=1;
	s=GenState(m,c,b);
	exchange(i,j,m,c,b,N);
    pstate[i][j]=s;
	InsertState(G,GCur,s);
	InsertState(OPEN,OCur,s);
    statetype[i][j]=stOPEN;
	
	while(!IsEmpty(OPEN))
	{
        n=Move_First(OPEN);
		if(IsObjState(n))
		{
			flag=1;
			break;
		}
		for(k=0;k<iOps;k++)
		{
			if(n->b)
			{
				m=n->m-pOper[k].m;
				c=n->c-pOper[k].c;
				b=0;
			}
			else
			{
				m=n->m+pOper[k].m;
				c=n->c+pOper[k].c;
				b=1;
			}
			cost=n->cost+1;
			if(!exchange(i,j,m,c,b,N))//非法节点,再来
				continue;
			if(!IsParent(n,m,c,b))//父节点,再来
			{
				switch(statetype[i][j])//三种节点分情况讨论
				{
				case stNEW://新节点
					statetype[i][j]=stOPEN;
                    snew=GenState(m,c,b,cost,n);
					pstate[i][j]=snew;
					InsertState(G,GCur,snew);
                    InsertState(OPEN,OCur,snew);
					break;
				case stOPEN://在OPEN表
					if(cost<pstate[i][j]->cost)
					{
						pstate[i][j]->parent=n;
					}
					break;
				case stCLOSE://在CLOSE表
					if(cost<pstate[i][j]->cost)
					{
						pstate[i][j]->parent=n;
					}
					//此处不用将CLOSE重新加入OPEN
					break;
				}
			}
		}
		InsertState(CLOSE,CCur,n);//将已经扩展的节点加入CLOSE表
		exchange(i,j,n->m,n->c,n->b,N);
        statetype[i][j]=stCLOSE;//标志该节点在CLOSE表
	}

	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>保存解答路径
	ops=n->cost;
	path=new Operator[ops];
	for(i=ops-1;i>=0;i--)
	{
		path[i].m=n->m-n->parent->m;
		path[i].c=n->c-n->parent->c;
		n=n->parent;
	}

	//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>释放空间
	for(i=0;i<2;i++)
	{
		delete []statetype[i];
	    delete []pstate[i];
	}
	delete []statetype;
    delete []pstate;

	return flag;
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>释放空间
void MCProb::ReleaseSpace(StatePoint* pHead)
{
	StatePoint * pTemp=NULL;
	while(pHead)
	{
		pTemp=pHead;
        pHead=pHead->next;
		delete pTemp;
	}
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>删除搜索图
void MCProb::ReleaseG()
{
	StatePoint* pTemp=NULL;
	while(G)
	{
		pTemp=G;
        G=G->next;
		delete pTemp->pstate;
		delete pTemp;
	}
}