alpha_beta.cpp

对树剪枝算法

#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;				//节点的值
	int level;				//节点处在极大层，还是极小层
	struct NODE *pFrom;		//该节点的值来自于哪个子节点
	struct NODE *pFather;	//指向父节点
	struct NODE *pChildren; //指向子节点链表
	struct NODE *pNext;		//指向兄弟链表的下一个节点
};

//动态产生一个节点
struct NODE *NewNode(char *name, int level)
{
	struct NODE *pNode = NULL;
	pNode = (NODE*)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)
{
	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)
{
	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 PrintTreeRoot(struct NODE *pRoot)
{
	if (pRoot == NULL) 
		return;	
	printf("根节点: %s\n", pRoot->name);	//显示根节点的名字
	printf("倒推值: %d\n", pRoot->value);
	printf("应走的步骤: %s\n", pRoot->pFrom->name);
}

//释放动态产生的树 
void FreeTree(struct NODE *pRoot)
{
	struct NODE *pChildren = NULL, *pNext = NULL;
	if (pRoot == NULL) return;
	pChildren = pRoot->pChildren;
	pNext = pRoot->pNext;
	free(pRoot);	//释放根节点
	FreeTree(pChildren);	//递归释放根节点的子节点
	FreeTree(pNext);	//递归释放根节点的兄弟节点
}

//判断在给定的节点处是否可以发生剪枝
int CutP(struct NODE *pNode)
{
	int value;
	int level;

	if (pNode == NULL) return 0;
	value = pNode->value;
	level = pNode->level;
	//printf("First : %s\n" , pNode->name);
	
	while (pNode)
	{
		if(pNode->pFather == NULL)
		{
			//printf("pNode->pFather == NULL\n");
			return 0;
		}
		pNode = pNode->pFather;			
		if(level == MAX)
		{	
			//printf("level == MAX\n");
			while(pNode->pFather != NULL && (pNode->value == MAX_INT || pNode->value == MIN_INT))
			{
				//printf("MAX:pNode->name : %s\n", pNode->name);
				pNode = pNode->pFather;
			}
			if(pNode->level == MIN && value >= pNode->value)
			{
				//printf("CUT:%d\n",value);
				//printf("CUT:%d\n",pNode->value);
				//printf("CUT\n");
				return 1;
			}
			//else
			//{
				//printf("NOT:%s\n",pNode->name);
				//printf("NOT:%d\n",value);
				//printf("NOT:%d\n",pNode->value);
				//printf("NOT CUT\n");
				return 0;
			//}
			/*while(pNode!= NULL && pNode->level == MIN && value >= pNode->value && pNode->value!= MIN_INT)
			{
				return 1;
				pNode = pNode->pFather;
			}*/
		}
		if(level == MIN)
		{
			//printf("level == MIN\n");
			while(pNode->pFather != NULL && (pNode->value == MAX_INT || pNode->value == MIN_INT))
			{
				//printf("MIN:pNode->name : %s\n", pNode->name);
				pNode = pNode->pFather;
			}
			if(pNode->level == MAX && value <= pNode->value)
			{
				//printf("%s\n",pNode->level);
				//printf("CUT:%d\n",value);
				//printf("CUT:%d\n",pNode->value);
				//printf("CUT\n");
				return 1;
			}
			else 
			{
				//printf("NOT:%s\n",pNode->name);
				//printf("NOT:%d\n",value);
				//printf("NOT:%d\n",pNode->value);
				//printf("NOT CUT\n");
				return 0;
			}
			/*while(pNode!= NULL && pNode->level == MAX && value <= pNode->value && pNode->value != MAX_INT)
			{
				return 1;
				pNode = pNode->pFather;
			}*/
		}
		//pNode = pNode->pFather;
		/*if (pNode == NULL) return 0;

		if (pNode->value == MAX_INT ||
			pNode->value == MIN_INT)
		{
			return 0;	//如果祖先节点还没有值，则不发生剪枝
		}

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

//打印剪枝
void Cut(struct NODE *pNode, struct NODE *pChildren)
{
	printf("剪枝 %s: ", pNode->name);
	while (pChildren)
	{
		printf("%s ", pChildren->name);
		pChildren = pChildren->pNext;
	}
	printf("\n");
}

//Alpha_Beta剪枝主函数
int Alpha_Beta(struct NODE *pRoot)
{
	struct NODE *pNode = NULL;
	int value;

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

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

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

	char filename[10];
	scanf("%s",filename);
	pFile = fopen(filename, "r");
	if (pFile == NULL)
	{
		printf("文件打开错误!\n");
	}
	else
	{
		pRoot = ReadTree(pFile);	//从文件中读入树结构
		fclose(pFile);
		if (pRoot == NULL)
		{
			printf("读数据文件错误!\n");
		}
		else
		{
			Alpha_Beta(pRoot);	//对该树进行Alpha_Beta剪枝
			PrintTreeRoot(pRoot);
			FreeTree(pRoot);	//释放动态产生的树
		}
	}
}