astar.java

八数码问题的A*算法实现

package test;

import java.io.*;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.StringTokenizer;

/**
 * @author zuec
 * 
 * 创建日期 2006-4-10
 * 
 * Email: [e-mail]
 * 
 * QQ:309011878
 * 
 * 八数码的A*算法，
 * 启发函数为f(x)=g(x)+h(x)，g(x)为结点x的深度，h(x)为结点x与目标结点相同元素的个数
 * 
 */
public class AStar {
    
    结点 初始结点; 
    结点 目标结点;
    
    结点 扩展结点[] = new 结点[4]; //保存父结点的四个子结点,顺序存储为上，下，左，右，为扩展的临时数组
    int f=0;//扩展结点的下标
 
    结点 open[] = new 结点[100];  //扩展结点类
    
    结点 最短路径[] = new 结点[100];//相当与closed表
    
    int opennum=0;//open表中结点的个数
    
    int closednum =0;//closed表中结点的个数s
    
    AStar(int a1[],int a2[])
    {

        初始结点 = new 结点(a1);
      
        目标结点 = new 结点(a2); 
        
        //初始结点.不相同结点个数 = 初始结点.不相同结点个数(目标结点);
       // 目标结点.不相同结点个数 = 目标结点.不相同结点个数(目标结点);
        
       // System.out.println("初始结点 的 不同点的个数:"+初始结点.不相同结点个数);
    }
    public class 结点
    {  
        int 深度,不相同结点个数;
        
        int 数码[][] = new int[3][3];
        
        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 static void 输出结果(Hashtable h)
    {
        Enumeration enum = h.elements();
        System.out.println("结果路径是:");
        while(enum.hasMoreElements())
        {
            System.out.println(enum.nextElement()+" ");
            System.out.println();
        }

    }

