searchprocess.java~135~

自己用JAVA编的一个人工智能的野人过河的程序

package yerenchengxu;

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

class SearchProcess {

  public Vector Open=new Vector();
  public Vector Close=new Vector();


  int id=0;
 // int s[][]={{3,3,1},{3,2,1},{3,1,1},{2,2,1},{1,1,1},{0,3,1},{0,2,1},{0,1,1},{3,2,0},{3,1,0},{3,0,0},{2,2,0},{1,1,0},{0,2,0},{0,1,0},{0,0,0}};
   public Vector success(){
     Boat boat1=new Boat();
     Boat boat2=new Boat();
       Riverside riverside1=new Riverside();
       Riverside riverside2=new Riverside();
       Riverside riverside3=new Riverside();
       Riverside riverside4=new Riverside();

   boolean flag=true;
 // Node Source;

  Node Source=new Node(0,0,0,boat1,riverside1,riverside2,0,0,0);

  Source.riverside1.wildMan=3;
  Source.riverside1.churchMan=3;
  Source.riverside2.wildMan=0;
  Source.riverside2.churchMan=0;
  Source.boat.wildMan=0;
  Source.boat.churchMan=0;
  Source.side=1;
  Source.id=0;
  Source.parentid=0;
  Source.h=4;
  Source.f=4;
  Source.g=0;

  Node Dest=new Node(0,0,0,boat2,riverside3,riverside4,0,0,0);
  Dest.riverside1.wildMan=0;
  Dest.riverside1.churchMan=0;
  Dest.riverside2.wildMan=3;
  Dest.riverside2.churchMan=3;
  Dest.boat.wildMan=0;
  Dest.boat.churchMan=0;



  push(Source,Open);
  Node Current=Source;
  while(flag==true){
    if(Open.isEmpty()){
        flag=false;
        break;
       }
   Current=pop(Open);
   push(Current,Close);
   if(judgesame(Current,Dest))
     break;
   extend(Current,Dest,Open);

   queopen();
    }
    Node Father;
    Vector Result=new Vector();
  if(flag==true){
    Result.add(Current);
   int m=Current.parentid;
   int k=0;
    while(m>0){
      Father=found(m,Close,Dest);
      Result.add(Father);
      m=Father.parentid;
      k++;
    }
  }
  else{                          //没找到标志
        System.out.print("no found");
          }
       Result.add(Source);
  return Result;

 }


     public void push(Node sour,Vector open){
           open.add(sour);
     }

     public Node pop(Vector open){
          Node firstnode=(Node)open.get(0);
          open.removeElementAt(0);
          return firstnode;
     }

     public boolean judgesame(Node cur,Node des){

        if(cur.riverside1.wildMan==des.riverside1.wildMan&&cur.riverside1.churchMan==des.riverside1.churchMan&&cur.side==des.side)
        return true;
        else return false;
      }

