searchprocess.java~139~

自己用JAVA编的人工智能的A*算法的八数码程序

package eightfigure;
import java.io.*;
import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import javax.swing.event.*;
import java.lang.Math;

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2004</p>
 * <p>Company: </p>
 * @author unascribed
 * @version 1.0
 */

public class searchProcess {
public Vector open=new Vector();
public  Vector close=new Vector();
public  int pnodeId=0;

public  Vector execute(int[][] Source,int[][] Dest){
       boolean flag;

      Node source=new Node(0,0,Source,0,0,0);
      Node dest=new Node(0,0,Dest,0,0,0);
      source.h=caculatemove(source,dest);
      source.f=source.g+source.h;

      push(source,open);
      Node pnode=source;

   while(flag=true){                  //OPEN表为空退出
      if(open.isEmpty()){
                   flag=false;
                   break;
                     }
      pnode=pop(open);
      push(pnode,close);
      if (judgesame(pnode, dest))    //找到目标退出
       break;
      extendnode(pnode,dest);
      queopen();
   }


      Node Father;                //根据父节点找最佳路径
      Vector Result=new Vector();
      int k=0;
      if(flag=true){
        Result.add(pnode);
        int m=pnode.parentid;
        while(m>=0){
          Father=found(m,close,source);
          Result.add(Father);
          m=Father.parentid;
          k++;
        }
      }
      else{                          //没找到标志
        System.out.print("no found");
          }
      return Result;              //即为结果

  }

  //////////////////////////////////////
  //以下是EXECUTE实现的所有方法：
  public  void push(Node node,Vector ope){     //将NODE加进OPEN表
    ope.add(node);
  }

  public   Node pop(Vector ope){             //将OPEN表的第一个NODE弹出
    Node firstnode=(Node)ope.get(0);
    ope.removeElementAt(0);
    return firstnode;
  }

  public   Node found(int k,Vector vec,Node Source){ //在CLOSE表中ID号相同的NODE
   Node result=Source;
   int i;
   for(i=0;i<vec.size();i++){
     if(k==((Node)vec.get(i)).Id)
     {
     result=(Node)vec.get(i);
     }
  }
  return result;
}

  public  boolean judgesame(Node s1,Node s2){       //判断找到的NODE是否是目标NODE
     int[][] arr=new int[3][3];
    for(int i=0;i<=2;i++){
      for(int j=0;j<=2;j++){
        if(!(s1.arr[i][j]==s2.arr[i][j]))
          return false;
      }
    }
    return true;
 }


