alpha_beta_1.c

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

 *	  level: 0                                        *
 *	  value: 0                                        *
 *	  from: C1                                        *
 *	  ......                                          *
 * 以上例子说明，A是一个节点，它有B1、B2、B3三个字节点*
 * 这三个子节点的倒推值分别为0、1、-1，“level: 1”表 *
 * 示A属于极大节点（如果是“level: 0”则表示属于极小节*
 * 点），“value: 1”表示A的倒推值是1，“from: C1”表 *
 * 示A的倒推值来自于C1节点。                          *
 ******************************************************/
{
	struct NODE *pChildren = NULL;

	if (pRoot == NULL) return;
	
	printf("%s:", pRoot->name);	//显示根节点的名字
	pChildren = pRoot->pChildren;
	
	if (pChildren) printf("\n	Childtren:");
	
	//依次显示根节点的子节点
	while (pChildren)
	{
		//采用“节点名（值）”的格式显示字节点
		printf(" %s(%d)", pChildren->name, pChildren->value);
		pChildren = pChildren->pNext;
	}
	
	printf("\n");
	printf("	level: %d\n", pRoot->level);	//显示根节点的所处的层
												//1表示极大层，0表示极小层
	printf("	value: %d\n", pRoot->value);	//显示根节点的值
	if (pRoot->pFrom) printf("	from: %s\n", pRoot->pFrom->name);	//该值来自于哪个子节点
	
	PrintTree(pRoot->pChildren);	//递归显示根节点的子节点信息
	
	PrintTree(pRoot->pNext);	//递归显示根节点的兄弟节点信息
}

void FreeTree(struct NODE *pRoot)
/******************************************************
 * 功能：释放动态产生的树                             *
 *                                                    *
 * 入口参数：                                         *
 *   pRoot: 指向树根节点的指针                        *
 *                                                    *
 * 返回值：无                                         *
 ******************************************************/
{
	struct NODE *pChildren = NULL, *pNext = NULL;
	if (pRoot == NULL) return;
	pChildren = pRoot->pChildren;
	pNext = pRoot->pNext;
	free(pRoot);	//释放根节点
	FreeTree(pChildren);	//递归释放根节点的子节点
	FreeTree(pNext);	//递归释放根节点的兄弟节点
}

void Prune(struct NODE *pNode, struct NODE *pChildren)
/******************************************************
 * 功能：发生剪枝。由于此程序是模拟剪枝过程，因此在这 *
 *       里显示在哪个节点发上了剪枝，哪些子节点被剪掉 *
 *       了                                           *
 *                                                    *
 * 入口参数：                                         *
 *   pNode：发生剪枝的节点指针                        *
 *   pChildren: 被剪掉的子节点                        *
 *                                                    *
 * 返回值：无                                         *
 *                                                    *
 * 说明：                                             *
 *   显示格式为：                                     *
 *   剪枝 <发生剪枝的节点>: {被剪掉的子节点}+         *
 ******************************************************/
{
	printf("剪枝 %s: ", pNode->name);
	while (pChildren)
	{
		printf("%s ", pChildren->name);
		pChildren = pChildren->pNext;
	}
	printf("\n");
}

int Min_Value(struct NODE *pNode, int nAlpha, int nBeta);

int Max_Value(struct NODE *pNode, int nAlpha, int nBeta)
/*******************************************************
 * 功能：通过递归调用，求解给定极大节点的倒推值        *
 *                                                     *
 * 入口参数：                                          *
 *   pNode: 当前节点，该节点是一个极大值点             *
 *   nAlpha: 当前节点的所有祖先节点中，最大的alpha值   *
 *   nBeta: 当前节点的所有祖先节点中，最小的beta值     *
 *                                                     *
 * 返回值：当前节点的倒推值                            *
 *******************************************************/
{
	int value = MIN_INT, v;
	struct NODE *p = NULL;

	if (pNode->pChildren == NULL) //如果当前节点是叶节点，则直接返回它的值
	{
		return pNode->value;
	}
	
	p = pNode->pChildren;

	// 对于当前节点的所有子节点，求他们的最小值，并判断能否剪枝
	while (p != NULL)
	{
		v = Min_Value(p, nAlpha, nBeta);

		if (v > value)  //对于极大点，取其子节点中值最大的，并记录其来源
		{
			value = v;
			pNode->value = v;
			pNode->pFrom = p;
		}

		p = p->pNext;

		if (value >= nBeta)  //判断是否满足剪枝条件
		{
			if (p != NULL)
			{
				Prune(pNode, p);  //当剪枝时，显示剪枝结果
			}

			return value;  //得到当前节点的最大值
		}

		nAlpha = max(value, nAlpha); 
	}

	return value;  //返回当前节点的最大值
}

int Min_Value(struct NODE *pNode, int nAlpha, int nBeta)
/*******************************************************
 * 功能：通过递归调用，求解给定极小节点的倒推值        *
 *                                                     *
 * 入口参数：                                          *
 *   pNode: 当前节点，该节点是一个极小值点             *
 *   nAlpha: 当前节点的所有祖先节点中，最大的alpha值   *
 *   nBeta: 当前节点的所有祖先节点中，最小的beta值     *
 *                                                     *
 * 返回值：当前节点的倒推值                            *
 *******************************************************/
{
	int value = MAX_INT, v;
	struct NODE *p = NULL;

	if (pNode->pChildren == NULL) //如果当前节点是叶节点，则直接返回它的值
	{
		return pNode->value;
	}
	
	p = pNode->pChildren;

	// 对于当前节点的所有子节点，求他们的最小值，并判断能否剪枝
	while (p != NULL)
	{
		v = Max_Value(p, nAlpha, nBeta);

		if (v < value)  //对于极小点，取其子节点中值最小的，并记录其来源
		{
			value = v;
			pNode->value = v;
			pNode->pFrom = p;
		}

		p = p->pNext;

		if (value <= nAlpha)  //判断是否满足剪枝条件
		{
			if (p != NULL)
			{
				Prune(pNode, p);  //当剪枝时，显示剪枝结果
			}

			return value;  //得到当前节点的最小值
		}

		nBeta = min(value, nBeta); 
	}

	return value;  //返回当前节点的最小值
}

int Alpha_Beta_Search(struct NODE *pRoot)
/*******************************************************
 * 功能：Alpha_Beta剪枝主函数                          *
 *                                                     *
 * 入口参数：                                          *
 *   pRoot: 指向树根节点的指针                         *
 *                                                     *
 * 返回值：根节点的倒推值                              *
 *******************************************************/
{
	return Max_Value(pRoot, MIN_INT, MAX_INT);
}

void main(void)
{
	FILE *pFile;
	struct NODE *pRoot;

	pFile = fopen("tree1.txt", "r");	//打开纪录树信息的文本文件

	if (pFile == NULL)
	{
		printf("文件打开错误!\n");
	}
	else
	{
		pRoot = ReadTree(pFile);	//从文件中读入树结构
		fclose(pFile);
		if (pRoot == NULL)
		{
			printf("读数据文件错误!\n");
		}
		else
		{
			Alpha_Beta_Search(pRoot);	//对该树进行Alpha_Beta剪枝
			PrintTree(pRoot);	//显示该树信息
			FreeTree(pRoot);	//释放动态产生的树
		}
	}
}