用java实现人工智能中的A*算法求8数码问题

//8数码类
class Eight{
 int e[][] = {{2,8,3},{1,6,4},{7,0,5}};   //默认的起始状态
 int faX ,faY;                                       //保存父状态中0的位置
 int f;                                                  //估价函数值
 Eight former ;           

 public Eight(){
        faX = -1;
        faY=-1;
    f=-1;
    former = null;
    }

 public Eight(Eight other){
     for(int i = 0; i<3; i++)
            for(int j=0 ;j<3; j++){
              e[i][j] = other.e[i][j];
            }
        faX = other.faX;
        faY = other.faY;
        f = other.f;
        former = other.former;
 }

 public void print()
 {
  for(int i1 = 0;i1<3;i1++)
   for(int j1=0;j1<3;j1++){
    System.out.print(e[i1][j1]);
    if(j1==2)
     System.out.println();
    }
  System.out.println();
 }

 public void listAll( Eight e ){
   while( e.former != null ){
             e.former.print();
                e = new Eight(e.former);
            }
  return ;
 }

}

class Queue extends Object{                   //队列类
 private int size = 0;
 Eight qe[] = new Eight[20];

 public void print(){
  for(int i=0;i<size;i++)
   qe[i].print();
 }

 public void addElement(Eight e){
  qe[size] = e;
  size++;
 }

 public boolean contains(Eight e){
  if( size == 0 )
   return false;
  else{
   for(int i=0;i<size;i++){
    if(qe[i].equals(e))
     return true;
   }
  }
  return false;
 }

 public boolean isEmpty(){
  if (size == 0) {
   return true;
  }
  else return false;
 }

 public Eight elementAt(int index){

  return qe[index];
 }

 public void setElementAt( Eight e,int index ){

  qe[index] = e;
 }

 public int size(){
  return size;
 }

 public int indexOf (Eight e) {
  for (int i = 0; i < size; i++){
   if (qe[i].equals( e ))
    return i;
  }
  return -1;
 }

 public void removeFirst( ){
  for(int i=0;i<size;i++){
   qe[i] = qe[i+1];
  }
        size--;
 }

 public void remove( Eight e ){
  for( int i = 0; i < size; i++ ){
   if( qe[i].equals( e ))
    qe[i] = null;
  }
        size--;
 }

 public void removeAllElements(){
  for (int i = 0; i < size; i++){
   qe[i] = null;
  }
        size = 0;
 }

}

//算法实现类
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--;
  if(i-1>=0){
         m=i-1;
            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){
  
  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);
                     }
             }
  }//end while
  
  System.out.println("Fail!");
        return;
 }//end main
}

这个程序是实现人工智能中的A*算法，照着书上的算法做的。Queue类是自己写的一个队列类，用来实现open表和closed表。原来用Vector做的，但后来发现Vector中保存的只是引用，生成子状态后表中的状态也跟着变了，只好自己实现一个队列类。现在知道还有个LinkedList类可以胜任这项工作，不过作业都交了，我也懒得改了！

本文地址：http://com.8s8s.com/it/it12379.htm