n传教士与n野人问题(a算法).cpp

历史上著名的N教士与N野人问题

#include<stdio.h>

#define MAX 1000000 //定义最大f(n)值

//定义状态结点
struct Node
{
	int m;
	int c;
	int b;
	int n;
	Node *next;
	Node *pre;
}*open,*closed,*openTail,*closedTail;

int N,K;  //定义N、K

void init();  //初始化函数
bool search();  //搜索解函数
void freeAll();  //释放资源函数
Node* getExtendNode();  //从open表中获取最小f(n)值的结点函数
void show(Node* a,int last);  //解输出函数
void insertOpen(Node* a);  //向open表插入结点函数
void insertClosed(Node* a);  //向closed表插入结点函数
bool used(Node* a,int m,int c,int b);  //判断扩展产生的结点是否重复函数


int main()
{
	init();
	if(!search())
		printf("NO ANWSER!\n");
	return 0;
}


//初始化函数
void init()
{
	scanf("%d%d",&N,&K);
	Node *temp=new Node;
	if(temp == NULL)
	{
		printf("内存分配失败\n");
		exit(1);
	}
	temp ->m = N;
	temp ->c = N;
	temp ->b = 1;
	temp ->n = 0;
	temp ->pre = NULL;
	temp ->next = NULL;
	open=NULL;
	open = temp;
	openTail = open;
	closed = NULL;
	closedTail = NULL;
}


//搜索解函数
bool search()
{
	while(1)
	{
		//获取open表中最小f(n)结点
		Node *curNode = getExtendNode();

        //无解
		if(curNode == NULL)
		{
			freeAll();
			return false;
		}

        //找到解
		if(curNode ->m == 0 && curNode ->c == 0 && curNode ->b == 0)
		{
			show(curNode,1);
			freeAll();
			return true;
		}

        //将从open表中选出的结点放进closed表中
		insertClosed(curNode);

		if(curNode ->b)
		{
			//船在左岸
			int i = 0,j = 0;
			
			//寻找满足条件的被被扩展的结点
			for(i = 0;i <= K && i <= curNode ->m;i++)
				for(j = 0;j <= K && j <= curNode ->c;j++)
				{
					if( i + j > K || (i != 0 && j > i) )
						break;
					if( i==0 && j==0 )
						continue;
					int Man = curNode ->m - i,Savage = curNode ->c - j;
					if( ( Man == 0 || Man == N || (Man >= Savage && (N - Man) >= (N - Savage) ) )
						&& !used(curNode,Man,Savage,0))
					{
						Node *temp = new Node;
						if(temp == NULL)
						{
							printf("内存分配失败\n");
							freeAll();
							exit(1);
						}
						temp ->m = Man;
						temp ->c = Savage;
						temp ->b = 0;
						temp ->n = curNode->n + 1;
						temp ->pre = curNode;
						temp ->next = NULL;
						insertOpen(temp);
					}
				}
		}
		else
		{  
			//船在右岸
			int i = 0,j = 0;

			//寻找满足条件的被被扩展的结点
			for(i = 0;i <= K && i <= (N - curNode ->m);i++)
				for(j = 0;j <=K && j <= (N - curNode ->c);j++)
				{
					if( i + j > K || (i != 0 && j > i) )
						break;
					if( i==0 && j==0 )
						continue;
					int Man =curNode ->m + i,Savage =curNode ->c + j;
					if( ( Man == 0 || Man == N || (Man >= Savage && (N - Man) >= (N - Savage)))
					    && !used(curNode,Man,Savage,1))
					{
						Node *temp = new Node;
						if(temp == NULL)
						{
							printf("内存分配失败\n");
							freeAll();
							exit(1);
						}
						temp ->m = Man;
						temp ->c = Savage;
						temp ->b = 1;
						temp ->n = curNode ->n + 1;
						temp ->pre = curNode;
						temp ->next = NULL;
						insertOpen(temp);
					}
				}
		}
	}
	return false;
}


//从open表中获取最小f(n)值的结点函数
Node* getExtendNode()
{
	int cost = MAX; 
	Node *t,*next = open;

    //表为空
	if(open == NULL)
		return NULL;
	else
	{
		//寻找最小f(n)的结点
		while(next)
		{
			if( (next->n + next->m + next->c - 2*next->b) < cost )
				t=next;
			next = next ->next;
		}

        //当该结点为首结点
		if(t == open)
		{
			open=NULL;
			openTail = open;
			
		}
		else
		//当该结点为尾结点
		if(t == openTail)
		{
			next=open;
			while(1)
			{
				if(next->next == openTail )
				{
					openTail = next;
					break;
				}
				next = next->next;
			}	
		}
		else
		//当该结点为中间结点
		{
			next=open;
			while(1)
			{
				if(next->next == t)
				{
					next->next = next->next->next;
					break;
				}
				next = next->next;
			}
		}

        //将该结点的后继结点设为空
		t->next = NULL;
	}


	return t;	
}


//解输出函数
void show(Node* a,int last)
{
	if(a ->pre != NULL)
	{
		show(a->pre,0);
		printf("(%d,%d,%d)",a->m,a->c,a->b);
		if(last)
			printf("\n");
		else
			printf("->");

	}		
}


//释放资源函数
void freeAll()
{
	Node * cur = open;
	while(cur)
	{
		Node *t = cur;
		cur = cur->next;
		delete t;
	}


	cur = closed;
	while(cur)
	{
		Node *t=cur;
		cur = cur ->next;
		delete t;
	}
}


//向open表插入结点函数
void insertOpen(Node* a)
{
	if(open == NULL)
	{
		open = a;
		open ->next = NULL;
		openTail = open;
	}
	else
	{
		openTail ->next = a;
		openTail = a;
		openTail ->next = NULL;
	}
}


//向closed表插入结点函数
void insertClosed(Node* a)
{
	if(closed == NULL)
	{
		closed = a;
		closed ->next = NULL;
		closedTail = closed;
	}
	else
	{
		closedTail ->next = a;
		closedTail = a;
		closedTail ->next = NULL;
	}
}


//判断扩展产生的结点是否重复函数
bool used(Node* a,int m,int c,int b)
{
	Node *temp =a;
	while(temp->pre)
	{
		temp=temp->pre;
		if(temp->m == m && temp->c == c && temp->b == b)
			return true;
	}
	return false;
}