backtrackm_c.cpp

通过回溯方法来解决传教士问题

#include <stdio.h>
#include <stdlib.h>
#define		FAIL	((struct RULE *)-1)	//定义失败标志
//#define		M	3		//传教士总人数
//#define		C	3		//野人总人数
//#define		K	2		//船一次可以乘坐的最多人数

static int M;
static int C;
static int K;

//输入M,C,K,对不同的结果进行测试
void Input_MCK()
{	
	int a, b;
	printf("请输入传教士和野人的数目 : \n");
	scanf("%d", &a);
	printf("请输入船上最大载客量 : \n");
	scanf("%d", &b);
	M = a, C = a, K = b;

}



// 定义节点结构
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)
{
	if (pNode1->m == pNode2->m &&
		pNode1->c == pNode2->c &&
		pNode1->b == pNode2->b) 
		return 1;
	else
		return 0;
}

//动态产生一个节点，其状态值由参数m，c，b给定
struct NODE *NewNode(int m, int c, int b)
{
	struct NODE *pNode = NULL;
	pNode = (NODE*)malloc(sizeof(struct NODE));
	if (pNode == NULL) return NULL;
	pNode->m = m;
	pNode->c = c;
	pNode->b = b;
	pNode->pNext = NULL;
	return pNode;
}

//动态产生一个规则，其值由参数m，c给定
//表示本次过河的传教士人数和野人人数 
struct RULE *NewRule(int m, int c)
{
	struct RULE *pRule = NULL;
	pRule = (RULE*)malloc(sizeof(struct RULE));
	if (pRule == NULL) return NULL;
	pRule->m = m;
	pRule->c = c;
	pRule->pNext = NULL;
	return pRule;
}

//初始化规则集
struct RULE *InitRules(void)
{
	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)
{
	if (pNode->m == 0 &&
		pNode->c == 0 &&
		pNode->b == 0) 
		return 1;
	else 
		return 0;
}

//判断一个状态是否为安全的
/*满足在河的任何一岸，传教士人数不少于野人人数，或者只有野
人而没有传教士。对于超出参数范围的状态，也认为是不安全的*/               
int Safe(struct NODE *pNode)
{
	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)
{
	printf("(%d, %d, %d)\n", pNode->m, pNode->c, pNode->b);
}

void PrintRule(struct RULE *pRule)
{
	printf("(%d %d)\n", pRule->m, pRule->c);
}

void PrintNodeList(struct NODE *pList)
{
	while (pList)	//依次打印链表
	{
		printf("(%d, %d, %d)\n", pList->m, pList->c, pList->b);
		pList = pList->pNext;
	}
}

void PrintRuleList(struct RULE *pList)
{
	
	if (pList == FAIL)
	{
		printf("no solution!\n");
		return;
	}
	if (pList == NULL)
	{
		printf("( )\n");
		return;
	}
	else
	{	
		printf("(0, 0, 0)\n");
	}
	/*while (pList)	//依次打印链表
	{
		pList = pList->pNext;
	}*/
}

//求链表的长度
int Length(struct NODE *pList)
{
	if (pList == NULL) return 0;
	return Length(pList->pNext) + 1;
}

//将一个节点插入到节点链表的前面
struct NODE *ConsNode(struct NODE *pNode, struct NODE *pList)
{
	pNode->pNext = pList;
	return pNode;
}

//将一个规则插入到规则链表的前面
struct RULE *ConsRule(struct RULE *pRule, struct RULE *pList)
{
	pRule->pNext = pList;
	return pRule;
}

//将规则作用于给定的节点，产生一个新节点
struct NODE *Gen(struct RULE *pRule, struct NODE *pData)
{
	if (pData->b == 1)
	{
		return NewNode(pData->m - pRule->m, pData->c - pRule->c, 0);
	}
	else
	{
		return NewNode(pData->m + pRule->m, pData->c + pRule->c, 1);
	}
}

//复制一个规则
struct RULE *CopyRule(struct RULE *pRule)
{
	return NewRule(pRule->m, pRule->c);
}

