bashuma2.java

用java实现人工智能中经典的A*算法

import java.io.*;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.StringTokenizer;
//启发函数为f(x)=g(x)+h(x)，g(x)为结点x的深度，h(x)为结点x与目标结点相同元素的个数
public class BaShuMa2 {
    JieDian chushijiedian; 
    JieDian mubiaojiedian;
    JieDian father;
    JieDian kuozhanjiedian[] = new JieDian[4]; //保存父结点的四个子结点,顺序存储为上，下，左，右，为扩展的临时数组
    int f=0;//扩展结点的下标
    JieDian open[] = new JieDian[100];         //扩展结点类
    JieDian zuiduanlujing[] = new JieDian[100];//相当与closed表
    int opennum=0;   //open表中结点的个数
    int closednum =0;//closed表中结点的个数s
    BaShuMa2(int a1[],int a2[])
    {
        chushijiedian = new JieDian(a1);
        mubiaojiedian = new JieDian(a2); 
        //初始结点.不相同结点个数 = 初始结点.不相同结点个数(目标结点);
        // 目标结点.不相同结点个数 = 目标结点.不相同结点个数(目标结点);
        // System.out.println("初始结点 的 不同点的个数:"+chushijiedian.不相同结点个数);
    }
    public class JieDian
    {  
        int shendu,buxiangtongjiediangeshu;
        int shuma[][] = new int[3][3];
        boolean yongguoma;
        public JieDian()
        {  yongguoma = false;  }
        public JieDian(JieDian n)
        {  shendu = n.shendu;
           for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                        shuma[i][j]=n.shuma[i][j];
           buxiangtongjiediangeshu = n.buxiangtongjiediangeshu;
           yongguoma = n.yongguoma;  
        }
        public JieDian(int a[])
        {   int m=0;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    {   shuma[i][j]=a[m];
                        m=m+1;
                    }
            yongguoma = false;//判断是否被用过
            shendu=0;//把深度负值为零 
        }
        public int[][] qushuzi()
        {    return shuma;     }//在等于中使用，被50行调用
        public boolean dengyu(JieDian st)
        {   int[][] s = st.qushuzi();     int i,j;
            for (i = 0; i < 3; i++)
                for(j = 0 ; j<3 ;j++)
                if (s[i][j] != shuma[i][j])
                    return false;
            return true;
        } 
        public int[] lingdianweizhi()
        {   int weizhi[] = new int[2];
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    if(this.shuma[i][j]==0)
                        {weizhi[0]=i;weizhi[1]=j;}
            return weizhi;     }
        public int buxiangtongjiediangeshu(JieDian a)
        {   int m = 0;
            for(int i=0 ; i<3 ; i++)
                for(int j=0; j<3 ;j++)
                    {    if( a.shuma[i][j] == shuma[i][j] && a.shuma[i][j]!=0 ) m=m+1;}
            return 8-m;   }
    }
    public static void PrintJieDian(JieDian h)
    {
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
                {  System.out.print(h.shuma[i][j]+" "); }
            System.out.println();
        }
    }
    public void kuozhanbingchazhaojiedian(JieDian n)
    {
        JieDian t = new JieDian();    
        int temp = 0;          //交换数码的中间变量
        boolean meizhaodao = true; 
        while(meizhaodao)
        {    
                if( n == chushijiedian)
                {
                    zuiduanlujing[closednum]=n;
                    closednum=closednum+1;
                 }
                 int[] p= n.lingdianweizhi();//知道0的位置，调到0的位置，57行                                 
                 System.out.println("===待扩展的结点;=== ");
                 PrintJieDian(n);//打印结点n,调到71行
                 System.out.println("0点位置:"+p[0]+" "+p[1]);
                 if(p[0]==0 && p[1]==0)//如果0点在左上角
                 {                                     
                    //展开(待扩展的结点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时结点数组);
                    //向下扩展 
                    if( zhankai(n,1,p,1,0,kuozhanjiedian) )            {meizhaodao=false;  break;}//调到214行
                    //向右扩展  
                    if( zhankai(n,3,p,0,1,kuozhanjiedian) )            {meizhaodao=false;  break;}
                 }
                 else if(p[0] == 0 && p[1] == 1)//如果0点在上中间的话
                 {
                     System.out.println("0点在上中间");
                     //向下扩展
                     if( zhankai(n,1,p,1,1,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向左扩展
                     if( zhankai(n,2,p,0,0,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向右扩展
                     if( zhankai(n,3,p,0,2,kuozhanjiedian) )            {meizhaodao=false;  break;}
                 }                 
                 else if(p[0] == 0 && p[1] == 2)//如果0点在右上角
                 {
                     System.out.println("0点在右上角");
                     //向下扩展
                     if( zhankai(n,1,p,1,2,kuozhanjiedian) )           {meizhaodao=false;  break;}
                     //向左扩展
                     if( zhankai(n,2,p,0,1,kuozhanjiedian) )           {meizhaodao=false;  break;}                    
                 }
                 else if(p[0] == 1 && p[1] == 0)//如果 点在左边中间
                 {
                     System.out.println("0点在左边中间");
                     //向上扩展
                     if( zhankai(n,0,p,0,0,kuozhanjiedian) )           {meizhaodao=false;  break;}
                     //向下扩展
                     if( zhankai(n,1,p,2,0,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向右扩展
                     if( zhankai(n,3,p,1,1,kuozhanjiedian) )            {meizhaodao=false;  break;}                    
                 }
                 else if(p[0] == 1 && p[1] == 1)//如果 点在正中间
                 {
                     System.out.println("0点在正中间");
                     //向上扩展
                     if( zhankai(n,0,p,0,1,kuozhanjiedian) )           {meizhaodao=false;  break;}
                     //向下扩展
                     if( zhankai(n,1,p,2,1,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向左扩展
                     if( zhankai(n,2,p,1,0,kuozhanjiedian) )           {meizhaodao=false;  break;}
                     //向右扩展
                     if( zhankai(n,3,p,1,2,kuozhanjiedian) )           {meizhaodao=false;  break;}
                 }
                 else if(p[0] == 1 && p[1] == 2)//如果 点在右边中间
                 {
                     System.out.println("0点在右边中间");
                     //向上扩展
                     if( zhankai(n,0,p,0,2,kuozhanjiedian) )           {meizhaodao=false;  break;}
                     //向下扩展
                     if( zhankai(n,1,p,2,2,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向左扩展
                     if( zhankai(n,2,p,1,1,kuozhanjiedian) )            {meizhaodao=false;  break;}
                 }
                 else if(p[0] == 2 && p[1] == 0)//如果 点在左下角
                 {
                     System.out.println("0点在左下角");
                     //向上扩展
                     if( zhankai(n,0,p,1,0,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向右扩展
                     if( zhankai(n,3,p,2,1,kuozhanjiedian) )           {meizhaodao=false;  break;}
                 }
                 else if(p[0] == 2 && p[1] == 1)//如果 点在下边中间
                 {
                     System.out.println("0点在下边中间");
                     //向上扩展
                     if( zhankai(n,0,p,1,1,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向左扩展
                     if( zhankai(n,2,p,2,0,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向右扩展
                     if( zhankai(n,3,p,2,2,kuozhanjiedian) )            {meizhaodao=false;  break;}
                 }
                 else if(p[0] == 2 && p[1] == 2)//如果 点在右下角
                 {
                     System.out.println("0点在右下角");
                     //向上扩展
                     if( zhankai(n,0,p,1,2,kuozhanjiedian) )            {meizhaodao=false;  break;}
                     //向左扩展
                     if( zhankai(n,3,p,2,1,kuozhanjiedian) )            {meizhaodao=false;  break;} 
                 }
                 if(meizhaodao)
                 {
                     n = quzuiyouzhi();
                     System.out.println("最优结点:");
                     PrintJieDian(n);//测试
                     kuozhanbingchazhaojiedian(n);
                     break;
                 }
        }
    }
    public boolean chunzaifu(JieDian n)
    { 
        boolean b=false;
        for(int i=0;i<opennum;i++)
        {
            if(open[i].dengyu(n)) b=true;
        }
        return b;
    }//判断open表中是否存在
    public boolean zhankai(JieDian n,int k,int[] z,int q,int p,JieDian[] kuozhanjiedian)
    {
        //展开(待扩展的结点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时结点数组
        JieDian t = new JieDian(n);
        // 用父结点扩展,调到30行
        int flag = 0;
        int temp;
        temp = t.shuma[z[0]][z[1]];
        t.shuma[z[0]][z[1]] = t.shuma[q][p];
        t.shuma[q][p] = temp;
        t.father=n;
        if(!chunzaifu(t))//如果不在open表中
        {
            t.shendu = n.shendu+1;
            t.buxiangtongjiediangeshu = t.buxiangtongjiediangeshu(mubiaojiedian);
            if(t.dengyu(mubiaojiedian))
            { 
                System.out.println("=======恭喜!终于找到目标结点了^-^!!!=======");
                PrintJieDian(t);
                zuiduanlujing[closednum]=t;
                closednum = closednum+1;
                return true;
            }
            else 
            {                
                kuozhanjiedian[f] = t;//如果在open表中不存在则装入扩展结点数组中
                f=f+1;
            }
            
            int r = t.shendu+t.buxiangtongjiediangeshu;//r是评估函数
          
            System.out.println();
        }
        else 
        {
            System.out.println("该结点已经分析过了");
            return false;
        }
        return false;
    }
    public JieDian quzuiyouzhi()
    {
        JieDian zuiyou;
        System.out.println("扩展数组的长度:"+youzidegeshu(kuozhanjiedian));
        zuiyou = kuozhanjiedian[0];
        for(int i=0;i<youzidegeshu(kuozhanjiedian);i++)
        {
            if((kuozhanjiedian[i].shendu+kuozhanjiedian[i].buxiangtongjiediangeshu)<=(zuiyou.shendu+zuiyou.buxiangtongjiediangeshu))
            {
                zuiyou = kuozhanjiedian[i];
            }
        }
        for(int i =0;i<youzidegeshu(kuozhanjiedian);i++)
        {
            if(kuozhanjiedian[i]==zuiyou) continue;
            open[opennum]=kuozhanjiedian[i];
            opennum=opennum+1;
        }
        //从open表中取出最优结点,放入closed表中
        zuiduanlujing[closednum]=zuiyou;
        closednum = closednum+1;
        f=0;//重置扩展数组下标
        return zuiyou;
     }
    public static int youzidegeshu(JieDian 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 int[] dushu()
    {
        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 void main(String args[])
    {
        int a1[] =new int[9];
        int a2[] =new int[9];
        System.out.println("请输入初始结点:");
        a1 = BaShuMa2.dushu();
        System.out.println("请输入目标结点:");
        a2 = BaShuMa2.dushu();
        BaShuMa2 bsm = new BaShuMa2(a1,a2);
        bsm.kuozhanbingchazhaojiedian(bsm.chushijiedian);
        
         System.out.println("应用程序终止");
    }
}