    public void 扩展_并查找结点(结点 n)
    {
        结点 t = new 结点();    
        
        int temp = 0;                 //交换数码的中间变量
        boolean 没找到 = true; 
        while(没找到)
        {    
                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( 展开(n,1,p,1,0,扩展结点) )         {没找到=false;  break;}
                    //向右扩展  
                    if( 展开(n,3,p,0,1,扩展结点) )            {没找到=false;  break;}

                 }
                 else if(p[0] == 0 && p[1] == 1)//如果0点在上中间的话
                 {
                     System.out.println("0点在上中间");
                     //向下扩展
                     if( 展开(n,1,p,1,1,扩展结点) )            {没找到=false;  break;}
                     //向左扩展
                     if( 展开(n,2,p,0,0,扩展结点) )            {没找到=false;  break;}
                     //向右扩展
                     if( 展开(n,3,p,0,2,扩展结点) )            {没找到=false;  break;}
                 }                 
                 else if(p[0] == 0 && p[1] == 2)//如果0点在右上角
                 {
                     System.out.println("0点在右上角");
                     //向下扩展
                     if( 展开(n,1,p,1,2,扩展结点) )           {没找到=false;  break;}
                     //向左扩展
                     if( 展开(n,2,p,0,1,扩展结点) )           {没找到=false;  break;}                    
                 }
                 else if(p[0] == 1 && p[1] == 0)//如果 点在左边中间
                 {
                     System.out.println("0点在左边中间");
                     //向上扩展
                     if( 展开(n,0,p,0,0,扩展结点) )           {没找到=false;  break;}
                     //向下扩展
                     if( 展开(n,1,p,2,0,扩展结点) )            {没找到=false;  break;}
                     //向右扩展
                     if( 展开(n,3,p,1,1,扩展结点) )            {没找到=false;  break;}                    
                 }
                 else if(p[0] == 1 && p[1] == 1)//如果 点在正中间
                 {
                     System.out.println("0点在正中间");
                     //向上扩展
                     if( 展开(n,0,p,0,1,扩展结点) )           {没找到=false;  break;}
                     //向下扩展
                     if( 展开(n,1,p,2,1,扩展结点) )            {没找到=false;  break;}
                     //向左扩展
                     if( 展开(n,2,p,1,0,扩展结点) )           {没找到=false;  break;}
                     //向右扩展
                     if( 展开(n,3,p,1,2,扩展结点) )           {没找到=false;  break;}
                 }
                 else if(p[0] == 1 && p[1] == 2)//如果 点在右边中间
                 {
                     System.out.println("0点在右边中间");
                     //向上扩展
                     if( 展开(n,0,p,0,2,扩展结点) )           {没找到=false;  break;}
                     //向下扩展
                     if( 展开(n,1,p,2,2,扩展结点) )            {没找到=false;  break;}
                     //向左扩展
                     if( 展开(n,2,p,1,1,扩展结点) )            {没找到=false;  break;}
                 }
                 else if(p[0] == 2 && p[1] == 0)//如果 点在左下角
                 {
                     System.out.println("0点在左下角");
                     //向上扩展
                     if( 展开(n,0,p,1,0,扩展结点) )            {没找到=false;  break;}
                     //向右扩展
                     if( 展开(n,3,p,2,1,扩展结点) )           {没找到=false;  break;}
                 }
                 else if(p[0] == 2 && p[1] == 1)//如果 点在下边中间
                 {
                     System.out.println("0点在下边中间");
                     //向上扩展
                     if( 展开(n,0,p,1,1,扩展结点) )            {没找到=false;  break;}
                     //向左扩展
                     if( 展开(n,2,p,2,0,扩展结点) )            {没找到=false;  break;}
                     //向右扩展
                     if( 展开(n,3,p,2,2,扩展结点) )            {没找到=false;  break;}
                 }
                 else if(p[0] == 2 && p[1] == 2)//如果 点在右下角
                 {
                     System.out.println("0点在右下角");
                     //向上扩展
                     if( 展开(n,0,p,1,2,扩展结点) )            {没找到=false;  break;}
                     //向左扩展
                     if( 展开(n,3,p,2,1,扩展结点) )           {没找到=false;  break;} 
                 }
                 if(没找到)
                 {
                     n = 取最优结点();
                     System.out.println("最优结点:");
                     打印结点(n);//测试
                     扩展_并查找结点(n);
                     break;
                 }
        }
    }
    
    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,结点[] 扩展结点)
    {
        //展开(待扩展的结点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时结点数组)
        结点 t = new 结点(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.等于(目标结点))
            { 
                System.out.println("=======恭喜!终于找到目标结点了^-^!!!=======");
                打印结点(t);//测试
                最短路径[closednum]=t;
                closednum = closednum+1;
                return true;
            }
            else {                
                扩展结点[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("扩展数组的长度:"+有值的个数(扩展结点));
        最优 = 扩展结点[0];
        for(int i=0;i<有值的个数(扩展结点);i++)
        {
            if((扩展结点[i].深度+扩展结点[i].不相同结点个数)<(最优.深度+最优.不相同结点个数))
            {
                最优 = 扩展结点[i];
            }
        }
        for(int i =0;i<有值的个数(扩展结点);i++)
        {
            if(扩展结点[i]==最优) continue;
            open[opennum]=扩展结点[i];
            opennum=opennum+1;
        }
        //从open表中取出最优结点,放入closed表中
      
        最短路径[closednum]=最优;
        closednum = closednum+1;

        f=0;//重置扩展数组下标
        return 最优;
     }
    
   
    public static int[] 读数()
    {
        int[] a = new int[9];
        int i=0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try
        {
            while(a.length<=9 && i<=8)
            {
                StringTokenizer st = new StringTokenizer(br.readLine());
                while(st.hasMoreTokens())
                {
                    if(i > 8) break;
                    a[i]=Integer.parseInt(st.nextToken());
                    i=i+1;
                }
 
            }
        }
        catch(Exception e){}
        return a;
    }
    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;
    }
    public static void main(String args[])
    {

        int a1[] =new int[9];
        int a2[] =new int[9];
        
        System.out.println("请输入初始结点:");
        a1 = AStar.读数();
        System.out.println("请输入目标结点:");
        a2 = AStar.读数();  
        AStar bsm = new AStar(a1,a2);
        bsm.扩展_并查找结点(bsm.初始结点);
        System.out.println("应用程序终止");
    }
}