α-β剪枝算法的Java语言实现

利用α-β剪枝算法，对下图所示的博弈树进行搜索，搜索得到根节点选择的走步，以及没有必要进行评估的节点，并求出给出在何处发生了剪枝，以及剪枝的类型（属于α剪枝还是β剪枝）。注：□表示MIN节点；○表示MAX节点public interface Interface{public void getStrategy（String InputFile）;} import java.util.*;import java.io.*;public class AlphaBeta implements Interface{final int MAX_INT=32767; final int MIN_INT=-32768;final int MAX=1; //极大节点final int MIN=0;//极小节点public class Node{private String name;private int value;private int leval;//节点判断极大层还是极小层private String pFather;private ArrayList<String> pChildren;Node（String name）{this.name=name;value=-1;pFather=new String（）;pChildren=new ArrayList<String>（）;}}private ArrayList<Node> NodeTree;private String jianzhi[]; private int count;public void getStrategy（String inputFile）{NodeTree=new ArrayList<Node>（）;jianzhi=new String[20];count=0;readTree（inputFile）;Alph_Beta（NodeTree.get（0）.name）; System.out.println（count）;String bestRoute="";for（int i=0;i<NodeTree.get（0）.pChildren.size（）;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<count;i++）{System.out.println（jianzhi[i]）;}}void Alph_Beta（String str） {boolean flag=false;Node nNode=NodeTree.get（search（str））;if（nNode.leval==MAX）{for（int i=0;i<nNode.pChildren.size（）;i++） {Alph_Beta（nNode.pChildren.get（i））;if（nNode.value<NodeTree.get（search（nNode.pChildren.get（i）））.value）{nNode.value=NodeTree.get（search（nNode.pChildren.get（i）））.value;if（Beta（str））//是否在极大点出执行Beta剪枝{jianzhi[count]=str+":";for（int j=i+1;j<nNode.pChildren.size（）;j++）{jianzhi[count]=jianzhi[count]+" "+nNode.pChildren.get（j）+" β剪枝 ";flag=true;}if（flag==true）{count++;}return;}}}}else {for（int i=0;i<nNode.pChildren.size（）;i++）{Alph_Beta（nNode.pChildren.get（i））;if（nNode.value>NodeTree.get（search（nNode.pChildren.get（i）））.value）{nNode.value=NodeTree.get（search（nNode.pChildren.get（i）））.value;if（Alpha（str））{jianzhi[count]=str+":";for（int j=i+1;j<nNode.pChildren.size（）;j++）{jianzhi[count]=jianzhi[count]+" "+nNode.pChildren.get（j）+" α剪枝";flag=true;}if（flag==true）{count++;}return;}}}}}boolean Alpha（String str）{Node nNode=NodeTree.get（search（str））;if（nNode.pFather==null） {return false;}int i=search（nNode.pFather）;while（i>=0）{if（（NodeTree.get（i）.value>=nNode.value）&&（NodeTree.get（i）.leval==MAX）&&（（NodeTree.get（i）.value！=MIN_INT）））return true;else{if（i！=0）{i=search（NodeTree.get（i）.pFather）;//其祖先节点}elsebreak;}}return false;}boolean Beta（String str）{Node nNode=NodeTree.get（search（str））;if（nNode.pFather==null）{return false;}int i=search（nNode.pFather）;while（i>=0）{if（（NodeTree.get（i）.value<=nNode.value）&&（NodeTree.get（i）.leval==MIN）&&（（NodeTree.get（i）.value！=MAX_INT）））return true;else{if（i！=0）{i=search（NodeTree.get（i）.pFather）;}elsebreak;}}return false;}public void readTree（String filename）{File file=new File（filename）;String nodename[]=new String[10];try{BufferedReader in=new BufferedReader（new FileReader（file））;String s;s=in.readLine（）;if（s.startsWith（"ROOT"））{nodename=s.split（"\s+"）;}NodeTree.add（new Node（nodename[1]））; NodeTree.get（0）.leval=MAX;NodeTree.get（0）.value=MIN_INT;NodeTree.get（0）.pFather=null;while（！（s=in.readLine（））.equals（"VALUE"））{nodename=s.split（"\s+"）; for（int i=1;i<nodename.length-1;i++） {NodeTree.get（search（nodename[0]））.pChildren.add（nodename[i]）;Node nNode=new Node（nodename[i]）;//value为-1；nNode.pFather=nodename[0];if（NodeTree.get（search（nodename[0]））.leval==MAX）{nNode.leval=MIN;nNode.value=MAX_INT;}else{nNode.leval=MAX;nNode.value=MIN_INT;}NodeTree.add（nNode）;}}String nodeValue[]=new String[10];while（！（s=in.readLine（））.equals（"END"））{nodeValue=s.split（"\s+"）;NodeTree.get（search（nodeValue[0]））.value=Integer.parseInt（nodeValue[1]）;}in.close（）;}catch（Exception e）{System.out.println（"Error！！"）;}}int search（String str） {for（int i=0;i<NodeTree.size（）;i++）{if（NodeTree.get（i）.name.equals（str））return i;}return -1;}public static void main（String argv[]）{String test= "test.txt";new AlphaBeta（）.getStrategy（test）;}} //test.txt文件ROOT AA B C ENDB D E ENDC F G ENDD H I ENDE J K ENDF L M ENDG N O ENDVALUEH 4I 1J 5K 0L 3M 2N 7O 1END 结果：本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-12/139008.htm