传教士与野人深度优先搜索.cpp

这是一遍人工智能的一个很经典的算法

#include<stdio.h>
#include<conio.h>
#include "windows.h"
struct Node
{
	int Priest;             //传教士
	int Wildman;            //野人
	int Boat;               //船   Boat=1时代表在左岸，Boat=0时代表在右岸
	int Extend;             //是否可扩展
	int Father;             //指向父节点
}BASE[2000];                //递推库数组

int Result[100];            //存放一次成功解法的中间过程
int n;

int Destination();          //判断是否是目标值
int Search(int );          //标志BASE[]是否是已到过节点，如果没有则返回1，否则返回0


void Forward(int z,int x,int y);       //船从左岸移到右岸，船上传教士x个，野人y个
void Afterward(int z,int x,int y);     //船从右岸移到左岸，船上传教士x个，野人y个


void main()
{
	int i;
	int SoloveNum=1;   //问题的解法
	
	n=1;

/*--------- 初始化 ---------*/

	BASE[0].Priest=3;       //左岸传教士3人
	BASE[0].Wildman=3;      //左岸野人3人
	BASE[0].Boat=1;          //船在左岸
	BASE[0].Extend=1;         //节点可扩展
	BASE[0].Father=-1;         //无父节点，即为初始节点
	
	for(i=0;i<n;i++)
	{
		if(BASE[i].Extend==1)        //判断节点是否可扩展
		{
			if(BASE[i].Boat==1)      //船在左岸 (Boat=1) 的一侧
			{
				if((BASE[i].Priest==0||BASE[i].Priest==3)&&BASE[i].Wildman>=1)
				{
					Forward(i,0,1);
				}
				if(BASE[i].Priest==1&&BASE[i].Wildman==1||BASE[i].Priest==3&&BASE[i].Wildman==2)
				{
					Forward(i,1,0);
				}
				if(BASE[i].Priest>=1&&BASE[i].Priest==BASE[i].Wildman)
				{
					Forward(i,1,1);
				}
				if((BASE[i].Priest==0||BASE[i].Priest==3)&&BASE[i].Wildman>=2)
				{
					Forward(i,0,2);
				}
				if(BASE[i].Priest==2&&BASE[i].Wildman==2||BASE[i].Priest==3&&BASE[i].Wildman==1)
				{
					Forward(i,2,0);
				}
			}
			else     //船在右岸 （Boat=0）的一侧
			{
				if((BASE[i].Priest==0||BASE[i].Priest==3)&&BASE[i].Wildman<=2)
				{
					Afterward(i,0,1);
				}
				if(BASE[i].Priest==2&&BASE[i].Wildman==2||BASE[i].Priest==0&&BASE[i].Wildman==1)
				{
					Afterward(i,1,0);
				}
				if(BASE[i].Priest<=2&&BASE[i].Priest==BASE[i].Wildman)
				{
					Afterward(i,1,1);
				}
				if((BASE[i].Priest==0||BASE[i].Priest==3)&&BASE[i].Wildman<=1)
				{
					Afterward(i,0,2);
				}
				if(BASE[i].Priest==1&&BASE[i].Wildman==1||BASE[i].Priest==0&&BASE[i].Wildman==2)
				{
					Afterward(i,2,0);
				}
			}
		}
	}
	printf("\n\n\t\t传教士野人过河问题\n\n");
	for(i=0;i<n;i++)
	{
		int j=0,k=i;
		int	 StepNum=1;    //每一种解法所需的步数
		if(BASE[k].Extend==-1)
		{
			while(k!=-1)
			{
				Result[j]=k;
				k=BASE[k].Father;
				j++;
			}
			j--;
			
			
			printf("\n 第%d种方法: \n\n",SoloveNum);
			while(j>0)
			{
				int BoatPriNum;     //船上传教士人数
                int BoatWildNum;     //船上野人人数
				 
				 BoatPriNum=BASE[Result[j]].Priest-BASE[Result[j-1]].Priest;
				 BoatWildNum=BASE[Result[j]].Wildman-BASE[Result[j-1]].Wildman;
				
				if(BASE[Result[j]].Boat==1)
				{
					printf("第%d次:\t左岸到右岸,传教士过去%d人,野人过去%d人\n\n",StepNum,BoatPriNum,BoatWildNum);
					StepNum++;
				}
				if(BASE[Result[j]].Boat==0)
				{
					printf("第%d次:\t右岸到左岸,传教士过去%d人,野人过去%d人\n\n",StepNum,BoatPriNum,BoatWildNum);
					StepNum++;
				}
				j--;
			}
			Sleep(1000);
			printf("\n");
			SoloveNum++;
		}
	}
	printf("\n\t\t\t运河结束\n\n");
	getch();

}


int Destination()          //判断是否是目标值
{
	if(BASE[n].Priest==0&&BASE[n].Wildman==0&&BASE[n].Boat==0)
	          return 1;
	return 0;
}

int Search(int x)                          //标志BASE[]是否是已到过节点，如果没有则返回1，否则返回0
{
	int i=x;
	while(BASE[i].Father!=-1)
	{
		if(BASE[i].Priest==BASE[n].Priest&&BASE[i].Wildman==BASE[n].Wildman&&BASE[i].Boat==BASE[n].Boat)
		{
			return 0;
		}

		i=BASE[i].Father;
	}
	if(BASE[i].Priest==BASE[n].Priest&&BASE[i].Wildman==BASE[n].Wildman&&BASE[i].Boat==BASE[n].Boat)
		     return 0;
	 return 1;
}

void Forward(int z,int x,int y)      //把船从左岸移到右岸，船上传教士x个，野人y个
{
	BASE[n].Priest=BASE[z].Priest-x;
	BASE[n].Wildman=BASE[z].Wildman-y;
	BASE[n].Boat=0;

	if(!Search(z))
	{
		return;
	}
	BASE[z].Extend=0;
	BASE[n].Extend=1;
	BASE[n].Father=z;
	if(Destination())
	{
		BASE[n].Extend=-1;
	}
	n++;
}

void Afterward(int z,int x,int y)   //把船从右岸移到左岸，船上传教士x个，野人y个
{
	BASE[n].Priest=BASE[z].Priest+x;
	BASE[n].Wildman=BASE[z].Wildman+y;
	BASE[n].Boat=1;

	if(!Search(z))
	{
		return;
	}
	BASE[z].Extend=0;
	BASE[n].Extend=1;
	BASE[n].Father=z;
	if(Destination())
	{
		BASE[n].Extend=-1;
	}
	n++;
}