  public  void extendnode(Node pnode,Node des){  //将OPEN表中第一个NODE 扩展

  int m=0;
  int n=0;
  //将NODE的“0”定位M，N
 for(int i=0;i<=2;i++)
    { for(int j=0;j<=2;j++)
     if(pnode.arr[i][j]==0)
     {
      m=i;
      n=j;
    }
 }

 //以下分四个方向扩展：上、下、左、右，并加如OPEN表中

 if(m-1>-1)
 { int[][] arr=new int[3][3];
  boolean flag=true;

   Node pnewnode=new Node(0,0,arr,0,0,0);
   for(int i=0;i<=2;i++)
   for( int j=0;j<=2;j++)
  pnewnode.arr[i][j]=pnode.arr[i][j];
 pnewnode.arr[m][n]=pnewnode.arr[m-1][n];
 pnewnode.arr[m-1][n]=0;


 int  k=0;
             while(k<close.size())
             {
               flag=true;
              for(int ii=0;ii<=2;ii++)
              {
               for( int jj=0;jj<=2;jj++)
                    if(pnewnode.arr[ii][jj]!=((Node)close.get(k)).arr[ii][jj])
                      {flag=false;
                       break;
                       }
                       if(flag==false) break;
             }
             if(flag==true) break;
             k++;
             }

          if(flag==false)
           {
               pnewnode.parentid=pnode.Id;
               pnodeId=pnodeId+1;
               pnewnode.Id=pnodeId;
               pnewnode.g=pnode.g+1;
                pnewnode.h=caculatemove(pnewnode,des);
                pnewnode.f=pnewnode.g+pnewnode.h;
                open.add(pnewnode);
           }
 }


 if(m+1<3)
 { int[][] arr=new int[3][3];
  boolean flag=false;
   Node pnewnode=new Node(0,0,arr,0,0,0);
   for(int i=0;i<=2;i++)
    for(int j=0;j<=2;j++)
       pnewnode.arr[i][j]=pnode.arr[i][j];
       pnewnode.arr[m][n]=pnewnode.arr[m+1][n];
       pnewnode.arr[m+1][n]=0;

int  k=0;
             while(k<close.size())
             {
               flag=true;
              for(int ii=0;ii<=2;ii++)
              {
               for( int jj=0;jj<=2;jj++)
                    if(pnewnode.arr[ii][jj]!=((Node)close.get(k)).arr[ii][jj])
                      {flag=false;
                       break;
                       }
                       if(flag==false) break;
             }
             if(flag==true) break;
             k++;
             }

     if(flag==false)

          {
           pnewnode.parentid=pnode.Id;
           pnodeId=pnodeId+1;
           pnewnode.Id=pnodeId;
           pnewnode.g=pnode.g+1;
           pnewnode.h=caculatemove(pnewnode,des);
           pnewnode.f=pnewnode.g+pnewnode.h;
          open.add(pnewnode);
         }
 }


 if(n-1>-1)
{ int[][] arr=new int[3][3];
 boolean flag=false;
  Node pnewnode=new Node(0,0,arr,0,0,0);
  for( int i=0;i<=2;i++)
   for(int j=0;j<=2;j++)
      pnewnode.arr[i][j]=pnode.arr[i][j];
      pnewnode.arr[m][n]=pnewnode.arr[m][n-1];
      pnewnode.arr[m][n-1]=0;

   int  k=0;
             while(k<close.size())
             {
               flag=true;
              for(int ii=0;ii<=2;ii++)
              {
               for( int jj=0;jj<=2;jj++)
                    if(pnewnode.arr[ii][jj]!=((Node)close.get(k)).arr[ii][jj])
                      {flag=false;
                       break;
                       }
                       if(flag==false) break;
             }
             if(flag==true) break;
             k++;
             }
       if(flag==false){
                        pnewnode.parentid=pnode.Id;
                        pnodeId=pnodeId+1;
                        pnewnode.Id=pnodeId;
                        pnewnode.g=pnode.g+1;
                        pnewnode.h=caculatemove(pnewnode,des);
                         pnewnode.f=pnewnode.g+pnewnode.h;
                        open.add(pnewnode);
                       }
}


 if(n+1<3)
 { int[][] arr=new int[3][3];
  boolean flag=false;
   Node pnewnode=new Node(0,0,arr,0,0,0);
   for( int i=0;i<=2;i++)
    for( int j=0;j<=2;j++)
       pnewnode.arr[i][j]=pnode.arr[i][j];
       pnewnode.arr[m][n]=pnewnode.arr[m][n+1];
       pnewnode.arr[m][n+1]=0;

 int  k=0;
             while(k<close.size())
             {
               flag=true;
              for(int ii=0;ii<=2;ii++)
              {
               for( int jj=0;jj<=2;jj++)
                    if(pnewnode.arr[ii][jj]!=((Node)close.get(k)).arr[ii][jj])
                      {flag=false;
                       break;
                       }
                       if(flag==false) break;
             }
             if(flag==true) break;
             k++;
             }


    if(flag==false)
    {
      pnewnode.parentid=pnode.Id;
      pnodeId=pnodeId+1;
     pnewnode.Id=pnodeId;
      pnewnode.g=pnode.g+1;
      pnewnode.h=caculatemove(pnewnode,des);
       pnewnode.f=pnewnode.g+pnewnode.h;
      open.add(pnewnode);

      }
   }
}



   public  void queopen(){                         //OPEN表排序，只用找F值最小的设为第一个NODE
     int indexmin=0;
     int[][] arr=new int[3][3];
     Node temp=new Node(0,0,arr,0,0,0);
    Node node0=(Node)open.get(0);
    int minvalue=node0.f;
    for(int i=0;i<open.size();i++){
       Node opei=(Node)open.get(i);
       // int minvalue=(Node)open.get(i
       if(opei.f<minvalue)
       {
         minvalue=opei.f;
         indexmin=i;
        }
  }


      temp=(Node)open.get(0);
      open.setElementAt((Node)open.elementAt(indexmin),0);
      open.setElementAt(temp,indexmin);
  }


public  int caculatemove(Node nod,Node destin){       //计算NODE到目标NODE 需要走的步数，即为H值
      int totalstep=0;
      int i,j,k,l,value;
      int row=0;
      int col=0;
      int step=0;
      for( i=0;i<=2;i++){
        for( j=0;j<=2;j++)
        {
          value=nod.arr[i][j];
          int t=1;
          for( k=0;k<=2;k++)
          {
            for( l=0;l<=2;l++) {
              if(value==destin.arr[k][l]) {
                t=0;
                row=k;
                col=l;
                break;
              }
            }
            if(t==0)
            {
              break;
            }
          }
          step=abs(i-row)+abs(j-col);

          if (value!=0)
            totalstep+=step;
        }
       }
      return totalstep;
     }

 public  int abs(int num)  //取一个数的绝对值
      {
    int nume;
    if(num>0)
     nume=num;
     else
     nume=-num;
    return nume;
     }

}


class Node {              //定义NODE 结构
 int Id;
int[][] arr=new int[3][3];
int parentid;
int g;
int f;
int h;
public Node()
{}

public  Node(int Id,int parentid,int[][] arr,int f,int g,int h) {
 this.Id=Id;
 this.parentid=parentid;
 for(int i=0;i<=2;i++)
 {for(int j=0;j<=2;j++)
this.arr[i][j]=arr[i][j];
 }
 this.f=f;
 this.g=g;
 this.h=h;
}
}