eightnum.java

我传的第一个是八数码的盲目搜索,而这个是A*,请指教

package text2;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.StringTokenizer;
public class EightNum{
   
    结点 初始结点;
    结点 目标结点;
    结点 中间结点;
    结点 局部结点;
    结点 局部结点1;
    结点 路径[]=new 结点[10000];
    int judge=1;
   int count=0;
    结点 扩展结点[] = new 结点[10000]; //保存父结点的四个子结点,顺序存储为上，下，左，右，为扩展的临时数组
    int f=0;//扩展结点的下标
 
    结点 open[] = new 结点[10000];  //扩展结点类
   
    结点 最短路径[] = new 结点[10000];//相当与closed表
   
    int opennum=0;//open表中结点的个数
   
    int closednum =0;//closed表中结点的个数s
   
    EightNum(int a1[],int a2[])
    {

        初始结点 = new 结点(a1);
     
        目标结点 = new 结点(a2);
       
        //初始结点.不相同结点个数 = 初始结点.不相同结点个数(目标结点);
       // 目标结点.不相同结点个数 = 目标结点.不相同结点个数(目标结点);
       
       // System.out.println("初始结点 的 不同点的个数:"+初始结点.不相同结点个数);
    }
    public class 结点
    { 
        int 深度,不相同结点个数;
       
        int 数码[][] = new int[3][3];
       
        结点 parent;
        boolean 用过吗;
      
        public 结点()
        {
            用过吗 = false;
        }
        public 结点(结点 n)
        {
            深度 = n.深度;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                        数码[i][j]=n.数码[i][j];
            不相同结点个数 = n.不相同结点个数;
            用过吗 = n.用过吗;
        }
        public 结点(int a[])
        {
            int m=0;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    {
                        数码[i][j]=a[m];
                        m=m+1;
                    }
           
            用过吗 = false;
            深度=0;
            //System.out.println("测试4");//测试
        }

        public int[][] 取数值()
        {
            return 数码;
        }

        public boolean 等于(结点 st)//只是数码不相等
        {
            int[][] s = st.取数值();
            int i,j;
            for (i = 0; i < 3; i++)
                for(j = 0 ; j<3 ;j++)
                if (s[i][j] != 数码[i][j])
                    return false;
            return true;
        }
       
        public int[] 零点位置()
        {
            int 位置[] = new int[2];
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    if(this.数码[i][j]==0)
                        {位置[0]=i;位置[1]=j;}
            return 位置;               
        }
       
        public int 不相同结点个数(结点 a)
        {
            int m = 0;
            for(int i=0 ; i<3 ; i++)
                for(int j=0; j<3 ;j++)
                    { if( a.数码[i][j] == 数码[i][j] && a.数码[i][j]!=0 ) m=m+1;}
            return 8-m;
        }
    }
   
