野人传教士nnk.cpp

野人传教士NNK 产生式系统简单实例 非常经典的算法

#include<iostream>
#include <queue>
#include <stack>
using namespace std;

int N_m;
int N_c;
int N_b;

struct zhuangtai{
	int l_m;
	int l_c;
	int l_b;//0为左；
	struct zhuangtai *father;
};

int judge(zhuangtai *now)
{
	if(now->l_c<0||now->l_c>N_c||now->l_m<0||now->l_m>N_m)
		return 0;
	if((now->l_m<now->l_c&&now->l_m!=0)||((N_m-now->l_m)<(N_c-now->l_c)&&N_m-now->l_m!=0))
		return 0;
	else if(now->l_m==0&&now->l_c==0&&now->l_b==0)
		return 3;
	else 
		return 1;

}
void print_zhuangtai(zhuangtai* result)
{
	if(result->l_b==0)
		cout<<"向左:"<<"左面传教士"<<result->l_m<<"人，野人"<<result->l_c<<"人\n";
	else 
		cout<<"向右:"<<"左面传教士"<<result->l_m<<"人，野人"<<result->l_c<<"人\n";
}
void print(zhuangtai *result)
{
    if(result != NULL)
    {
        //把路径倒序
        struct zhuangtai *p=result;
        stack<struct zhuangtai *> daoxu;
        while(p->father != NULL)
        {
            daoxu.push(p);
            p = p->father;
        }
        cout<<"搜索结果:"<<endl;
        while(!daoxu.empty())
        {
            print_zhuangtai(daoxu.top());
            daoxu.pop();
        }
        cout<<"\n完成!\n";
    }
}

bool chongfu(zhuangtai *test)
{
	zhuangtai *fath=test->father;
	zhuangtai *grandfath;
	if(fath!=NULL)
	{
		grandfath=fath->father;
	}
	if(fath!=NULL&&grandfath!=NULL)
	{
		if(grandfath->l_b==test->l_b&&test->l_c==grandfath->l_c&&test->l_m==grandfath->l_m)
			return true;
	}
	return false;

}

void search(zhuangtai *start)
{
	struct qipan *p;
	int step=0;
	p=NULL;	    
	queue<struct zhuangtai *> open; 
	queue<struct zhuangtai *> close;
	queue<struct zhuangtai *> change;

	open.push(start);
	do
	{
		zhuangtai *temp;
		temp=open.front();
		open.pop();

		int i,j;
		int zhixing;

		if(temp->l_b==1)
		{
		
			for(j=0;j<=N_b;j++ )
			{
				for(i=0;i<=N_b;i++)
				{
					if(1<=(i+j)&&(i+j)<=N_b&&(j>=i||i==0||j==0))
					{
						zhuangtai *temps=new zhuangtai;
						temps->father=temp;
						temps->l_b=0;
						temps->l_c=temp->l_c-i;
						temps->l_m=temp->l_m-j;
						zhixing=judge(temps);
						if(zhixing==0)
							delete temps;
						else if(zhixing==1)
							open.push(temps);
						else if(zhixing==3)
						{
							print(temps);
							return ;
						}
					}
				}
			}
		}
		else if(temp->l_b==0)
		{
			for(j=0;j<=N_b;j++ )
			{
				for(i=0;i<=N_b;i++)
				{
					if(1<=(i+j)&&(i+j)<=N_b&&(j>=i||i==0||j==0))
					{
						zhuangtai *temps=new zhuangtai;
						temps->father=temp;
						temps->l_b=1;
						temps->l_c=temp->l_c+i;
						temps->l_m=temp->l_m+j;
						zhixing=judge(temps);
						if(zhixing==0)
							delete temps;
						else if(zhixing==1&&!chongfu(temps))
							open.push(temps);
					}
				}
			}
		}

	}while(!open.empty());

}
void main()
{
	struct zhuangtai *start;
	bool in;
	in=false;
	start=new zhuangtai;
	cout<<"请输入野人，传教士，船载人数\n";
	start->father=NULL;

	while(!in)
	{
		cin>>start->l_c;
		cin>>start->l_m;
		cin>>N_b;
		if(start->l_c>start->l_m)
		{
			cout<<"此输入不合法，请重新输入\n";
		}
		else 
			in=true;
	}
	N_m=start->l_m;
	N_c=start->l_c;		
	start->l_b=1;

	search(start);	
}