alpha_beta_1.c

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

/*********************************************************************************
 *          程  序  说  明                                                       *
 * 功能: Alpha_Beta剪枝程序，该程序只涉及剪枝部分，不涉及博弈部分的内容。        *
 *       该程序是对Alpha_Beta.c程序的改进，效率有所提高。                        *
 *                                                                               *
 * 说明:                                                                         *
 *     本程序实现《人工智能导论》一书所介绍Alpha_Beta剪枝算法，不涉及具体的博弈  *
 *     问题，博弈树用一个给定的树代替。                                          *
 *     树用文件表示，读入内容后建立树结构。                                      *
 *     文件的表示如下：                                                          *
 *                                                                               *
 *     ROOT A			//表示A是根节点                                          *
 *     A B1 B2 B3 END	//A的子节点为B1 B2 B3                                    *
 *     B1 C1 C2 END		//B1的子节点为C1 C2                                      *
 *     B2 C3 C4 C5 END	//B2的子节点为C3 C4 C5                                   *
 *     ......                                                                    *
 *     VALUE			//赋值标志，为叶节点赋估计值                             *
 *     D1 7				//D1的估计值为7                                          *
 *     D2 8				//D2的估计值为8                                          *
 *     D3 -4			//D3的估计值为-4                                         *
 *     ......                                                                    *
 *     END				//结束标志                                               *
 *                                                                               *
 *     tree1.txt和tree2.txt是两个给定的树文件的例子。                            *
 * 说明: 该程序没有严格按照《人工智能导论》中算法实现，但是思路是一样的。        *
 *       该程序中，通过一个极大过程和一个极小过程，相互递归调用实现Alpha_Beta剪枝*
 *       并通过将祖先中的最好的Alpha值和Beta想后代传递的方法，实现是否需要剪枝， *
 *       从而避免了每次判断剪枝时，需要从当前节点，一步步向祖先搜索，与祖先的    *
 *       Alpha（Beta）值进行比较的过程，从而提高了搜索的效率。                   *
 *       该程序参考了北京邮电大学出版社的《人工智能——一种现代方法（第二版）》  *
 *       中，有关Alpha－Beta剪枝部分的内容。                                     *
 *                                                                               *
 * 作者：马少平                                                                  *
 * 单位：清华大学智能技术与系统国家重点实验室                                    *
 * 时间：2004年8月15日                                                           *
 * 修改：2005年9月14日                                                           *
 *********************************************************************************/

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

#define		MAX_INT	 32767		//定义最大整数
#define		MIN_INT -32768		//定义最小整数
#define		MAX			 1		//极大层节点标志
#define		MIN			 0		//极小层节点标志

//以下结构定义了树结构的一个节点。
//树结构的表示如下：
//每个节点指向其父节点
//每个节点指向其子节点链表
//一个节点的所有子节点，形成一个兄弟链表，其父节点指向该兄弟链表的第一个
//节点，但是兄弟链表中的每个节点，都指向其父节点
struct NODE
{
	char name[10];			//节点名
	int value;				//节点的值，在实际的博弈程序中并不需要该值，这里为了显示得到的每个节点
	                        //的倒推值，设置了该域。
	                        //下面的level/pFrom域，也是同样的作用。
	int level;				//节点处在极大层，还是极小层
	struct NODE *pFrom;		//该节点的值来自于哪个子节点
	struct NODE *pFather;	//指向父节点
	struct NODE *pChildren; //指向子节点链表
	struct NODE *pNext;		//指向兄弟链表的下一个节点
};

struct NODE *NewNode(char *name, int level)
/******************************************************
 * 功能：动态产生一个节点，其状态值由参数name、level  *
 *       给定。                                       *
 *                                                    *
 * 入口参数：                                         *
 *   name：节点名                                     *
 *   level：节点是极大节点还是极小节点                *       
 *                                                    *
 * 返回值：指向新产生的节点的指针，或者空间不够时，返 *
 *         回NULL                                     *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	pNode = malloc(sizeof(struct NODE));
	if (pNode == NULL) return NULL;
	strcpy(pNode->name, name);
	if (level == MAX) 
	{
		pNode->value = MIN_INT;
	}
	else 
	{
		pNode->value = MAX_INT;
	}
	pNode->level = level;
	pNode->pFrom = NULL;
	pNode->pFather = NULL;
	pNode->pChildren = NULL;
	pNode->pNext = NULL;
	return pNode;
}

struct NODE *Search(char *name, struct NODE *pTree)
/******************************************************
 * 功能：从已经建立的树中，查找给定名字的节点，并返回 *
 *       指向该节点的指针                             *
 *                                                    *
 * 入口参数：                                         *
 *   name：节点名                                     *
 *   pTree: 指向树根节点的指针                        *
 *                                                    *
 * 返回值：指向给定节点的指针                         *
 ******************************************************/
{
	struct NODE *pNode = NULL;
	if (pTree == NULL) return NULL;
	if (! strcmp(name, pTree->name)) return pTree;	//如果根节点就是待查找的节点，则返回该节点
	if (pNode = Search(name, pTree->pNext))	//否则从该节点的兄弟节点中递归查找
	{
		return pNode;	//如果找到，则返回该节点
	}
	if (pNode = Search(name, pTree->pChildren))	//否则在子节点中递归查找
	{
		return pNode;	//如果找到则返回该节点
	}
	return NULL;	//以上均找不到的话则返回NULL
}

