abt.java

这是人工智能课的一个编程

import java.util.*;
import java.io.*;
   
 class State//状态图的某一个结点
{
	//varibles
	 int numArray[][]=new int[3][3];
	 int LevelDepth;
	 Location zerol=new Location();
	 //
	 int f_value;//计算的f值的关系
	 State fatherS;//上层的状态，记录路径
	 
	 //methods
   //计算g函数值
  public int g_fuc(State obj)
  {
   	return obj.LevelDepth+1;
  }
 
   //计算f函数值
   public int f_fuc(State goal)
   {
   	int dif_value=0;
   	int i,j;
   	for(i=0;i<3;i++)
   	  for(j=0;j<3;j++)
   	    if(numArray[i][j]!=goal.numArray[i][j])
   	      dif_value=dif_value+1;
   	      
   	 return dif_value;
   }
   
   public int caculate_f(State obj,State goal)
   {
   	  return g_fuc(obj)+f_fuc(goal);
  	}
  	
  	public void set_f(int value)
  	{
  		 f_value=value;
  	}
  		
    //状态信息打印 
   public void print()
   {
   	  int i,j;
   	  
   	  System.out.println();
   	  for(i=0;i<3;i++)
	    	{
	    	  for(j=0;j<3;j++)
	    	    System.out.print(numArray[i][j]+" ");
	    	  System.out.println();
	    	}
	    	
	    	System.out.println("0的位置是："+zerol.x+"  "+zerol.y);
	    	System.out.println("深度是： "+LevelDepth);
	    	System.out.println("f值的关系是：" +f_value);
	  }
   	  
   public State(int[][] node,int Depth,State father)//construction method
  {
  	int i,j;
  	for(i=0;i<3;i++)
  	  for(j=0;j<3;j++)
  	   {  if(node[i][j]==0)
  	    	{
  	    		zerol.x=i;
  	    		zerol.y=j;
  	    	}
  	    	numArray[i][j]=node[i][j];
  	    }
  	    
  	 LevelDepth=Depth;
  	 fatherS=father;
  }
  	    		 
  public boolean LeftMovable()//是否可将空格向上移动
	 {
	 	 if(zerol.y-1>=0)
	 	   return true;
	 	 else
	 	   return false;
	 	}
	 	
	 public	boolean RightMovable()//右移
	 	{
	 		if(zerol.y+1<3)
	 		   return true;
	 		else
	 		   return false;
	 	}
	 	
	  public boolean TopMovable()//上移
	 {
	 	 if(zerol.x-1>=0)
	 	   return true;
	 	 else
	 	   return false;
	 	}
	 	
	  public 	boolean DownMovable()//下移
	 	{
	 		if(zerol.x+1<3)
	 		   return true;
	 		else
	 		   return false;
	 	}
	 	
	  public boolean myequal(State obj)//状态是否重复
	 {
	 	  int i,j;
	 	  for(i=0;i<3;i++)
	 	    for(j=0;j<3;j++)
	 	      if(numArray[i][j]!=obj.numArray[i][j])
	 	        return false;
	 	  return true;
	 }
	
}//end of state

 class Location//标志每个格局中0的位置
 {
   	 int x;
   	 int y;
   	public Location()//没有返回值
    {
   	 	 x = -1;
   	 	 y = -1;
   	}
 }

class BreadthSearch
{
	 State startS;
	 State goalS;
	  
	 Vector openT = new Vector(10,1);
	 Vector closeT = new Vector(10,1);
	 Vector successP =new Vector(10,1);
	  
	  //methods
   public BreadthSearch(State start,State end)//construction  method
	  {
	    State test_s;
	    startS=start;
	    goalS=end;
	    
	    openT.addElement(startS);//开始结点放在可变数组中
     }
      
    public State inVector(Vector v ,State s)
     { 
      	int i;
      	for(i=0;i<v.size();i++)
      	  if(((State)(v.elementAt(i))).myequal(s))
      	    return (State)(v.elementAt(i));
      	return null;
      }
      	
