a.cpp

人工智能教科书里面传教士与野人问题的VC++源代码

#include<iostream.h>

int N,K;		//野人和传教士数目，两者相同
struct NODE	
{
	int cost;//最小路径代价，在这里设为节点深  度
	int prem;//前一个节点的位置
	int prec;
	int preb;
	int pos;//1 new 0 nodet -1 close
	bool used_open;//曾经在open里出现过
};
NODE ***list;

struct nodet
{
	int m;
	int c;
	int b;
};
nodet* open;
int open_count;	//可扩展节点数目
int open_record_count;		//所有记录节点数目

nodet* path;//用来最后输出路径
int path_count;
bool succeed;

void ini()
{
	for(int i=0;i<N+1;i++)
	{
		list[i] = new NODE*[N+1];
		for(int j=0;j<N+1;j++)
		{
			list[i][j] = new NODE[2];
			list[i][j][1].pos = 1;
			list[i][j][0].pos = 1;
			list[i][j][1].used_open = false;
			list[i][j][0].used_open = false;
		}
	}
}

void solve()
{
	open = new nodet[(N+1)*(N+1)*2];
	open_count = 0;
	open_record_count=0; 
	path = new nodet[(N+1)*(N+1)*2];
	path_count = 0;
	succeed = false;
		
	//移进第一个节点
	list[N][N][1].cost =0;
	list[N][N][1].prem =-1;
	list[N][N][1].prec =-1;
	list[N][N][1].preb =-1;
	list[N][N][1].pos = 0;
	open[open_count].m =N;
	open[open_count].c =N;
	open[open_count].b =1;
	open_count =1;
	open_record_count=1;
		//开始一般图搜索
	while(open_count)//若nodet不是空表
	{
		//n:=MOVE_FIRST(nodet);
		int index =0;
		while(list[open[index].m][open[index].c][open[index].b].pos !=0)
			index++;
		int current_m = open[index].m;//当前左岸传教士和野人数目
		int current_c = open[index].c;
		int current_b = open[index].b;
		list[current_m][current_c][current_b].pos =-1;//把当前节点移到close表
		list[current_m][current_c][current_b].used_open = true;//该节点曾在open表出现
		open_count--;
		if(current_m ==0 && current_c ==0)//如果当前节点是目标节点，则搜索成功，给出解答路径
		{	
			succeed = true;
			int tempm,tempc,tempb;
			do
			{
				path[path_count].m = current_m;
				path[path_count].c = current_c;
				path[path_count].b = current_b;
				path_count++;
				tempm=list[current_m][current_c][current_b].prem;
				tempc=list[current_m][current_c][current_b].prec;
				tempb=list[current_m][current_c][current_b].preb;
				
				current_m = tempm;
				current_c = tempc;
				current_b = tempb;
			}
			while(current_m!=-1);
			for(int i=path_count-1;i>0;i--)
			{
				cout<<"("<<path[i].m<<","<<path[i].c<<","<<path[i].b<<")"<<"->";
			}
			cout<<"("<<path[i].m<<","<<path[i].c<<","<<path[i].b<<")"<<endl;
				break;
		}
		else//不是目标节点，开始扩展该节点
		{
			for(int m_loop=0;m_loop<=K;m_loop++)//m_loop上船的传教士人数
			{
				for(int c_loop=0;c_loop<=K;c_loop++)//c_loop上船的野人人数
				{
					if(m_loop+c_loop>0 && m_loop+c_loop<=K &&//符合船的载重限量
							((m_loop!=0 && c_loop!=0 && m_loop>=c_loop)||(m_loop == 0 ||c_loop ==0)))//船上安全
					{
						if(current_b==1 //船从左岸开出
							&& current_m>=m_loop && current_c>=c_loop)//有足够的传教士和野人
						{
							int leftm = current_m-m_loop;//渡河完成后两岸的传教士和野人数目
							int leftc = current_c-c_loop;
							int rightm = N-current_m+m_loop;
							int rightc = N-current_c+c_loop;
							if((leftm==0 || leftc==0 || leftm>=leftc)//左岸安全
								&&(rightm==0 || rightc==0 || rightm>=rightc))//右岸安全
							{
								if(list[leftm][leftc][0].pos == 1)//新节点
								{
									//记录父节点信息
									list[leftm][leftc][0].cost = list[current_m][current_c][1].cost+1;
									list[leftm][leftc][0].prem = current_m;
									list[leftm][leftc][0].prec = current_c;
									list[leftm][leftc][0].preb = current_b;
									list[leftm][leftc][0].pos =0;
										//添加到open
									open[open_record_count].m = leftm;
									open[open_record_count].c = leftc;
									open[open_record_count].b = 0;
									open_count++;
									open_record_count++;
								}
								else if(list[leftm][leftc][0].pos == 0)//open里的节点
								{
									if(list[current_m][current_c][1].cost+1<list[leftm][leftc][0].cost)
									{
										list[leftm][leftc][0].cost = list[current_m][current_c][1].cost+1;
										list[leftm][leftc][0].prem = current_m;
										list[leftm][leftc][0].prec = current_c;
										list[leftm][leftc][0].preb = current_b;
									}
								}
								else//close里面的节点
								{
									if(list[current_m][current_c][1].cost+1<list[leftm][leftm][0].cost)
									{
										list[leftm][leftc][0].cost = list[current_m][current_c][1].cost+1;
										list[leftm][leftc][0].prem = current_m;
										list[leftm][leftc][0].prec = current_c;
										list[leftm][leftc][0].preb = current_b;
										
										list[leftm][leftc][0].pos = 0;//从close移出
									}
								}
								//重新排列open里面的点,这个留待以后做启发式搜索
							}	
						}
						else if(current_b==0 //船从右岸开出
							&& N-current_m>=m_loop && N-current_c>=c_loop)//有足够的传教士和野人
						{
							int leftm = current_m+m_loop;//渡河完成后两岸的传教士和野人数目
							int leftc = current_c+c_loop;
							int rightm = N-current_m-m_loop;
							int rightc = N-current_c-c_loop;
								if((leftm==0 || leftc==0 || leftm>=leftc)//左岸安全 
								&&(rightm==0 || rightc==0 || rightm>=rightc))//右岸安全
							{
							if(list[leftm][leftc][1].pos == 1)//新节点
								{
									//记录父节点信息
									list[leftm][leftc][1].cost = list[current_m][current_c][0].cost+1;
									list[leftm][leftc][1].prem = current_m;
									list[leftm][leftc][1].prec = current_c;
									list[leftm][leftc][1].preb = current_b;
									list[leftm][leftc][1].pos =0;
									//添加到open
									open[open_record_count].m = leftm;
									open[open_record_count].c = leftc;
									open[open_record_count].b = 1;
									open_count++;
									open_record_count++;
								}
								else if(list[leftm][leftc][1].pos == 0)//open里的节点
								{
									if(list[current_m][current_c][0].cost+1<list[leftm][leftc][1].cost)
									{
										list[leftm][leftc][1].cost = list[current_m][current_c][0].cost+1;
										list[leftm][leftc][1].prem = current_m;
										list[leftm][leftc][1].prec = current_c;
										list[leftm][leftc][1].preb = current_b;
									}
								}
								else//close里面的节点
								{
									if(list[current_m][current_c][0].cost+1<list[leftm][leftc][1].cost)
									{
										list[leftm][leftc][1].cost = list[current_m][current_c][0].cost+1;
										list[leftm][leftc][1].prem = current_m;
										list[leftm][leftc][1].prec = current_c;
										list[leftm][leftc][1].preb = current_b;
										
										list[leftm][leftc][0].pos = 0;//从close移出，注意这里没有改变close数组的值，但也能奏效
									}
								}
								//重新排列open里面的点
							}
						}
					}
				}
			}
		}
	}
}

int main()
{
	cout<<"请输入N和K：（输入0和0表示结束）"<<endl;
	while(cin>>N>>K)	//输入N和K
	{
		if(N+K==0)
			return 0;
		list = new NODE**[N+1];

		ini();//初始化
		
		solve();
		
		if(!succeed)
			cout<<"没有解法！"<<endl;
		delete []list;
		delete []open;
		delete []path;
		cout<<"请输入N和K：（输入0和0表示结束）"<<endl;
	}
	return 0;
}