北航人工智能原理课大作业源代码，A*算法解决野人与传教士过河问题

网上绝大部分解决野人与传教士问题的代码使用的是递归+回朔。根据北航研究生人工智能课大作业的要求，本程序用A*算法解决了野人与传教士过河问题。因为是无聊帮同学做的，所以自己写了所有的链表操作函数。
算法思路随处可见，本程序初始条件为3个野人和3个传教士，使用的启发函数为M+C-2B。

#include 
#include 

#define MAX_MISS 				3			//传教士人数
#define MAX_CANN 				3			//野人人数

#define OUTPUTMODE				1			//输出模式：0------输出至屏幕，1------输出至文件

//============================================数据结构：
typedef struct _status						//描述问题状态
{
	int mLeft;								//左岸传教士数量
	int cLeft;								//左岸野人数量
	int mRight;								//右岸传教士数量
	int cRight;								//右岸野人数量
	int b;									//船在左岸还是右岸
	int Hash;								//为了快速判断结点是否存在引入的哈希值
	int HVal;								//启发函数值
	struct _status *Next;					//后向结点指针
	struct _status *Prev;					//前驱结点指针
} STATUS;

typedef struct _passenger					//描述状态转移算子（过河方法）
{
	int m;									//可过河的传教士人数
	int c;									//可过河的野人人数
} PASSENGER;

STATUS *OpenHead = new STATUS;				//创建Open表保存所有已生成而未考察的结点
STATUS *CloseHead = NULL;					//创建Close表暂为空保存所有已考察的结点

int Hash（STATUS *Node）;						//哈希函数
int Heruistic（STATUS *Node）;				//启发函数

bool isTarget（STATUS *Current）;				//判断是否满足目标状态
bool isSafe（STATUS *Node）;					//判断给定状态是否安全

STATUS* AStar（STATUS *Current）;				//A*算法主函数
void ResultOut（STATUS *Current）;			//输出结果

STATUS* GetLastNodeOpen（）;					//取Open表最后一个节点
STATUS* GetLastNodeClose（）;					//取Close表最后一个节点
void RemoveOpen（STATUS *Node）;				//从Open表中删除节点
void RemoveClose（STATUS *Node）;				//从Close表中删除节点
STATUS* isInOpen（STATUS *Node）;				//判断指定结点是否在Open表中
STATUS* isInClose（STATUS *Node）;			//判断指定结点是否在Close表中
void InsertOpen（STATUS *Node）;				//插入节点到Open表中
void InsertClose（STATUS *Node）;				//插入节点到Close表中
void SwapOpen（）;							//对Open表按启发函数排序

int main（）
{
	STATUS *Current = NULL;

	OpenHead->mLeft = MAX_MISS;									//创建初始状态，得到最初的父节点
	OpenHead->cLeft = MAX_CANN;
	OpenHead->mRight = 0;
	OpenHead->cRight = 0;
	OpenHead->b = 0;
	OpenHead->Hash = Hash（OpenHead）;
	OpenHead->HVal = Heruistic（OpenHead）;
	OpenHead->Next = NULL;
	OpenHead->Prev = NULL;

	while （OpenHead）											//Open表非空
	{
		Current = GetLastNodeOpen（）;							//从Open表中得到启发函数最小的结点作为父节点，并从Open表中删除
		RemoveOpen（Current）;

		if （isTarget（Current））									//达到目标状态则输出结果，否则继续A*算法
		{
			ResultOut（Current）;
			getchar（）;
			return 0;
		}
		else
		{
			AStar（Current）;
		}
	}

	printf（“过不了河，传不了教...“）;
}

void ResultOut（STATUS *Current）
{
	FILE *p;
	Current->Next = NULL;

	do
	{
		Current->Prev->Next = Current;
		Current = Current->Prev;
	}
	while （Current->Prev != NULL）;

	int i = 0;

	if （OUTPUTMODE）												//输出到文件
	{
		p = fopen（“Result.txt“ “w+“）;
		printf（“结果输出至Result.txt...\n“）;
		fprintf（p “渡河过程\n步数\t传教士\t野人\t左岸| 船\t|右岸\t传教士\t野人\t\n“）;

		do
		{
			fprintf（p “%d\t%d\t%d\t    |“ i++ Current->mLeft Current->cLeft）;

			if （Current->b == 0）
				fprintf（p “<==>    \t“）;
			else
				fprintf（p “\t    <==>“）;

			fprintf（p “|\t%d\t%d\t\n“ Current->mRight Current->cRight）;
			Current = Current->Next;
		}
		while （Current != NULL）;

		printf（“完毕!\n“）;
		fclose（p）;
	}
	else														//输出到屏幕
	{
		printf（“渡河过程\n步数\t传教士\t野人\t左岸| 船\t|右岸\t传教士\t野人\n“）;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      10240  2010-01-14 23:11  AStar.cpp

     文件      49643  2010-01-14 23:23  AStar.exe

     文件        394  2010-01-16 17:59  Result.txt

----------- ---------  ---------- -----  ----

                60277                    3