	 public void expandNode(State s)//扩展一个结点
	  {
	    int num[][]=new int[3][3];
	    int depth,i,j;
	    int originValue;
	    Location loc_z=new Location();
	    State return_open,return_close;
	    int f_value;
	    
	  	//top expand
	  	if(s.LeftMovable())
	  	{
	  	  State s_new;
	  	  for(i=0;i<3;i++)
	  		  for(j=0;j<3;j++)
	  		    num[i][j]=s.numArray[i][j];
	  		    
	  		loc_z.x=s.zerol.x;
	  		loc_z.y=s.zerol.y-1;
	  		
	  	
	  		originValue=num[loc_z.x][loc_z.y];
	  		num[loc_z.x][loc_z.y]=0;
	  		num[loc_z.x][loc_z.y+1]=originValue;
	  	
	  		depth = s.LevelDepth + 1 ;
	  		s_new=new State(num,depth,s);
	  		
	 		//计算其f_value值,并且加入到s_new中
	   	    f_value=s_new.caculate_f(s,goalS);
	   	    
	  	    return_open=inVector(openT,s_new);
	  	    return_close=inVector(closeT,s_new);
	  	    
	  	    if(return_close==null&&return_open==null)//没有在open表或是在close表中出现的
	  	    {
	  	    	  s_new.set_f(f_value);
	  	        openT.addElement(s_new);
	  	     }
	  	    else if(return_close!=null)
	  	    {
	  	    	if(f_value<return_close.f_value)
	  	    	{
	  	    		 closeT.removeElement(return_close);
	  	    	   return_close.set_f(f_value);
	  	    	   return_close.fatherS=s;
	  	    	   openT.addElement(return_close);
	  	      }
	  	     } else if(return_open!=null)
	  	     {
	  	     	 if(f_value<return_open.f_value)
	  	     	 {
	  	     	 	 return_open.set_f(f_value);
	  	     	 	 return_open.fatherS=s;
	  	     	 	}
	  	     	}
	  	     	 	 
	    }//end of if top expand
	  		
	 	//down expand
	 	if(s.RightMovable())
	   {
	  	  State s_new;
	  	  for(i=0;i<3;i++)
	  		  for(j=0;j<3;j++)
	  		    num[i][j]=s.numArray[i][j];
	  		    
	  		loc_z.x=s.zerol.x;
	  		loc_z.y=s.zerol.y+1;
	  		
	  		originValue=num[loc_z.x][loc_z.y];
	  		num[loc_z.x][loc_z.y]=0;
	  		num[loc_z.x][loc_z.y-1]=originValue;
	  	
	  		depth = s.LevelDepth + 1 ;
	  		s_new=new State(num,depth,s);
	  		
	  		  
	  	    f_value=s_new.caculate_f(s,goalS);
	  	    return_open=inVector(openT,s_new);
	  	    return_close=inVector(closeT,s_new);
	  	    
	  	    if(return_close==null&&return_open==null)//没有在open表或是在close表中出现的
	  	    {
	  	    	  s_new.set_f(f_value);
	  	        openT.addElement(s_new);
	  	     }
	  	    else if(return_close!=null)
	  	    {
	  	    	if(f_value<return_close.f_value)
	  	    	{
	  	    		 closeT.removeElement(return_close);
	  	    	   return_close.set_f(f_value);
	  	    	   return_close.fatherS=s;
	  	    	   openT.addElement(return_close);
	  	   	  }
	  	     } else if(return_open!=null)
	  	     {
	  	     	 if(f_value<return_open.f_value)
	  	     	 {
	  	     	 	 return_open.set_f(f_value);
	  	     	 	 return_open.fatherS=s;
	  	     	 	}
	  	     	}
	  	}//end of if down expand
	  		
	  	//left expand
	  	if(s.TopMovable())
	   {
	  	  State s_new;
	  	  for(i=0;i<3;i++)
	  		  for(j=0;j<3;j++)
	  		    num[i][j]=s.numArray[i][j];
	  		    
	  		loc_z.x=s.zerol.x-1;
	  		loc_z.y=s.zerol.y;
	  		
	  		originValue=num[loc_z.x][loc_z.y];
	  		num[loc_z.x][loc_z.y]=0;
	  		num[loc_z.x+1][loc_z.y]=originValue;
	  	
	  		depth = s.LevelDepth + 1 ;
	  		s_new=new State(num,depth,s);
	  		
	  		  
	  	    f_value=s_new.caculate_f(s,goalS);
	  	    return_open=inVector(openT,s_new);
	  	    return_close=inVector(closeT,s_new);
	  	    
	  	    if(return_close==null&&return_open==null)//没有在open表或是在close表中出现的
	  	    {
	  	    	  s_new.set_f(f_value);
	  	        openT.addElement(s_new);
	  	     }
	  	    else if(return_close!=null)
	  	    {
	  	    	if(f_value<return_close.f_value)
	  	    	{
	  	    		closeT.removeElement(return_close);
	  	    	   return_close.set_f(f_value);
	  	    	   return_close.fatherS=s;
	  	    	   openT.addElement(return_close);
	  	      }
	  	     } else if(return_open!=null)
	  	     {
	  	     	 if(f_value<return_open.f_value)
	  	     	 {
	  	     	 	 return_open.set_f(f_value);
	  	     	 	 return_open.fatherS=s;
	  	     	 	}
	  	     	}
	 	  }//end of if left expand
	  		
	     	//right expand
	  	if(s.DownMovable())
	   {
	  	  State s_new;
	  	  for(i=0;i<3;i++)
	  		  for(j=0;j<3;j++)
	  		    num[i][j]=s.numArray[i][j];
	  		    
	  		loc_z.x=s.zerol.x+1;
	  		loc_z.y=s.zerol.y;
	  		
	  		originValue=num[loc_z.x][loc_z.y];
	  		num[loc_z.x][loc_z.y]=0;
	  		num[loc_z.x-1][loc_z.y]=originValue;
	  	
	  		depth = s.LevelDepth + 1 ;
	  		s_new=new State(num,depth,s);
	  		
	  		  
	  	    f_value=s_new.caculate_f(s,goalS);
	  	    return_open=inVector(openT,s_new);
	  	    return_close=inVector(closeT,s_new);
	  	    
	  	    if(return_close==null&&return_open==null)//没有在open表或是在close表中出现的
	  	    {
	  	    	  s_new.set_f(f_value);
	  	        openT.addElement(s_new);
	  	     }
	  	    else if(return_close!=null)
	  	    {
	  	    	if(f_value<return_close.f_value)
	  	    	{
	  	    		 closeT.removeElement(return_close);
	  	    	   return_close.set_f(f_value);
	  	    	   return_close.fatherS=s;
	  	    	   openT.addElement(return_close);
	  	      }
	  	    } else if( return_open!=null)
	  	     {
	  	     	 if(f_value< return_open.f_value)
	  	     	 {
	  	     	 	 return_open.set_f(f_value);
	  	     	 	 return_open.fatherS=s;
	  	     	 	}
	  	     	}
	 	}//end of if right expand
	  		
	 }//end of expanding process
	 
