breadthtest.java

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

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


   
 class State//状态图的某一个结点
{
	//varibles
	 int numArray[][]=new int[3][3];
	 int LevelDepth;
	 Location zerol=new Location();
	 
	 State fatherS;//上层的状态，记录路径
   //methods
     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);
	    	
	 }
   	  
   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 equal(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 Table
{
    //varible
	  State table[]=  new State[100000];
	  int t_head;
	  int t_tail;
	  
	  //methods
	  public Table( )//初始化表的大小
	  {
	  	t_head=0;//只是从头部提取的过程中用到了
	  	t_tail=-1;
	  }
	  
	  public boolean inTable(State obj)//状态obj是否在表中
	  { 
	  	 int i;
	  	 if(t_tail==-1)//表中暂无元素
	  	   return false;
	  	 else
	  	  {
	  	  	for(i=t_head;i<=t_tail;i++)
	  	  	  if(table[i].equal(obj))
	  	  	     return true;
	  	  }
	  	  return false;
	  }
	  
	  public State removeHead()
	  {
	  	t_head++;
	  	return table[t_head-1];
	  }
	  
	  public  void addTail(State obj)
	  {
	   	t_tail++;
	    table[t_tail]=obj;
	  }//end of addTail
	  
}//end of table

class BreadthSearch
{
	  //varible

	 State startS;
	 State goalS;
	  
	 Table  openT = new Table();
	 Table  closeT = new Table();

	 public  Table  successP = new Table();
	  
	  //methods
   public BreadthSearch(State start,State end)//construction  method
	  {
	   
	    State test_s;
	    startS=start;
	    goalS=end;
	    
      openT.addTail(startS);
	   // System.out.print(openT.t_tail);
	  }
	
	  
 public void expandNode(State s)//扩展一个结点
	  {
	    int num[][]=new int[3][3];
	    int depth,i,j;
	    int originValue;
	    Location loc_z=new Location();
	    
	  	//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);
	  		
	 // 		s_new.print();//打印出状态信息
	  		
	  		if(!(openT.inTable(s_new)||closeT.inTable(s_new)))//将不在open表和close表中的节点加入open中
	  		  openT.addTail(s_new);
	  	  else s_new=null;
	   }//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);
	//  		s_new.print();//打印出状态信息 test
	  		
	  		if(!(openT.inTable(s_new)||closeT.inTable(s_new)))//将不在open表和close表中的节点加入open中
	  		  openT.addTail(s_new);
	  		else
	  		   s_new=null;
	  	
	  		}//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);
	  //  	s_new.print();//打印出状态信息 test
	  		
	  		if(!(openT.inTable(s_new)||closeT.inTable(s_new)))//将不在open表和close表中的节点加入open中
	  		  openT.addTail(s_new);
	  		else 
	  		  s_new=null;
	  	
	  }//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);
	 //  		s_new.print();//打印出状态信息 test
	  		
	  		if(!(openT.inTable(s_new)||closeT.inTable(s_new)))//将不在open表和close表中的节点加入open中
	  		  openT.addTail(s_new);
	  		else 
	  		  s_new=null;
	 	}//end of if right expand
	  		
	 }//end of expanding process
	 
public boolean SearchSuccess()
	 {
	  	 State s_first;
	  	 State pathState;
	  
  	 while(openT.t_head<=openT.t_tail)//当open表不是空的时候
	    {
	    	s_first=openT.removeHead();//取open表中的第一个结点
	    	
	   // 	s_first.print();
	   // 	goalS.print();
	     if(s_first.LevelDepth>2000)
	        return false;
	    	
	    	if(s_first.equal(goalS))//如果是目标结点的话，停止搜索
	      {
	      	pathState=s_first;
	      	
	      	System.out.println("结果如下：\n");
	       	while(!pathState.equal(startS))
	      	{
	      		successP.addTail(pathState);
	      		pathState=pathState.fatherS;
	      	//	pathState.print();
	      	}//end of while
	      	
	      	if(pathState!=null)//排除目标状态和初始状态相同的情况
	      	  // successP.addTail(startS);
	      	  successP.addTail(pathState);
	      	return true;
	    
	     }//end of if ,success 将路径加入到successPath中
	    	    
	    	expandNode(s_first);
	    	closeT.addTail(s_first);
	    }//end of while
	   
	    return false;//not found
	    
 }//end of Search
 
 
 public void getResult()//输出具体的路径
 {
 	 int loc;
 	 loc=successP.t_tail;
 	 
 	 System.out.print("计算过程 :");
 	 while(loc>=successP.t_head)
 	 {
 	 	    successP.table[loc].print();
 	 	    System.out.println();
 	 	    loc--;
 	 	    System.out.println();
 	 }
 	
 } //end of getResult

}

public class BreadthTest
{
	
	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);
		
		
		try
		{
		BreadthSearch testInstance= new BreadthSearch(s,e);
		if(testInstance.SearchSuccess())
		   testInstance.getResult();
		else
		  System.out.print(" 达不到结果！\n");
		}
	  catch(Exception em)
		{
		  	System.out.println("The em is "+em);
	  }
		
	}

}