searchprocess.java~136~

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

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

/**
 * <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 father=new Vector();

 // Node source=new Node(1,0,Source,0,0);
// Node dest=new Node(0,0,Dest,0,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){
      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;

  }

  //////////////////////////////////////
  public   void push(Node node,Vector ope){
    ope.add(node);
  }

  public   Node pop(Vector ope){

     Node firstnode=(Node)ope.get(0);
    ope.removeElementAt(0);
    return firstnode;
    }

  public   Node found(int k,Vector vec,Node Source){

 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){
     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){

   //int f=0;
   // int g=0;
    //int h=0;

   // int parentid=0;
    int m=0;
  int n=0;
  // int i=0;
   //int j=0;
  // int k=0;

   for(int i=0;i<=2;i++)
    { for(int j=0;j<=2;j++)
     if(pnode.arr[i][j]==0)
     {
      m=i;
      n=j;
    }
 }

 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];


//if(pnewnode.arr[m-1][n]!=des.arr[m-1][n])
    pnewnode.arr[m][n]=pnewnode.arr[m-1][n];
     pnewnode.arr[m-1][n]=0;






    // 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)
           { int l=0;
             while(l<close.size())
             {flag=true;
             for( i=0;i<=2;i++)
             {
               for( j=0;j<=2;j++)
                 if(pnewnode.arr[i][j]!=((Node)close.get(l)).arr[i][j])
                 {flag=false;
                  }
             }
             if(flag=true) break;
             l++;
             }
           }
           for(i=0;i<=2;i++)
        {for (j=0;j<=2;j++)
              System.out.print(pnewnode.arr[i][j]);
 }*/



            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;
               // System.out.print("pnewnode.f  "+pnewnode.f+" \n");
               //  System.out.print("pnewnode.g  "+pnewnode.g+" \n");
                 // System.out.print("pnewnode.h  "+pnewnode.h+" \n");
                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];

//if(pnewnode.arr[m+1][n]!=des.arr[m+1][n]);
     pnewnode.arr[m][n]=pnewnode.arr[m+1][n];
       pnewnode.arr[m+1][n]=0;



    /* k=0;
             while(k<open.size())
             {flag=true;
             for( i=0;i<=2;i++)
             {
               for( j=0;j<=2;j++)
                    if(pnewnode.arr[i][j]!=((Node)open.get(k)).arr[i][j])
                      {flag=false;
                       }
             }
             if(flag=true) break;
             k++;
             }
           if(flag=false)
           { int l=0;
             while(l<close.size())
             {flag=true;
             for( i=0;i<=2;i++)
             {
               for( j=0;j<=2;j++)
                 if(pnewnode.arr[i][j]!=((Node)close.get(l)).arr[i][j])
                 {flag=false;
                  }
             }
             if(flag=true) break;
             l++;
             }
           }*/
       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];


//if(pnewnode.arr[m][n-1]!=des.arr[m][n-1]);
    pnewnode.arr[m][n]=pnewnode.arr[m][n-1];
      pnewnode.arr[m][n-1]=0;

   /* k=0;
            while(k<open.size())
            {flag=true;
            for( i=0;i<=2;i++)
            {
              for(j=0;j<=2;j++)
                   if(pnewnode.arr[i][j]!=((Node)open.get(k)).arr[i][j])
                     {flag=false;
                      }
            }
            if(flag=true) break;
            k++;
            }
          if(flag=false)
          { int l=0;
            while(l<close.size())
            {flag=true;
            for( i=0;i<=2;i++)
            {
              for( j=0;j<=2;j++)
                if(pnewnode.arr[i][j]!=((Node)close.get(l)).arr[i][j])
                {flag=false;
                 }
            }
            if(flag=true) break;
            l++;
            }
          }*/
      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];

//if(pnewnode.arr[m][n+1]!=des.arr[m][n+1])
    pnewnode.arr[m][n]=pnewnode.arr[m][n+1];
       pnewnode.arr[m][n+1]=0;


    /* k=0;
             while(k<open.size())
             {flag=true;
             for( i=0;i<=2;i++)
             {
               for( j=0;j<=2;j++)
                    if(pnewnode.arr[i][j]!=((Node)open.get(k)).arr[i][j])
                      {flag=false;
                       }
             }
             if(flag=true) break;
             k++;
             }
          /* if(flag=false)
           { int l=0;
             while(l<close.size())
             {flag=true;
             for( i=0;i<=2;i++)
             {
               for( j=0;j<=2;j++)
                 if(pnewnode.arr[i][j]!=((Node)close.get(l)).arr[i][j])
                 {flag=false;
                  }
             }
             if(flag=true) break;
             l++;
             }
           }*/
       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(){
     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;
     // Node min;
       for(int i=0;i<open.size();i++){
      // Node min;
     //  Node temp;
      // Node opei;
        Node opei=(Node)open.get(i);
       // int minvalue=(Node)open.get(i
       if(opei.f<minvalue)
       {
         minvalue=opei.f;
         indexmin=i;
         }
       }
      // return (Node)ope.elementAt(indexmin);
     //  ope.removeElementAt(indexmin);

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

       }


    public  int abs(int num)
{
  int nume;
  if(num>0)
    nume=num;
  else
    nume=-num;
  return nume;
}



     public   int caculatemove(Node nod,Node destin){
      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);
          /*
          System.out.print(i);
          System.out.print(j);
          System.out.print(row);
          System.out.print(col);
          System.out.print("\n");
          */
          if (value!=0)
            totalstep+=step;
        }
       }
      return totalstep;
     }

}


class 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;
}
}