	 public int getMinInOpen()
	 {
	 	 State temp;
	 	 int i;
	   int i_value=55555,flag=0;
	   for(i=openT.size()-1;i>=0;i--)
	   {
	   	 temp=(State)(openT.elementAt(i));
	     if(temp.f_value<i_value)
	      {
	      	flag = i;
	      	i_value = temp.f_value;
	      }
	    }
	   return flag;
	  }
	     
	     
public boolean SearchSuccess()
	 {
	  	 State s_first;
	  	 State pathState;
	  	 int flag_min;
	  
 	   while(!openT.isEmpty())
	    {
	     //计算其最小应该提取的元素
	    	flag_min=getMinInOpen();
	    	s_first=(State)(openT.elementAt(flag_min));//取open表中的第一个结点
	    	openT.removeElementAt(flag_min);
	    	closeT.addElement(s_first);
	    	
	    	if(s_first.LevelDepth>2000)//人为的界定一个界限防止无解和解路径很长的情况
	    	    return false;
	    	    
	    	if(s_first.myequal(goalS))//如果是目标结点的话，停止搜索
	     	 {
	      	 pathState=s_first;
	      	 System.out.println("\n结果如下：\n");
	       	 while(!pathState.myequal(startS))
	      	 {
	      		successP.addElement(pathState);
	      		pathState=pathState.fatherS;
	       	 }//end of while
	      	
	      	if(pathState!=null)//排除目标状态和初始状态相同的情况
	      	   successP.addElement(pathState);
	      	return true;
	      }//end of if ,success 将路径加入到successPath中
	    
	     expandNode(s_first);
	    }//end of while
    return false;//not found
	    
 }//end of Search
 
 
 public void getResult()//输出具体的路径
 {
 	 State s_temp;
 	 int i;
 	 System.out.print("计算过程 :");
 	 for(i=successP.size()-1;i>=0;i--)
 	 {
 	 	    s_temp = (State)successP.elementAt(i);
 	 	    s_temp.print();
 	 	    System.out.println();
 	 	    System.out.println();
 	 }
 } //end of getResult
}

public class ABT
{
	public static void ReadFormSI(int[][] a)
	{
		int i,j;
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		
		try
		{
			for(i=0;i<3;i++)
			   for(j=0;j<3;j++)
			  {
			    a[i][j]=(char)br.read()-48;//真是比较笨的方法
			  }
		}//end of try
		catch(Exception e)
		{  
			System.out.print("IO 溢出!\n");
	  }
  }//end of ReadFormSI
		
	public static void main(String args[])
	{
		int input_s[][]=new int[3][3];
		int input_d[][]=new int[3][3];
		int i,j;
				
		State s;
		State e;
		
    System.out.print("请输入初始状态：\n");
		ReadFormSI(input_s);
		System.out.print("请输入结果状态：\n");
		ReadFormSI(input_d);
		
		s = new State(input_s,0,null);
		e= new State(input_d,-1,null);
		
		s.set_f(s.f_fuc(e));
		e.set_f(0);
		
		try
		{
		 BreadthSearch testInstance= new BreadthSearch(s,e);
		 if(testInstance.SearchSuccess())
		   testInstance.getResult();
		 else
		   System.out.print(" 不能达到!\n");
		 }
		 catch( Exception  em)
		 {
		 	  System.out.println("The ex is "+em);
		 }
		  
	}//end of main
}//end of ABT