#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