a_star_m_c.c

使用A*算法解决传教士与野人的问题

/*********************************************************************************
 *          程  序  说  明                                                       *
 * 功能: 用A*算法求解传教士与野人问题。M=C=5, K=3                                *
 * 说明:                                                                         *
 *     本程序按照《人工智能导论》一书所介绍的A*算法求解传教士与野人问题。        *
 *                                                                               *
 * 注意: 该程序尽可能用与算法一致的思路实现算法, 力求简单明了, 注重算法的清晰性，*
 * 而没有考虑算法的效率问题。                                                    *
 *********************************************************************************/

#include <stdio.h>
#include <stdlib.h>

#define		M	5		//传教士总人数
#define		C	5		//野人总人数
#define		K	3		//船一次可以乘坐的最多人数

struct NODE
{
	int m;						//在左岸的传教士人数
	int c;						//在左岸的野人人数
	int b;						//b=1表示船在左岸,b=0表示船在右岸
	double g;					//该节点的g值
	double f;					//该节点的f值
	struct NODE *pFather;		//指向该节点的父节点
	struct NODE *pNext;			//在OPEN表或者CLOSED表中，指向下一个元素
};

struct NODE *g_pOpen = NULL;	//全程变量，OPEN表
struct NODE *g_pClosed = NULL;		//全程变量，CLOSED表


int Equal(struct NODE *pNode1, struct NODE *pNode2)
/******************************************************
 * 功能：判断两个节点所表示的状态是否相等             *
 *                                                    *
 * 入口参数：                                         *
 *   pNode1：指向节点1的指针                          *
 *   pNode2：指向节点2的指针                          *
 *                                                    *
 * 返回值：当两个节点所表示的状态相等时，返回1，否则  *
 *         返回0                                      *
 ******************************************************/
{
	if (pNode1->m == pNode2->m &&
		pNode1->c == pNode2->c &&
		pNode1->b == pNode2->b) return 1;
	else return 0;
}

struct NODE *NewNode(int m, int c, int b)
/******************************************************
 * 功能：动态产生一个节点，其状态值由参数m，c，b给定。*
 *                                                    *
 * 入口参数：                                         *
 *   m：河左岸的传教士人数                            *
 *   c：河左岸的野人人数                              *
 *   b：船是否在左岸，1：表示在左岸，0：表示不在左岸  *
 *                                                    *
 * 返回值：指向新产生的节点的指针，或者空间不够时，返 *
 *         回NULL                                     *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	pNode = malloc(sizeof(struct NODE));
	if (pNode == NULL) return NULL;
	pNode->m = m;
	pNode->c = c;
	pNode->b = b;
	pNode->g = 0;
	pNode->f = 0;
	pNode->pFather = NULL;
	pNode->pNext = NULL;
	return pNode;
}

void FreeList(struct NODE *pList)
/******************************************************
 * 功能：释放动态产生的链表                           *
 *                                                    *
 * 入口参数：                                         *
 *   pList：指向OPEN表或者CLOSED表的指针              *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	while (pList)
	{
		pNode = pList;
		pList = pList->pNext;
		free(pNode);
	}
}

struct NODE *In(struct NODE *pNode, struct NODE *pList)
/******************************************************
 * 功能：判断一个节点是否在一个链表中                 *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *   pList：指向给点链表的指针                        *
 *                                                    *
 * 返回值：当pNode在pList中时，返回以pNode为首的链表  *
 *         的后一部分；否则返回NULL                   *
 ******************************************************/
{
	if (pList == NULL) return NULL;
	if (Equal(pNode, pList)) return pList;
	return In(pNode, pList->pNext);
}

struct NODE *Del(struct NODE *pNode, struct NODE *pList)
/******************************************************
 * 功能：从链表pList中删除节点pNode                   *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *   pList：指向给定的链表                            *
 *                                                    *
 * 返回值：删除给定节点后的链表                       *
 ******************************************************/
{
	if (pList == NULL) return pList;
	if (Equal(pNode, pList)) return pList->pNext;
	pList->pNext = Del(pNode, pList->pNext);
	return pList;
}

struct NODE *AddToOpen(struct NODE *pNode, struct NODE *pOpen)
/******************************************************
 * 功能：将一个节点按照f值（从小到大）插入到OPEN表中  *
 *                                                    *
 * 入口参数：                                         *
 *   pNode: 指向给定节点的指针                        *
 *   pOpen：指向OPEN表的指针                          *
 *                                                    *
 * 返回值：指向插入给定节点后OPEN表的指针             *
 *                                                    *
 * 注意：同一个节点（具有相同指针的一个节点），只能向 *
 *       表中添加一次，否则可能会造成循环链表         *
 ******************************************************/
{
	if (pOpen == NULL)	//OPEN表为空
	{
		pNode -> pNext = NULL;
		return pNode;	
	}
	if (pNode->f < pOpen->f)	//给定节点的f值小于OPEN表第一个节点的f值
	{
		pNode->pNext = pOpen;	//插入到OPEN的最前面
		return pNode;
	}
	pOpen->pNext = AddToOpen(pNode, pOpen->pNext);	//递归
	return pOpen;
}

struct NODE *AddToClosed(struct NODE *pNode, struct NODE *pClosed)
/******************************************************
 * 功能：将一个节点插入到CLOSED表中                   *
 *                                                    *
 * 入口参数：                                         *
 *   pNode: 指向给定节点的指针                        *
 *   pClosed：指向CLOSED表的指针                      *
 *                                                    *
 * 返回值：指向插入给定节点后CLOSED表的指针           *
 *                                                    *
 * 注意：同一个节点（具有相同指针的一个节点），只能向 *
 *       表中添加一次，否则可能会造成循环链表         *
 ******************************************************/
{
	pNode->pNext = pClosed;
	return pNode;
}

void PrintList(struct NODE *pList)
/******************************************************
 * 功能：在屏幕上打印一个链表，用于调试程序           *
 *                                                    *
 * 入口参数：                                         *
 *   pList：指向链表的指针                            *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	while (pList)	//依次打印链表
	{
		printf("((%d %d %d) %f %f)\n", pList->m, pList->c, pList->b, pList->g, pList->f);
		pList = pList->pNext;
	}
}

void PrintNode(struct NODE *pNode)
/******************************************************
 * 功能：在屏幕上打印一个节点，用于调试程序           *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向节点的指针                            *