struct NODE *ReadTree(FILE *pFile)
/******************************************************
 * 功能：从一个文本文件中读入一个树                   *
 *                                                    *
 * 入口参数：                                         *
 *   pFile：文件指针                                  *
 *                                                    *
 * 返回值：返回指向树根节点的指针，或者空间不够时，返 *
 *         回NULL                                     *
 *                                                    *
 * 文本文件格式说明：                                 *
 *     ROOT A			//表示A是根节点               *
 *     A B1 B2 B3 END	//A的子节点为B1 B2 B3         *
 *     B1 C1 C2 END		//B1的子节点为C1 C2           *
 *     B2 C3 C4 C5 END	//B2的子节点为C3 C4 C5        *
 *     ......                                         *
 *     VALUE			//赋值标志，为叶节点赋估计值  *
 *     D1 7				//D1的估计值为7               *
 *     D2 8				//D2的估计值为8               *
 *     D3 -4			//D3的估计值为-4              *
 *     ......                                         *
 *     END				//结束标志                    *
 ******************************************************/
{
	char name[256];
	int value;
	struct NODE *pNode = NULL, *pRoot = NULL, *pFNode = NULL, *pLast = NULL;

	//在树文件中，寻找ROOT标志
	while (!feof(pFile))
	{
		fscanf(pFile, "%s", name);
		if (feof(pFile)) return NULL;
		if (! strcmp(name, "ROOT")) break;
	}

	fscanf(pFile, "%s", name);	//得到根节点名字
	pRoot = NewNode(name, MAX);	//建立根节点
	if (pRoot == NULL) return NULL;	//如果空间不够则返回NULL

	//读文本文件，建立树结构
	while (!feof(pFile))
	{
		fscanf(pFile, "%s", name);	//name得到父节点名字
		if (feof(pFile)) return NULL;
		if (! strcmp(name, "VALUE")) break;
		pFNode = Search(name, pRoot);	//得到父节点在树中的指针
		if (pFNode == NULL) return NULL;	//如果树中不存在该节点则返回NULL

		pLast = NULL;

		//读子节点，建立父子关系和兄弟关系
		while (!feof(pFile))
		{
			fscanf(pFile, "%s", name);	//得到子节点名
			if (feof(pFile)) return NULL;
			if (! strcmp(name, "END")) break;
			pNode = NewNode(name, !pFNode->level);	//建立子节点
			if (pNode == NULL) return NULL;	//空间不够用时返回NULL

			if (pLast == NULL)	//如果是第一个子节点，其父节点指向该节点
			{
				pFNode->pChildren = pNode;
			}
			else
			{
				pLast->pNext = pNode;	//否则将该节点链接到兄弟链表中
			}
			pLast = pNode;
			pNode->pFather = pFNode;	//设置该节点的父节点
		}
	}

	//为叶节点赋初始估计值
	while (!feof(pFile))
	{
		fscanf(pFile, "%s", name);	        //得到叶节点名
		if (feof(pFile)) return NULL;
		if (! strcmp(name, "END")) break;	//END为结束标志
		fscanf(pFile, "%d", &value);	    //得到叶节点的初始估计值
		if (feof(pFile)) return NULL;
		pNode = Search(name, pRoot);	    //从树中得到该节点的指针
		if (pNode == NULL) return NULL;	    //如果树中没有该节点，则返回NULL
		pNode->value = value;	            //为该节点赋初始估计值
	}

	return pRoot;	//返回树根节点
}

void PrintTree(struct NODE *pRoot)
/******************************************************
 * 功能：显示一个树                                   *
 *                                                    *
 * 入口参数：                                         *
 *   pTree: 指向树根节点的指针                        *
 *                                                    *
 * 返回值：无                                         *
 * 说明：显示格式如下(举例)：                         *
 * A:                                                 *
 *	  Childtren: B1(0) B2(1) B3(-1)                   *
 *	  level: 1                                        *
 *	  value: 1                                        *
 *	  from: B2                                        *
 * B1:                                                *
 *	  Childtren: C1(0) C2(2)                          *