    public static void 打印结点(结点 h)
    {
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
                {
                 System.out.print("  "+h.数码[i][j]+"  ");
                }
            System.out.println();
        }
    }
    public void 扩展_并查找结点(结点 n)
    {
      
        
        结点 t = new 结点();   
       
        int temp = 0;                 //交换数码的中间变量
        boolean 没找到 = true;
      
                if( n == 初始结点)
                {
                    open[opennum]=n;        // （状态位置,结点对象)
                    opennum=opennum+1;
                    最短路径[closednum]=n;
                    closednum=closednum+1;
                 }
                 int[] p= n.零点位置();//知道0的位置                                
                 System.out.println("=================================待扩展的结点;================================");
                 打印结点(n);
                // if(!n.等于(初始结点))
                // {
               //     if(存在否(n)){System.out.println("该结点已经在open表中已经存在不用扩展");break;}
                // }
                 System.out.println("0点位置:"+p[0]+" "+p[1]);
                 if(p[0]==0 && p[1]==0)//如果0点在左上角
                 {                                    
                    //展开(待扩展的结点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时结点数组);
                    //向下扩展
                     if(judge!=0)
                    展开(n,1,p,1,0,扩展结点);        
                    //向右扩展 
                      if(judge!=0)
                   展开(n,3,p,0,1,扩展结点);           

                 }
                 else if(p[0] == 0 && p[1] == 1)//如果0点在上中间的话
                 {
                     System.out.println("0点在上中间");
                     //向下扩展
                      if(judge!=0)
                     展开(n,1,p,1,1,扩展结点) ;         
                     //向左扩展
                      if(judge!=0)
                     展开(n,2,p,0,0,扩展结点)          ;
                     //向右扩展
                      if(judge!=0)
                  展开(n,3,p,0,2,扩展结点)           ;
                 }                
                 else if(p[0] == 0 && p[1] == 2)//如果0点在右上角
                 {
                     System.out.println("0点在右上角");
                     //向下扩展
                     if(judge!=0)
                   展开(n,1,p,1,2,扩展结点)           ;
                     //向左扩展
                      if(judge!=0)
                      展开(n,2,p,0,1,扩展结点)            ;                  
                 }
                 else if(p[0] == 1 && p[1] == 0)//如果 点在左边中间
                 {
                     System.out.println("0点在左边中间");
                     //向上扩展
                     if(judge!=0)
                      展开(n,0,p,0,0,扩展结点)           ;
                     //向下扩展
                      if(judge!=0)
                      展开(n,1,p,2,0,扩展结点)            ;
                     //向右扩展
                   if(judge!=0)
                      展开(n,3,p,1,1,扩展结点)           ;                   
                 }
                 else if(p[0] == 1 && p[1] == 1)//如果 点在正中间
                 {
                     System.out.println("0点在正中间");
                     //向上扩展
                     if(judge!=0)
                      展开(n,0,p,0,1,扩展结点)           ;
                     //向下扩展
                      if(judge!=0)
                      展开(n,1,p,2,1,扩展结点)            ;
                     //向左扩展
                    if(judge!=0)
                     展开(n,2,p,1,0,扩展结点)            ;
                     //向右扩展
                     if(judge!=0)
                     展开(n,3,p,1,2,扩展结点)            ;
                 }
                 else if(p[0] == 1 && p[1] == 2)//如果 点在右边中间
                 {
                     System.out.println("0点在右边中间");
                     //向上扩展
                    if(judge!=0)
                    展开(n,0,p,0,2,扩展结点)           ;
                     //向下扩展
                     if(judge!=0)
                      展开(n,1,p,2,2,扩展结点)            ;
                     //向左扩展
                      if(judge!=0)
                      展开(n,2,p,1,1,扩展结点)         ;
                 }
                 else if(p[0] == 2 && p[1] == 0)//如果 点在左下角
                 {
                     System.out.println("0点在左下角");
                     //向上扩展
                     if(judge!=0)
                      展开(n,0,p,1,0,扩展结点)            ;
                     //向右扩展
                     if(judge!=0)
                      展开(n,3,p,2,1,扩展结点)         ;
                 }
                 else if(p[0] == 2 && p[1] == 1)//如果 点在下边中间
                 {
                     System.out.println("0点在下边中间");
                     //向上扩展
                     if(judge!=0)
                      展开(n,0,p,1,1,扩展结点)           ;
                     //向左扩展
                      if(judge!=0)
                     展开(n,2,p,2,0,扩展结点)             ;
                     //向右扩展
                      if(judge!=0)
                      展开(n,3,p,2,2,扩展结点)             ;
                 }
                 else if(p[0] == 2 && p[1] == 2)//如果 点在右下角
                 {
                     System.out.println("0点在右下角");
                     //向上扩展
                   if(judge!=0)
                      展开(n,0,p,1,2,扩展结点)          ;
                     //向左扩展
                     if(judge!=0)
                      展开(n,3,p,2,1,扩展结点)           ;
                 }
                
                    /* n = 取最优结点();
                     open[opennum]=n;
                     opennum++;
                     System.out.println("最优结点:");
                     打印结点(n);//测试
                     扩展_并查找结点(n);
                */
               
      
    }
   
    public boolean 存在否(结点 n)
    {
        for(int i=0;i<opennum;i++)
        {
            if(open[i].等于(n)) return true;
        }
        return false;
    }
       
    public boolean 展开(结点 n,int k,int[] z,int q,int p,结点[] 扩展结点)
    {
        
        
       count++;
        //展开(待扩展的结点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时结点数组)
        结点 t = new 结点(n);  // 用父结点扩展
        t.parent=n;
        int flag = 0;
        int temp;
        temp = t.数码[z[0]][z[1]];
        t.数码[z[0]][z[1]] = t.数码[q][p];
        t.数码[q][p] = temp;
       
        String msg="";
        if(k==0){ msg = new String("向上扩展结果");}
        else if(k==1){ msg = new String("向下扩展结果");}
        else if(k==2){ msg = new String("向左扩展结果");}
        else if(k==3){ msg = new String("向右扩展结果");}
        System.out.println(msg);
        打印结点(t);//测试
        if(!存在否(t))//如果不在open表中（测试此映射表中是否存在与指定值关联的键）
        {
            t.深度 = n.深度+1;
            t.不相同结点个数 = t.不相同结点个数(目标结点);
           
            if(t.等于(目标结点))
            {
                
                f=0;
                judge=0;
                目标结点.parent=t;
                System.out.println("=======恭喜!终于找到目标结点了^-^!!!==============");
                
                System.out.println("一共扩展了"+count+"个结点");
                打印结点(t);//测试
                最短路径[closednum]=t;
                closednum = closednum+1;
                return true;
            }
            else { 
                //System.out.println("what's wrong");
                扩展结点[f] = t;//如果在open表中不存在则装入扩展结点数组中
                f=f+1;
            }
            System.out.println("该结点的深度:"+t.深度+"\n该结点的不同与目标结点的个数:"+t.不相同结点个数);
            int r = t.深度+t.不相同结点个数;
            System.out.println("择优权值:"+r);
            System.out.println();
        }
        else
        {
            System.out.println("该结点已经分析过了");
            return false;
        }
        return false;
    }
   
    public 结点 取最优结点()
    {
        结点 最优;
        System.out.println("扩展数组的长度:"+有值的个数(扩展结点));
        
       
            for(int i=0;i<=f;i++){
            if(扩展结点[i]!=null){
                
                
            局部结点= 扩展结点[i];
            break;
            }
            }
          最优=局部结点;
            
        for(int i=0;i<f;i++)
        {
              if(扩展结点[i]!=null){
              
            if((扩展结点[i].深度+扩展结点[i].不相同结点个数)<(最优.深度+最优.不相同结点个数))
            {
                最优 = 扩展结点[i];
            }
              }
        }
        for(int i =0;i<f;i++)
        {
            if(扩展结点[i]==最优) 
            {
                扩展结点[i]=null;
                continue;
            }
             
             
        }
        //从open表中取出最优结点,放入closed表中
     
        最短路径[closednum]=最优;
        closednum = closednum+1;

        //f=0;//重置扩展数组下标
        return 最优;
     }
    public static int 有值的个数(结点 m[])
    {
        int n =0;
        for(int i=0;i<m.length;i++)
        {
            if(m[i] != null) n=n+1;
            if(m[i] == null) break;
        }         
        return n;
    }
 
}