/**
?*?實(shí)現(xiàn)Inter.java接口中的函數(shù)
?*?不要添加?package語句
?*/

import?java.util.*;
import?java.io.*;



public?class?AbPruning?implements?Inter{
	/**
	?*?不要定義static?的變量
	?*/
			
	
	
	
	final?int?MAX_INT=32767;??	//定義最大整數(shù)
	final?int?MIN_INT=-32768;	//定義最小整數(shù)
	final?int?MAX=1;			//極大層節(jié)點(diǎn)標(biāo)志
	final?int?MIN=0;			//極小層節(jié)點(diǎn)標(biāo)志
	
	/**
	?*?以下結(jié)構(gòu)定義了樹結(jié)構(gòu)的一個節(jié)點(diǎn)。
	?*/
	public?class?Node
	{
		private?String?name;??//節(jié)點(diǎn)名
		private?int?value;??//節(jié)點(diǎn)的值，在實(shí)際博弈程序中并不需要該值，這里為了顯示得到的每個節(jié)點(diǎn)
							//的倒推值，設(shè)置了該域。
		private?int?leval;//節(jié)點(diǎn)處在極大層，還是在極小層
		private?String?pFather;//該節(jié)點(diǎn)的父親名字是什么
		private?ArrayList?pChildren;//該節(jié)點(diǎn)的子節(jié)點(diǎn)
		
		Node（String?name）
		{
			this.name=name;	
			value=-1;
			pFather=new?String（）;
			pChildren=new?ArrayList（）;
		}
		
	}


	private?ArrayList?NodeTree;
	private?String?jianzhi[];???//存儲剪枝的結(jié)果
	private?int?count;
	
	public?void?getStrategy（String?inputFile）{		
		/**說明：
			這里是你的實(shí)現(xiàn)，對輸入文件中描述的博弈樹進(jìn)行alpha-beta剪枝并輸出剪枝后的結(jié)果
			
			輸入輸出格式見作業(yè)文檔，輸出用系統(tǒng)標(biāo)準(zhǔn)輸出System.out
			
			your?code?here
			
			*/
		
		NodeTree=new?ArrayList（）;
		jianzhi=new?String[20];
		count=0;
		readTree（inputFile）;
		/*for（int?i=0;i			{
			????System.out.print（NodeTree.get（i）.name+“?“+NodeTree.get（i）.value+“?“+NodeTree.get（i）.pFather）;
			????for（int?j=0;j			????	System.out.print（“?“+NodeTree.get（i）.pChildren.get（j））;
			????System.out.println（）;
			}*/
		Alph_Beta（NodeTree.get（0）.name）;???//根節(jié)點(diǎn)開始用Alpha_Beta算法
		//System.out.println（count）;
		String?bestRoute=““;
		for（int?i=0;i		{
			if（NodeTree.get（0）.value==NodeTree.get（search（NodeTree.get（0）.pChildren.get（i）））.value）
				{
					bestRoute=NodeTree.get（0）.name+“?“+NodeTree.get（0）.value+“?“+NodeTree.get（search（NodeTree.get（0）.pChildren.get（i）））.name;
					break;
				}
				
		}
		System.out.println（bestRoute）;
		for（int?i=0;i			{
				System.out.println（jianzhi[i]）;
			}
			
	}
	void?Alph_Beta（String?str）?????//如考參數(shù)為節(jié)點(diǎn)名
	{
		boolean?flag=false;
		Node?nNode=NodeTree.get（search（str））;
		/*System.out.print（nNode.name+“?“+nNode.leval+“?“+nNode.pFather）;
		for（int?j=0;j	????	System.out.print（“?“+nNode.pChildren.get（j））;*/
		if（nNode.leval==MAX）??//當(dāng)前節(jié)點(diǎn)是極大點(diǎn)
		{
			for（int?i=0;i			{
				Alph_Beta（nNode.pChildren.get（i））;//遞歸對子節(jié)點(diǎn)進(jìn)行算法計(jì)算
				if（nNode.value				{
					nNode.value=NodeTree.get（search（nNode.pChildren.get（i）））.value;//將子節(jié)點(diǎn)的值給父親節(jié)點(diǎn)
					if（Beta（str））//是否在極大點(diǎn)出執(zhí)行Beta剪枝
					{
						//在此處執(zhí)行剪枝，則該節(jié)點(diǎn)后面的兄弟節(jié)點(diǎn)都被剪去
						jianzhi[count]=str+“:“;
						for（int?j=i+1;j						{
							//System.out.println（nNode.pChildren.get（j））;
							jianzhi[count]=jianzhi[count]+“?“+nNode.pChildren.get（j）;
							flag=true;
						}
						if（flag==true）
						{	
							co

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????7495??2009-11-25?16:06??新建文件夾\AbPruning.java

?????文件????????152??2009-11-11?00:59??新建文件夾\Inter.java

?????文件????????287??2009-11-25?16:05??新建文件夾\Test.java

?????文件????????472??2009-09-23?00:08??新建文件夾\tree1.txt

?????文件???????1187??2009-09-23?00:08??新建文件夾\tree2.txt

?????目錄??????????0??2009-11-30?19:49??新建文件夾

-----------?---------??----------?-----??----

?????????????????9593????????????????????6