alpha_beta.c

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

 *	  Childtren: B1(0) B2(1) B3(-1)                   *
 *	  level: 1                                        *
 *	  value: 1                                        *
 *	  from: B2                                        *
 * B1:                                                *
 *	  Childtren: C1(0) C2(2)                          *
 *	  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节点。                          *
 *                                                    *
 * 值为32767或者－32768的节点，为被剪掉的节点。       *
 ******************************************************/
{
	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);	//递归释放根节点的兄弟节点
}

int PruneTest(struct NODE *pNode)
/******************************************************
 * 功能：判断在给定的节点处是否可以发生剪枝           *
 *                                                    *
 * 入口参数：                                         *
 *   pTree: 指向给定节点的指针                        *
 *                                                    *
 * 返回值：1/0表示发生或者不发生剪枝                  *
 ******************************************************/
{
	int value;
	int level;

	if (pNode == NULL) return 0;
	value = pNode->value;
	level = pNode->level;
	
	while (pNode)
	{
		pNode = pNode->pFather;

		if (pNode == NULL) return 0;

		if (level == MAX)	//对于极大节点
		{
			if (value >= pNode->value)	//如果当前值大于其祖先极小节点的值，
			{
				return 1;	//则发生剪枝
			}
		}
		else	//对于极小节点
		{
			if (value <= pNode->value)	//如果当值小于其祖先极大节点的值
			{
				return 1;	//则发生剪枝
			}
		}
		pNode = pNode->pFather;
	}	
	return 0;
}

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 Alpha_Beta_Search(struct NODE *pRoot)
/******************************************************
 * 功能：Alpha_Beta剪枝主函数                         *
 *                                                    *
 * 入口参数：                                         *
 *   pRoot: 指向树根节点的指针                        *
 *                                                    *
 * 返回值：根节点的值                                 *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	int value;

	//如果根节点没有子节点，则其值就是该节点的指
	if (pRoot->pChildren == NULL)
	{
		return pRoot->value;
	}

	pNode = pRoot->pChildren;	
	while (pNode)
	{
		value = Alpha_Beta_Search(pNode);	//对于根节点的子节点，递归计算其值
		if (pRoot->level == MAX)	//对于极大节点
		{
			if (value > pRoot->value)	//如果子节点的值大于当前节点的值 
			{
				pRoot->value = value;	//则用其子节点的值代替
				pRoot->pFrom = pNode;	//标记该值的出处
				if (pNode->pNext && PruneTest(pRoot))	//如果其子节点还有没有扩展的兄弟节点
													//并且当前节点满足剪枝条件
				{
					Prune(pRoot, pNode->pNext);	//则进行剪枝
					return value;	//返回得到的值
				}
			}
		}
		else	//对于极小节点
		{
			if (value < pRoot->value)	//如果子节点的值小于当前节点的值
			{
				pRoot->value = value;	//则用其子节点的值代替
				pRoot->pFrom = pNode;	//标记该值的出处
				if (pNode->pNext && PruneTest(pRoot))	//如果其子节点还有没有扩展的兄弟节点
													//并且当前节点满足剪枝条件
				{
					Prune(pRoot, pNode->pNext);	//则进行剪枝
					return value;	//返回得到的值
				}
			}
		}
		pNode = pNode->pNext;	//试探下一个兄弟节点
	}
	return pRoot->value;
}

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);	//释放动态产生的树
		}
	}
}