//判断一个节点是否在一个链表中
struct NODE *In(struct NODE *pNode, struct NODE *pList)
{
	if (pList == NULL) return NULL;
	if (Equal(pNode, pList)) return pList;
	return In(pNode, pList->pNext);
}

//释放动态产生的节点链表
void FreeNodeList(struct NODE *pNodeList)
{
	struct NODE *pNode = NULL;
	while (pNodeList)
	{
		pNode = pNodeList;
		pNodeList = pNodeList->pNext;
		free(pNode);
	}
}

//释放动态产生的规则链表
void FreeRuleList(struct RULE *pRuleList)
{
	struct RULE *pRule = NULL;
	if (pRuleList == FAIL) return;
	while (pRuleList)
	{
		pRule = pRuleList;
		pRuleList = pRuleList->pNext;
		free(pRule);
	}
}

//回溯算法主函数 
struct RULE *Backtrack1(struct NODE *pDataList, int bound)
{
	struct NODE *pData = NULL, *pRData = NULL, *pRDataList = NULL;
	struct RULE *pRule = NULL, *pRules = NULL, *pPath = NULL;

	pData = pDataList;	//取当前节点
	if (In(pData, pDataList->pNext)) 
	{
		return FAIL;	//如果当前节点已经出现在初始节点到当前节点的路径上，
						//则返回失败，准备回溯
	}
	if (IsGoal(pData))	//如果当前节点是目标节点
	{
		FreeNodeList(pDataList);	//释放掉路径上的所有节点
		return NULL;	//以“空”作为解路径返回，表示从目标节点到目标节点
						//不需要任何规则操作。算法成功结束
	}
	if (!Safe(pData))	//如果当前节点是一个非法节点
	{
		return FAIL;	// 返回失败，准备回溯
	}
	if (Length(pDataList) > bound)	//如果搜索深度达到了给定的深度
	{
		return FAIL;	// 返回失败，准备回溯
	}

	pRules = g_pRuleSet;	//获取所有规则
	
	PrintNode(pDataList);
	while (pRules)	//当规则集非空时
	{
		pRule = pRules;	//取规则集的第一个规则
		pRules = pRules->pNext;	//将第一个规则从规则集中删除
		pRData = Gen(pRule, pData);	//将第一个规则作用于当前节点，产生一个新节点
		if (pRData == NULL) return FAIL;	//空间不够，失败返回

		if (!Safe(pRData))	//如果新节点非法
		{
			free(pRData);	//释放掉该节点
			continue;	//试探下一个规则
		}
		
		
		pRDataList = ConsNode(pRData, pDataList);	//将新节点加入到从初始节点到当前的路径中
		pPath = Backtrack1(pRDataList, bound);	//新节点作为当前节点递归调用回溯算法
		

		if (pPath == FAIL)	//如果从当前节点到目标节点没有路径
		{

			free(pRData);	//释放当前节点
			continue;	//试探下一条规则
		}
		
		// 如果从当前节点到目标节点存在路径
		pRule = CopyRule(pRule);	//复制当前所用的规则
		if (pRule == NULL) return FAIL;	//空间不够，失败返回
		return ConsRule(pRule, pPath);	//将规则添加到规则表中，并作为解路径返回
	}
	return FAIL;	//如果规则表已空，则返回失败，回溯或者算法以失败结束
}

void main(void)
{
	struct NODE *pData = NULL;
	struct RULE *pPath = NULL;
	Input_MCK();
	g_pRuleSet = InitRules();	//初始化规则集
	
	pData = NewNode(M, C, 1);	//设置初始节点

	pPath = Backtrack1(pData, 20);	//调用回溯程序
	
	PrintRuleList(pPath);	//显示解路径
	
	if (pPath == FAIL)	//当求解失败时
	{
		free(pData);	//释放初始节点
	}
	FreeRuleList(pPath);	//释放解路径
	FreeRuleList(g_pRuleSet);	//释放规则集
}