backtrack_m_c.c

清华大学《人工智能导论》课程电子教案,给大家看看

/*********************************************************************************
 *          程  序  说  明                                                       *
 * 功能: 用回溯算法求解传教士与野人问题。M=C=3, K=2                              *
 * 说明:                                                                         *
 *     本程序按照《人工智能导论》一书所介绍的回溯算法求解传教士与野人问题。      *
 *                                                                               *
 * 注意: 该程序尽可能用与算法一致的思路实现算法, 力求简单明了, 注重算法的清晰性，*
 * 而没有考虑算法的效率问题。                                                    *
 *                                                                               *
 * 作者：马少平                                                                  *
 * 单位：清华大学智能技术与系统国家重点实验室                                    *
 * 时间：2004年8月15日                                                           *
 *********************************************************************************/

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

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

#define		FAIL	((struct RULE *)-1)	//定义失败标志

// 定义节点结构
struct NODE
{
	int m;						//在左岸的传教士人数
	int c;						//在左岸的野人人数
	int b;						//b=1表示船在左岸,b=0表示船在右岸
	struct NODE *pNext;			//构成链表，指向下一个元素
};

// 定义规则结构，一条规则用本次上船的传教士人数和野人人数表示
struct RULE
{
	int m;	//本次上船的传教士人数
	int c;	//本次上船的野人人数
	struct RULE *pNext;	//构成链表，指向下一个元素
};

struct RULE *g_pRuleSet = NULL;	//定义全程变量，用于存放规则集

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->pNext = NULL;
	return pNode;
}

struct RULE *NewRule(int m, int c)
/******************************************************
 * 功能：动态产生一个规则，其值由参数m，c给定，表示本 *
 *       次过河的传教士人数和野人人数                 *
 *                                                    *
 * 入口参数：                                         *
 *   m：过河的传教士人数                              *
 *   c：过河的野人人数                                *
 *                                                    *
 * 返回值：指向新产生的规则的指针，或者空间不够时，返 *
 *         回NULL                                     *
 ******************************************************/
{
	struct RULE *pRule = NULL;
	pRule = malloc(sizeof(struct RULE));
	if (pRule == NULL) return NULL;
	pRule->m = m;
	pRule->c = c;
	pRule->pNext = NULL;
	return pRule;
}

struct RULE *InitRules(void)
/******************************************************
 * 功能：初始化规则集                                 *
 *                                                    *
 * 入口参数：无                                       *
 *                                                    *
 * 返回值：指向规则集的指针，或者当内存不够时返回NULL *
 ******************************************************/
{
	struct RULE *pRules = NULL, *pRule = NULL;
	int i, j;

	//形成过河规则集
	for (i = 0; i <= K; i++)
	{
		for (j = 0; j <= K; j++)
		{
			if (i + j == 0 ||
				i + j > K ||
				(i != 0 && i < j)) continue;
			pRule = NewRule(i, j);
			if (pRule == NULL) return NULL;
			pRule->pNext = pRules;
			pRules = pRule;
		}
	}
	return pRules;
}

int IsGoal(struct NODE *pNode)
/******************************************************
 * 功能：判断给定节点是否为目标节点                   *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *                                                    *
 * 返回值：当给定节点是目标节点时，返回1，否则返回0   *
 ******************************************************/
{
	if (pNode->m == 0 &&
		pNode->c == 0 &&
		pNode->b == 0) return 1;
	else return 0;
}

int Safe(struct NODE *pNode)
/******************************************************
 * 功能：判断一个状态是否为安全的，即是否满足在河的任 *
 *       何一岸，传教士人数不少于野人人数，或者只有野 *
 *       人而没有传教士。对于超出参数范围的状态，也认 *
 *       为是不安全的                                 *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向给定节点的指针                        *
 *                                                    *
 * 返回值：当给定节点安全时，返回1，否则返回0         *
 ******************************************************/
{
	if (pNode->m < 0 ||
		pNode->c < 0 ||
		pNode->m > M ||
		pNode->c > M) return 0;
	if (pNode->m == M ||
		pNode->m == 0) return 1;
	return (pNode->m == pNode->c);
}

void PrintNode(struct NODE *pNode)
/******************************************************
 * 功能：在屏幕上打印一个节点，用于调试程序           *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向节点的指针                            *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	printf("(%d %d %d)\n", pNode->m, pNode->c, pNode->b);
}

void PrintRule(struct RULE *pRule)
/******************************************************
 * 功能：在屏幕上打印一个规则，用于调试程序           *
 *                                                    *
 * 入口参数：                                         *
 *   pRule：指向规则的指针                            *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	printf("(%d %d)\n", pRule->m, pRule->c);
}

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

void PrintRuleList(struct RULE *pList)
/******************************************************
 * 功能：在屏幕上打印一个规则链表，用于调试程序       *
 *                                                    *
 * 入口参数：                                         *
 *   pList：指向链表的指针                            *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	if (pList == FAIL)
	{
		printf("失败!\n");
		return;
	}
	if (pList == NULL)
	{
		printf("( )\n");
		return;
	}
	while (pList)	//依次打印链表
	{