asearch.java

这个程序是实现人工智能中的A*算法

public class ASearch{
 static int dest[][] = {{1,2,3},{8,0,4},{7,6,5}};

    static void Swap(Eight ee,int i,int j,int m,int n){//交换
     int temp;
        temp = ee.e[i][j];
        ee.e[i][j] = ee.e[m][n];
        ee.e[m][n] = temp;
 }


 static int compare(Eight a){//为当前节点“不在位”的将牌数
  int h =0,i,j;
  for(i=0;i<3;i++)
   for(j=0;j<3;j++){
    if(a.e[i][j]!=dest[i][j])
     h++;
   }
  return h;
 }
 
 //生成子状态
 static Queue born(Eight e){
  int m=1,n=1,i=0,j=0;
  boolean flag = true;
  Queue sons = new Queue();//队列对象
  for(i=0;i<3&&flag;i++)
   for(j=0;j<3&&flag;j++){
    if(e.e[i][j]==0){
     flag=false;
     break;
    }
   }
  i--;//i=2
  if(i-1>=0){
         m=i-1;//m=0
            if(m!=e.faX){
             Swap(e,m,j,i,j);
                //e.print();

                Eight son1 = new Eight(e);
    son1.faX = i;
    son1.faY = j;
    son1.former = e;
                sons.addElement(son1);
             Swap(e,i,j,m,j);

        }
  }
  if(i+1<3){
         m=i+1;
            if(m!=e.faX){
             Swap(e,m,j,i,j);
                //e.print();
             Eight son2 = new Eight(e);
             son2.faX = i;
    son2.faY = j;
    son2.former = e;
                sons.addElement(son2);
                Swap(e,i,j,m,j);
        }

  }
  if(j-1>=0){
   n=j-1;
   if(n!=e.faY){
    Swap(e,i,n,i,j);
    //e.print();
    Eight son3 = new Eight(e);
    son3.faX = i;
    son3.faY = j;
    son3.former = e;
    sons.addElement(son3);
         Swap(e,i,j,i,n);
        }

  }
  if(j+1<3){
   n=j+1;
   if(n!=e.faY){
    Swap(e,i,n,i,j);
    //e.print();
             Eight son4 = new Eight(e);
             son4.faX = i;
    son4.faY = j;
    son4.former = e;
    sons.addElement(son4);
         Swap(e,i,j,i,n);
        }

  }
  return sons;
 }
 public static void main(String[] args){
	 System.out.println();
  int depth=0;                          //深度
  Eight n = new Eight() ;
  Eight temp1 = new Eight() , temp2 = new Eight() ;
  //open表
  Queue open = new Queue();
  //closed表
  Queue closed = new Queue();
  //保存子状态的表
  Queue son = new Queue();
  open.addElement(n);

  while(!open.isEmpty()){
   n= open.elementAt(0); //
   open.removeFirst( );
   if(compare(n)==0){
    n.listAll(n);
    System.out.println("Success!");
    return;
   }
   son = born(n);
   depth++;
   int count = son.size();
   if(count==0)
             continue;
   else for(int t=0;t<count;t++){
    temp1 = son.elementAt(t);
    if(!open.contains(temp1)&&!closed.contains(temp1)){
     temp1.f = depth + compare(temp1);
     open.addElement(temp1);
    }
    else if(open.contains(temp1)){
     temp1.f = depth + compare(temp1);
     int pos = open.indexOf(son.elementAt(t));
     temp2 = open.elementAt(pos);
     if(temp1.f<temp2.f){
      open.setElementAt(temp1,pos);
     }
    }
    else if(closed.contains(temp1)){
                 temp1.f = depth + compare(temp1);
                 int pos = closed.indexOf(temp1);
                 temp2 = closed.elementAt(pos);
                    if( temp1.f<temp2.f ){
                     closed.remove(son.elementAt(t));
                        open.addElement(temp1);
                    }
    }
   }//end for
            closed.addElement(n);
            for(int i=open.size()-1;i>0;i--)
                for(int j=0;j<i;j++){
                    temp1 = (Eight)open.elementAt(j);
                    temp2 = (Eight)open.elementAt(j+1);
                    if(temp1.f>temp2.f){
                     Eight tq=new Eight();
                        tq = open.elementAt(j);
                        open.setElementAt(open.elementAt(j+1),j);
                        open.setElementAt(tq,j+1);
                     }
             }
            //System.out.println(n.former);
  }//end while
  
  System.out.println("Fail!");
        return;
 }//end main
}