       public void extend(Node current,Node des,Vector open){
         int nwildMan1=0;
         int  nchurchMan1=0;
         int nwildMan2=0;
       int  nchurchMan2=0;
       int i;

       Boat boatState[]=new Boat [5];
      for( i=0;i<5;i++)
        boatState[i]=new Boat();


        if(current.side==1)
          {
          boatState[0].wildMan=2;
          boatState[0].churchMan=0;
          boatState[1].wildMan=1;
          boatState[1].churchMan=1;
          boatState[2].wildMan=0;
          boatState[2].churchMan=2;
          boatState[3].wildMan=1;
          boatState[3].churchMan=0;
          boatState[4].wildMan=0;
          boatState[4].churchMan=1;

          }

          else
          {
          boatState[0].wildMan=0;
          boatState[0].churchMan=1;
          boatState[1].wildMan=1;
          boatState[1].churchMan=0;
          boatState[2].wildMan=0;
          boatState[2].churchMan=2;
          boatState[3].wildMan=1;
          boatState[3].churchMan=1;
          boatState[4].wildMan=2;
          boatState[4].churchMan=0;
          }

        boolean  flag=true;

      // if(current.boat.wildMan==0&&current.boat.churchMan==0)
      //  i=0;
     //  else
        // {
     //   for(i=0;i<5;i++)
         // if(current.boat.wildMan==boatState[i].wildMan&&current.boat.churchMan==boatState[i].churchMan)
         //  break;
        //   i++;
       //  }
        //if(i<5)
         // {
        int j;
         for( j=0;j<5;j++)
         {
           if(current.side==1)
           {
            nwildMan1=current.riverside1.wildMan-boatState[j].wildMan;
            nchurchMan1=current.riverside1.churchMan-boatState[j].churchMan;
           }
           else
           {
            nwildMan1=current.riverside1.wildMan+boatState[j].wildMan;
            nchurchMan1=current.riverside1.churchMan+boatState[j].churchMan;
           }

            nwildMan2=3-nwildMan1;
            nchurchMan2=3-nchurchMan1;

           if((nwildMan1<=nchurchMan1||nchurchMan1==0)&&(nwildMan2<=nchurchMan2||nchurchMan2==0)&&nwildMan1>=0&&nchurchMan1>=0&&nwildMan2>=0&&nchurchMan2>=0)

           {







            // }
             // int preid=current.id-1;
            //  Node Father=found(preid,Open,current);
             // if(Father.riverside1.wildMan!=nwildMan1||Father.riverside1.churchMan!=nchurchMan1)

        // }

                 if(j<5)

                  {
                current.boat.wildMan=boatState[j].wildMan;
                   current.boat.churchMan=boatState[j].churchMan;
                     Boat boat=new Boat();
                     Riverside riverside1=new Riverside();
                     Riverside riverside2=new Riverside();

                       Node next=new Node(0,0,0,boat,riverside1,riverside2,0,0,0);

                         next.riverside1.wildMan=nwildMan1;
                        next.riverside1.churchMan=nchurchMan1;
                        next.riverside2.wildMan=nwildMan2;
                           next.riverside2.churchMan=nchurchMan2;
                        next.boat.wildMan=0;
                              next.boat.churchMan=0;

                       next.id=++id;

                    next.parentid=current.id;

                       next.g=current.g+1;
                        if(next.g%2==0)
                      next.side=1;
                            else
                        next.side=0;

                       next.h=next.riverside1.wildMan+next.riverside1.churchMan-2*next.side;
                     next.f=next.h+next.g;

           // System.out.println("   "+next.id+"   "+next.h+"   ");
          // if(next.riverside2.wildMan==3&&next.riverside2.churchMan==3)
           //  break outer1;
                     // else
               if(next.id!=0)
                  {
                     int k=0;
                        while((k<Close.size()))
                         {

                          if((next.riverside1.wildMan!=((Node)(Close.get(k))).riverside1.wildMan)||(next.riverside1.churchMan!=((Node)(Close.get(k))).riverside1.churchMan)||(next.side!=((Node)(Close.get(k))).side))
                           flag=false;
                          else
                         flag=true;



                        if(flag==true) break;

                            k++;
                         }
                   }
                   if(flag==false)
                   {
                     int m=0;
                       while((m<Open.size()))
                        {

                         if((next.riverside1.wildMan!=((Node)(Open.get(m))).riverside1.wildMan)||(next.riverside1.churchMan!=((Node)(Open.get(m))).riverside1.churchMan)||(next.side!=((Node)(Open.get(m))).side))
                          flag=false;
                         else
                        flag=true;



                       if(flag==true) break;

                           m++;
                         }
                   }
                   if(flag==false)

                      push(next,Open);

           // System.out.println("   "+((Node)open.get(0)).f+"  ");
                }


            }


         }
      }


    public void queopen()
    {
      int indexmin=0;
     // Boat boat=new Boat();
     //  Riverside riverside1=new Riverside();
     //Riverside riverside2=new Riverside();
      Node temp;
      Node node0=(Node)Open.get(0);

      int minvalue=node0.f;
      for(int i=0;i<Open.size();i++){
      Node opei=(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 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;
}
}



class Node{
  int f,h,g,id,parentid;
  Boat boat;
  Riverside riverside1;
  Riverside riverside2;
  int side;
  public Node()
  {};
  public Node(int f,int h,int g,Boat boat,Riverside riverside1,Riverside riverside2,int side,int id,int parentid){
    this.f=f;
    this.h=h;
    this.g=g;
    this.boat=boat;
    this.riverside1=riverside1;
    this.riverside2=riverside2;
    this.side=side;
    this.id=id;
    this.parentid=parentid;

  }

}
class Boat{
  int wildMan;
  int churchMan;
  public Boat()
  {}
  public Boat(int wildMan,int churchMan)
  {
    this.wildMan=wildMan;
    this.churchMan=churchMan;
  }
}
class Riverside{
   int wildMan;
   int churchMan;
   public Riverside()
   {}
}