mc.cpp

上人工智能课的时候写的一个小程序,用于求解传教士与野人问题,用的是A算法.

#include<iostream>
using namespace std;
struct data
{
	int M;      //传教士人数
	int C;      //野人数
	int B;      //船
};
data state[50]; //记录状态
int K,M,sum=0;  //载重，人数，解的个数
data Right,Left;//左岸和右岸的状态
void setData(data& Data,int m,int c,int b)//设置两岸状态
{
	Data.M=m; 
	Data.C=c; 
	Data.B=b;
}
void Print(int depth)    //输出状态序列
{
		for(int i=0;i<depth-1;i++)
			cout<<"("<<state[i].M<<","<<state[i].C<<","<<state[i].B<<")->";
		cout<<"("<<state[depth-1].M<<","<<state[depth-1].C<<","<<state[depth-1].B<<")"<<endl;
       }

bool noCircle(int m,int c,int k) //看状态序列中是否有自环
{
	bool flag=false;
	for(int i=0;i<k;i++)
		if((state[i].B==Right.B)&&(state[i].M==m)&&(state[i].C==c))
		{
			flag=true;
			break;
		}
		if(flag)return false;
		return true;
}

bool safe(int m,int c)         //看过河方案是否合理
{
	if((m+c)>0&&(m+c)<=K)
	{
		if(Right.B==0&&(m>=c||m==0)&&(((Left.M-m)>=(Left.C-c))||Left.M==m)&&(((Right.M+m)>=(Right.C+c))||(Right.M+m)==0)&&(Left.M-m>=0)&&(Left.C-c>=0)&&(Right.M+m<=M)&&(Right.C+c<=M))return true;
		if(Right.B==1&&(m>=c||m==0)&&((Left.M+m)>=(Left.C+c)||(Left.M+m)==0)&&((Right.M-m)>=(Right.C-c)||Right.M==m)&&(Left.M+m<=M)&&(Left.C+c<=M)&&(Right.M-m>=0)&&(Right.C-c>=0))return true;
	}
	return false;
}

void Find(int depth)           //递归求解
{
	if(Left.M==0&&Left.C==0)   //出口
	{
		sum++;
		Print(depth);
	}
	else
		for(int i=0;i<=M;i++)
		{
			for(int j=0;j<=M;j++)
			{
				if((Left.B==1)&&safe(i,j)&&noCircle(Left.M-i,Left.C-j,depth)) 
				{
					setData(state[depth],Left.M-i,Left.C-j,0);        //在左岸，递归并回溯
					setData(Right,Right.M+i,Right.C+j,1);
					setData(Left,Left.M-i,Left.C-j,0);
					Find(depth+1);
					setData(state[depth],0,0,0);
					setData(Right,Right.M-i,Right.C-j,0);
					setData(Left,Left.M+i,Left.C+j,1);
				}
				if((Left.B==0)&&safe(i,j)&&noCircle(Left.M+i,Left.C+j,depth))
				{   
					setData(state[depth],Left.M+i,Left.C+j,1);        //在右岸，递归并回溯
					setData(Right,Right.M-i,Right.C-j,0);
					setData(Left,Left.M+i,Left.C+j,1);
					Find(depth+1);
					setData(state[depth],0,0,0);
					setData(Right,Right.M+i,Right.C+j,1);
					setData(Left,Left.M-i,Left.C-j,0);
				}
			}
		}
}

int main()
{
	cout<<"请输入人数：";
	cin>>M;
	cout<<"请输入容量：";
	cin>>K;
	setData(state[0],M,M,1);  //设置初始状态
	setData(Left,M,M,1);
	setData(Right,0,0,0);
	Find(1);                  //开始求解
	if(sum==0)cout<<"no solution!"<<endl;
	else cout<<"共有"<<sum<<"个解"<<endl;
	return 0;
}