tree.cpp

人工智能的程序,用递归实现了剪枝算法.相信会十分有用的.

#include<iostream>
#include<fstream>
#include<vector>
#include<string>
using namespace std;
class node //表示树结点
{	
public:
	string name;
	int value;
	vector<int> son;//记录子女的下标
	node(string Str,int value=INT_MAX):name(Str),value(value){}	
};

vector<node> tree; //用向量表示树
int Depth=-1;
int best; //记录最优路径

int search(string Str) //查找树结点
{
	for(int i=0;i<tree.size();i++)
		if(tree[i].name==Str)return i;
		return 0;
}

int alpha_beta(int depth,int level,int alpha,int beta,node& Node)//递归剪枝
{
	if(depth==0) //是叶结点
		return Node.value;
	int score;
	for(int i=0;i<Node.son.size();i++) 
	{
		score=-alpha_beta(depth-1,level+1,-beta,-alpha,tree[Node.son[i]]);
		if(score>alpha)
		{
			alpha=score;
			if(level==0) best=Node.son[i]; //记录最优路径
		}
		if(alpha>=beta) //可以剪枝
		{
			if(i+1<Node.son.size()) cout<<"剪枝："<<Node.name<<":";
			for(int k=i+1;k<Node.son.size();k++)
				cout<<tree[Node.son[k]].name<<" ";
		    if(i+1<Node.son.size()) cout<<endl;
			break;
		}
	}
	if(depth==Depth) //是根结点
	{
		cout<<"根结点："<<tree[0].name<<endl;
		cout<<"倒推值："<<alpha<<endl;
	}
	return alpha;
}

int main()
{
	char str[20];
	char file[30];
	cin>>file;
	fstream in(file);
	if(!in) 
	{
		cout<<"找不到文件！"<<endl;
		return 0;
	}
	else //读文件，建树
	{
		int index=0;
		while(in>>str)
		{
			if(strcmp(str,"ROOT")==0) 
			{
				in>>str;
				node Node(str);
				tree.push_back(Node);
				Depth++;
				in>>str;
			}
			else if(strcmp(str,"END")==0)
			{
				in>>str;
				if(strcmp(str,"VALUE")==0)
					break;
				else
					index=search(str);
			}
			else 
			{
				node Node(str);
				tree[index].son.push_back(tree.size());
				tree.push_back(Node);		
			}
		}
		int value;
		string end;
		while(in>>str) //为叶结点赋值
		{
			if(strcmp(str,"END")==0) break;
			else
			{
				index=search(str);
				in>>value;
				tree[index].value=value;
			}
		}
	}
	in.close();
	int f=0;
	while(tree[f].son.size()!=0) //计算树的深度
	{
		f=tree[f].son[0];
		Depth++;
	}
	alpha_beta(Depth,0,-INT_MAX,INT_MAX,tree[0]);
	cout<<"应走步骤:"<<tree[best].name<<endl;
	return 0;
}