backtrack_m_c.c

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

		printf("(%d %d)\n", pList->m, pList->c);
		pList = pList->pNext;
	}
}

int Length(struct NODE *pList)
/******************************************************
 * 功能：求链表的长度                                 *
 *                                                    *
 * 入口参数：                                         *
 *   pList：指向链表的指针                            *
 *                                                    *
 * 返回值：链表的长度                                 *
 ******************************************************/
{
	if (pList == NULL) return 0;
	return Length(pList->pNext) + 1;
}

struct NODE *ConsNode(struct NODE *pNode, struct NODE *pList)
/******************************************************
 * 功能：将一个节点插入到节点链表的前面               *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：指向节点的指针                            *
 *   pList：指向链表的指针                            *
 *                                                    *
 * 返回值：插入节点后的链表指针                       *
 ******************************************************/
{
	pNode->pNext = pList;
	return pNode;
}

struct RULE *ConsRule(struct RULE *pRule, struct RULE *pList)
/******************************************************
 * 功能：将一个规则插入到规则链表的前面               *
 *                                                    *
 * 入口参数：                                         *
 *   pRule：指向规则的指针                            *
 *   pList：指向链表的指针                            *
 *                                                    *
 * 返回值：插入规则后的链表指针                       *
 ******************************************************/
{
	pRule->pNext = pList;
	return pRule;
}

struct NODE *Gen(struct RULE *pRule, struct NODE *pData)
/******************************************************
 * 功能：将规则作用于给定的节点，产生一个新节点       *
 *                                                    *
 * 入口参数：                                         *
 *   pRule：指向规则的指针                            *
 *   pList：指向节点的指针                            *
 *                                                    *
 * 返回值：指向新节点的指针                           *
 ******************************************************/
{
	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)
/******************************************************
 * 功能：复制一个规则                                 *
 *                                                    *
 * 入口参数：                                         *
 *   pRule：指向规则的指针                            *
 *                                                    *
 * 返回值：指向复制的规则的指针                       *
 ******************************************************/
{
	return NewRule(pRule->m, pRule->c);
}

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);
}

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

void FreeRuleList(struct RULE *pRuleList)
/******************************************************
 * 功能：释放动态产生的规则链表                       *
 *                                                    *
 * 入口参数：                                         *
 *   pNodeList：指向规则链表的指针                    *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	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)
/******************************************************
 * 功能：回溯算法主函数                               *
 *                                                    *
 * 入口参数：                                         *
 *   pDataList：指向从初始节点到当前节点的所有节点构成*
 *              链表，当前节点在链表的最前面，初始节点*
 *              在链表的最后面。                      *
 *   bound：算法限制的最大搜索深度                    *
 *                                                    *
 * 返回值：以规则表表示的解路径，或者当求解失败时返回 *
 *         FAIL                                       *
 *                                                    *
 * 说明：当该函数成功结束时，即找到了一条解路径时，将 *
 *       释放掉包括初始节点在内的所有动态产生的节点； *
 *       但是当该函数失败结束时，初始节点将不被释放， *
 *       需要在函数外额外释放                         *
 ******************************************************/
{
	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;	//获取所有规则
	
	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;

	g_pRuleSet = InitRules();	//初始化规则集
	
	pData = NewNode(M, C, 1);	//设置初始节点

	pPath = Backtrack1(pData, 20);	//调用回溯程序

	PrintRuleList(pPath);	//显示解路径

	if (pPath == FAIL)	//当求解失败时
	{
		free(pData);	//释放初始节点
	}
	FreeRuleList(pPath);	//释放解路径
	FreeRuleList(g_pRuleSet);	//释放规则集
}