problem.java

人工智能中一个关于野人过河的小程序

import com.ms.wfc.ui.*;

public class Problem
{
	Vector stateTree=new Vector();
	
	//int operatNum;
	//int maxLoad;
	int priestNum;
	int wildManNum;
	int counter=0;
	RichEdit richEdit;
	
	Vector operaters=new Vector();
	
	Vector widths=new Vector();
	
	public Problem(int priest,int wildMan,int maxLoad,RichEdit richEdit)
	{this.priestNum=priest;
	 this.wildManNum=wildMan;
	 this.richEdit=richEdit;
	 //this.maxLoad=maxLoad;
	 setOperaters(priest,wildMan,maxLoad);
	 
	 stateTree.addElement(new State(priest,wildMan,1,0,0,-1,-1));
	 widths.addElement(new Integer(1));
	 
	}
	
	private void setOperaters(int A,int B,int maxLoad)
	{int count=0;
	 for(int i=0;i<=A;i++)
	 for(int j=0;j<=B;j++)
	   if((i+j<=maxLoad)&&((i+j)!=0)&&( !((j>i)&&(i!=0)) ))
		 operaters.addElement(new Operater(i,j));
	}

	public boolean extendOneState(int stateIndex,int operaterIndex)
	{State state=((State)stateTree.elementAt(stateIndex));
	 Operater operater=((Operater)operaters.elementAt(operaterIndex));
	 int priestL =state.priestLeft -state.boatLoation*operater.prist;
	 int wildManL=state.wildManLeft-state.boatLoation*operater.wildMan;
	 int priestR =this.priestNum -priestL;
	 int wildManR=this.wildManNum-wildManL;
	 int boat=-state.boatLoation;
	 
	 if((0<=priestL)&&(priestL<=this.priestNum)&&
		( !((priestL<wildManL)&&(priestL!=0)) )&&
		( !((priestR<wildManR)&&(priestR!=0)) ))
	  {stateTree.addElement(new State(priestL,wildManL,boat,priestR,wildManR,stateIndex,operaterIndex));
	   return true;}
	 else return false;
	}
	
	public int firstStateIndexOfCurrentDepth()
	{int count=0;
	 for(int i=0;i<widths.elementCount()-1;i++)
	  {count+=((Integer)widths.elementAt(i)).intValue();}
	 return count;
	}
	
	public void extendOneDepth()
	{int wide=0;
	 for(int i=firstStateIndexOfCurrentDepth();
		 i<firstStateIndexOfCurrentDepth()+((Integer)widths.elementAt(widths.elementCount()-1)).intValue();
		 i++)
	 {
	  for(int j=0;j<operaters.elementCount();j++)
	  { if(extendOneState(i,j)) wide++;}
	  
	  
	 }
	 widths.addElement(new Integer(wide));
	}
	
	public int widthFirstSearch()
	{int i=0;
	 while(i<stateTree.elementCount())
	 {State state=((State)stateTree.elementAt(i));
	  if((state.priestRight==this.priestNum)&&(state.wildManRight==this.wildManNum))
		  break;
	  else i++;
	 }
	 if(i==stateTree.elementCount())
	   return -1;
	 else return i;
	}
	
	public int father(int i)
	{ return ((State)stateTree.elementAt(i)).father;}
	
	
    
	public int getMovmentOfState(int i)
	{return ((State)stateTree.elementAt(i)).movment;}
	
	public void printOperater(int direction,int operateIndex)
	{//if(getDirection(direction)) System.out.print("       ==>");else System.out.print("       <==");
	 //System.out.println(((Operater)operaters.elementAt(operateIndex)).prist+" "+
	//				  ((Operater)operaters.elementAt(operateIndex)).wildMan);
	
		if(((Operater)operaters.elementAt(operateIndex)).prist==0)
			this.richEdit.setText(this.richEdit.getText()+"      "+
								  ((Operater)operaters.elementAt(operateIndex)).wildMan+"个野人");
        else if(((Operater)operaters.elementAt(operateIndex)).wildMan==0)
			this.richEdit.setText(this.richEdit.getText()+"      "+
								  ((Operater)operaters.elementAt(operateIndex)).prist+"个传教士");
            else this.richEdit.setText(this.richEdit.getText()+"      "+
								  ((Operater)operaters.elementAt(operateIndex)).prist+"个传教士和"+
								  ((Operater)operaters.elementAt(operateIndex)).wildMan+"个野人");
		if(getDirection(direction))
			this.richEdit.setText(this.richEdit.getText()+
								  "从左岸乘船渡到右岸。"+"\r\n");
		else this.richEdit.setText(this.richEdit.getText()+
								  "从右岸乘船渡到坐岸。"+"\r\n");
	
	}
	
	public boolean getDirection(int i)
	{if (((State)stateTree.elementAt(i)).boatLoation==-1)
		 return true;
	 else return false;
	}
	
	public void printState(int i)
	{State state=(State)stateTree.elementAt(i);
		//System.out.println("   "+state.priestLeft+" "+state.wildManLeft+"        "
		//				  +state.priestRight+" "+state.wildManRight+"    ");
	 if(state.priestLeft==0&&state.wildManLeft==0)
		  this.richEdit.setText(this.richEdit.getText()+"          最后，所有人都到达了右岸。"+"\r\n");
	 else if(state.priestRight==0&&state.wildManRight==0)
		  this.richEdit.setText(this.richEdit.getText()+"          开始时，所有人都在左岸"+"\r\n");
	 else 
	 {
		  if(state.priestLeft!=0&&state.wildManLeft==0)
		    this.richEdit.setText(this.richEdit.getText()+"          左岸只剩"+state.priestLeft+"个传教士。"+"\r\n");
	 else if(state.priestLeft==0&&state.wildManLeft!=0)
		    this.richEdit.setText(this.richEdit.getText()+"          左岸只剩"+state.wildManLeft+"个野人。"+"\r\n");
     else   this.richEdit.setText(this.richEdit.getText()+"          左岸剩"+state.priestLeft+"个传教士和"+state.wildManLeft+"个野人。"+"\r\n");
	      
		  if(state.priestRight!=0&&state.wildManRight==0)
		    this.richEdit.setText(this.richEdit.getText()+"          右岸只剩"+state.priestRight+"个传教士。"+"\r\n");
	 else if(state.priestRight==0&&state.wildManRight!=0)
		    this.richEdit.setText(this.richEdit.getText()+"          右岸只剩"+state.wildManRight+"个野人。"+"\r\n");
     else   this.richEdit.setText(this.richEdit.getText()+"          右岸剩"+state.priestRight+"个传教士和"+state.wildManRight+"个野人。"+"\r\n");
	      
	 
	 }
	}
	
	public void backPatch(int i)
	{if(i>0) 
	 {backPatch(father(i));
	  this.richEdit.setText(this.richEdit.getText()+"\r\n        -----------第"+(++counter)+"步-----------\r\n");
	  printOperater(i,getMovmentOfState(i));
	  printState(i);}
	}

	public void printOutSolution(int i)
	{printState(0);
	 backPatch(i);
	
	}
}