searchprocess.java~3~

自己用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.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 static Vector open=new Vector();
public static Vector close=new Vector();
public  static Vector father=new Vector();
public static boolean flag=true;
 // Node source={0,0,Source,0,0};
  //Node dest={0,0,Dest,0,0};
  public static Vector execute(int[][] Source,int[][] Dest){
    // Vector open=new Vector();
 // Vector close=new Vector();
  // boolean flag=true;
    Node source=new Node(1,0,Source,0,0);
    Node dest=new Node(0,0,Dest,0,0);
    push(source,open);
      Node pnode=source;
    while(flag=true){
      if(open.isEmpty())
      {
        flag=false;
        break;
      }
     pnode=pop(open);
   push(pnode,close);
    //if(equal(pnode,dest)) break;
    if (judgesame(pnode, dest))
   break;
    extendnode(pnode);
    queopen();
    pnode=pop(open);
    }
      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);
          Result.add(Father);
          m=Father.parentid;
          k++;
        }
      }
      else{
        System.out.print("no found");
      }
      return Result;

  }

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

  public static Node pop(Vector ope){
    Node firstnode;
    firstnode=ope.firstElement();
    ope.removeElementAt(0);
    return firstnode;
    }

  public static Node found(int k,Vector vec){
 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 static boolean judgesame(Node s1,Node s2){
    for(int i=0;i<=s1.arr.length;i++){
      for(int j=0;j<=s2.arr.length;j++){
        if(!(s1.arr[i][j]==s2.arr[i][j]))
          return false;

      }
       return true;
  }
  }


  public static void extendnode(Node pnode){
    int f=0;
    int g=0;
    int h=0;
    int Id=0;
    int parentid=0;
    int m=0;
   int n=0;
   int i=0;
   int j=0;
   int k=0;

   for( i=0;i<=2;i++)
    { for( j=0;j<=2;j++)
     if(pnode.arr[i][j].equals("0"))
     {
      m=i;
      n=j;
    }
 }
 if(m-1>-1)
 {
  boolean flag=false;
   Node pnewnode;
   for( i=0;i<=2;i++)
   { for( j=0;j<=2;j++)
       pnewnode.arr[i][j]=pnode.arr[i][j];
   if(!pnewnode.arr[i][j]=dest.arr[i][j])
     {
     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++;
             }
           }

                Id++;
                pnewnode.parentid()=pnode.Id;
                 g++;
                h=caculatemove(pnewnode);
                 f=g+h;
                 open.add(new Node(Id,parentid,pnewnode.arr,f,g));
 }

 if(m+1<3)
 {
  boolean flag=false;
   Node pnewnode=new Node();
   for( i=0;i<=2;i++)
   { for( j=0;j<=2;j++)
       pnewnode.arr[i][j]=pnode.arr[i][j];
   if(!pnewnode.arr[i][j]=dest.arr[i][j])
     {
     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++;
             }
           }

                Id++;
                pnewnode.parentid()=pnode.Id;
                 g++;
                h=caculatemove(pnewnode);
                 f=g+h;
                 open.add(new Node(Id,pnewnode,parentid,f,g));
 }


 if(n-1>-1)
{
 boolean flag=false;
  Node pnewnode=new Node();
  for( i=0;i<=2;i++)
   for( j=0;j<=2;j++)
      pnewnode.arr[i][j]=pnode.arr[i][j];
  if(!pnewnode.arr[i][j]=dest.arr[i][j])
    {
    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++;
            }
          }

               Id++;
               pnewnode.parentid()=pnode.Id;
                g++;
               h=caculatemove(pnewnode);
                f=g+h;
                open.add(new Node(Id,pnewnode,parentid,f,g));
}


 if(n+1<3)
 {
  boolean flag=false;
   Node pnewnode=new Node();
   for( i=0;i<=2;i++)
   { for( j=0;j<=2;j++)
       pnewnode.arr[i][j]=pnode.arr[i][j];
   if(!pnewnode.arr[i][j]=dest.arr[i][j])
     {
     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++;
             }
           }

                Id++;
                pnewnode.parentid()=pnode.Id;
                 g++;
                h=caculatemove(pnewnode);
                 f=g+h;
                 open.add(new Node(Id,pnewnode,parentid,f,g));
 }
  }


   public static void queopen(){
       for(int i=0;i<open.size();i++){
       Node min;
       Node nod;
       int position;
       min=open.firstElement();
       if(comparefvalue(open.get(i),min))
       {
         position=i;
         }
         nod=open.get(position);
        open.get(position)=min;
        min=nod;
     }


     }

     public static int caculatemove(Node nod){
      int totalstep=0;
      for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++)
        {
          int value=nod[i][j];
          int row,col,step;
          for(int k=0;k<=2;k++)
          {for(int l=0;l<=2;l++)
          if(!(dest.Dest[k][l]==value))
            {
             row=k;
             col=l;
             break;
            }

            step=abs(row-i)+abs(col-j);
            totalstep+=step;
          }
        }
      }
     }

}