eight.java

利用A*算法实现8数码,其中利用数组来实现节点的存贮

public class Eight 
{   Node startNode; 
    Node goalNode; 
    Node expandNode[] = new Node[4]; //保存父节点的四个子节点,顺序存储为上，下，左，右，为扩展的临时数组 
    int f=0;//扩展节点的下标 
    Node open[] = new Node[100]; //扩展节点类 
    Node shortestPath[] = new Node[100];//相当与closed表 
    int opennum=0;//open表中节点的个数 
    int closednum =0;//closed表中节点的个数s 
    Eight(int a1[],int a2[])//构造方法两个参数 数组 
    { 
        startNode = new Node(a1); 
        goalNode = new Node(a2); 
        startNode.stepNumber = startNode.getStepNumber(goalNode);
        goalNode.stepNumber = goalNode.getStepNumber(goalNode); 
        System.out.println("本接点数是"+goalNode.father);
        System.out.println("初始节点到目标节点的步数:"+startNode.stepNumber); 
    } 
     
    public static void printNode(Node h) //输出节点的内容 
 { 
        for(int i=0;i<3;i++) 
        { 
            for(int j=0;j<3;j++) 
                { 
                 System.out.print(h.code[i][j]+" "); 
                } 
            
            System.out.println();
        } 
    } 
    public void Find(Node n)//查找
    {
      boolean isFind = true; 
       if (startNode.ifEqual(goalNode)) 
              { isFind=false; 
               System.out.println("没有必要了!");} 
        while(isFind) 
       {     
                if (n.ifEqual(goalNode)) 
                { 
                 System.out.println("没有必要了!");
                 break; 
                 } 
                if(n.ifEqual(startNode)) 
                { 
                   open[opennum]=n;        // （状态位置,节点对象) 
                   opennum=opennum+1; 
                    shortestPath[closednum]=n; 
                    closednum=closednum+1; 
                    System.out.println("第一次展开"); 
                 } 
                 int[] p= n.getZeroPosition();//知道0的位置                                  
                 System.out.println("=================================待扩展的节点;================================"); 
                 printNode(n);//测试 ///打印
                 //System.out.println("0点位置:"+p[0]+" "+p[1]); 
                 if(p[0]==0 && p[1]==0)//如果0点在左上角 
                 {                                      
                    //展开(待扩展的节点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时节点数组); 
                    //向下扩展 
                    if( Expand(n,1,p,1,0,expandNode) )   
                    {
                    	isFind=false;
                        break;
                    } 
                    //向右扩展   
                    if( Expand(n,3,p,0,1,expandNode) )         
                    {
                    	isFind=false; 
                    	break;} 
                 } 
                 else if(p[0] == 0 && p[1] == 1)//如果0点在上中间的话 
                 {   
                	 System.out.println("0点在上中间"); 
                     //向下扩展 
                     if( Expand(n,1,p,1,1,expandNode) )      
                     {isFind=false; 
                     break;} 
                     //向左扩展 
                     if( Expand(n,2,p,0,0,expandNode) )        
                     {isFind=false; 
                     break;} 
                     //向右扩展 
                     if( Expand(n,3,p,0,2,expandNode) )         
                     {isFind=false; 
                     break;} 
                 }                  
                 else if(p[0] == 0 && p[1] == 2)//如果0点在右上角 
                 { 
                     System.out.println("0点在右上角"); 
                     //向下扩展 
                     if( Expand(n,1,p,1,2,expandNode) )           {isFind=false; break;} 
                     //向左扩展 
                     if( Expand(n,2,p,0,1,expandNode) )           {isFind=false; break;}                     
                 } 
                 else if(p[0] == 1 && p[1] == 0)//如果 0点在左边中间 
                 { 
                      System.out.println("0点在左边中间"); 
                     //向上扩展 
                     if( Expand(n,0,p,0,0,expandNode) )           {isFind=false; break;} 
 //向下扩展 
                     if( Expand(n,1,p,2,0,expandNode) )            {isFind=false; break;} 
                     //向右扩展 
                     if( Expand(n,3,p,1,1,expandNode) )            {isFind=false; break;}                     
                 } 
                 else if(p[0] == 1 && p[1] == 1)//如果 点在正中间 
                 { 
                     System.out.println("0点在正中间"); 
                     //向上扩展 
                     if( Expand(n,0,p,0,1,expandNode) )           {isFind=false; break;} 
                     //向下扩展 
                     if( Expand(n,1,p,2,1,expandNode) )            {isFind=false; break;} 
                     //向左扩展 
                     if( Expand(n,2,p,1,0,expandNode) )           {isFind=false; break;} 
                     //向右扩展 
                     if( Expand(n,3,p,1,2,expandNode) )           {isFind=false; break;} 
                 } 
                 else if(p[0] == 1 && p[1] == 2)//如果 点在右边中间 
                 { 
                   // System.out.println("0点在右边中间"); 
                     //向上扩展 
                     if( Expand(n,0,p,0,2,expandNode) )           {isFind=false; break;} 
                     //向下扩展 
                     if( Expand(n,1,p,2,2,expandNode) )            {isFind=false; break;} 
                     //向左扩展 
                     if( Expand(n,2,p,1,1,expandNode) )            {isFind=false; break;} 
                 } 
                 else if(p[0] == 2 && p[1] == 0)//如果 点在左下角 
                 { 
                   // System.out.println("0点在左下角"); 
                     //向上扩展 
                     if( Expand(n,0,p,1,0,expandNode) )            {isFind=false; break;} 
                     //向右扩展 
                     if( Expand(n,3,p,2,1,expandNode) )           {isFind=false; break;} 
                 } 
                 else if(p[0] == 2 && p[1] == 1)//如果 点在下边中间 
                 { 
                   // System.out.println("0点在下边中间"); 
                     //向上扩展 
                     if( Expand(n,0,p,1,1,expandNode) )            {isFind=false; break;} 
                     //向左扩展 
                     if( Expand(n,2,p,2,0,expandNode) )            {isFind=false; break;} 
                     //向右扩展 
                     if( Expand(n,3,p,2,2,expandNode) )            {isFind=false; break;} 
                 } 
                 else if(p[0] == 2 && p[1] == 2)//如果 点在右下角 
                 { 
                   
                     //向上扩展 
                     if( Expand(n,0,p,1,2,expandNode) )            {isFind=false; break;} 
                     //向左扩展 
                     if( Expand(n,3,p,2,1,expandNode) )           {isFind=false; break;} 
                 } 
                 n.isUsed=true; 
                 if(isFind) 
                 { 
                   for(int i =0;i<NumberNode(expandNode);i++) 
                 {         open[opennum]=expandNode[i]; 
                      opennum=opennum+1; 
                  } 
                      for(int i=0;i<NumberNode(expandNode);i++) 
                     { 
                        expandNode[i]=null; 
                     } 
                     n = BestNode(); 
                     System.out.println("最优节点:"); 
                     printNode(n);//测试 
                     Find(n); //递归
                     break; 
                 } 
             } 
    } 
     
    public boolean isExist(Node n)//判断节点在open表内是否存在 
    { 
        for(int i=0;i<opennum;i++) 
        { 
            if(open[i].ifEqual(n)) 
            	return true; 
        } 
        return false; 
    } 
         
    public boolean Expand(Node n,int direction,int[] z,int q,int p,Node[] expangNode) 
    { 
        //展开(待扩展的节点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时节点数组) 
        Node t = new Node(n); // 用父节点扩展 
        int temp; 
        temp = t.code[z[0]][z[1]]; 
        t.code[z[0]][z[1]] = t.code[q][p]; 
        t.code[q][p] = temp; 
         
        String msg=""; 
        if(direction==0){
        	msg = new String("向上扩展结果");} 
        else if(direction==1){
        	msg = new String("向下扩展结果");} 
        else if(direction==2){
        	msg = new String("向左扩展结果");} 
        else if(direction==3){ 
        	msg = new String("向右扩展结果");} 
        System.out.println(msg); 
        printNode(t);//测试 
        if(!isExist(t))//如果不在open表中其 
        { 
            t.depth = n.depth+1; 
            t.stepNumber = t.getStepNumber(goalNode); 
             t.father=n;             
            if(t.ifEqual(goalNode)) 
            { 
                System.out.println("=======恭喜!找到目标节点!!!======="); 
              
                return true; 
            }else {                 
                expangNode[f] = t;//如果在open表中不存在则装入扩展节点数组中 
                f=f+1; 
            } 
            System.out.println("该节点的深度:"+t.depth+"\n该节点到目标节点的步数:"+t.stepNumber); 
            int r = t.depth+t.stepNumber; 
            System.out.println("择优权值:"+r); 
            System.out.println(); 
        } 
        else 
        { 
            System.out.println("该节点已经分析过了"); 
            return false; 
        } 
        return false; 
    } 
     
    public Node BestNode()//对open表排序找到最优的那个节点 
    { 
        Node bestNode= new Node(); 
        System.out.println("open表内节点个数:"+ NumberNode(open)); 
        bestNode =open[opennum-1]; 
        bestNode.depth=100;
        bestNode.stepNumber=100; 
      
        for(int i=0;i<NumberNode(open);i++) //便历查找出符合最优接点
        {    
            if((open[i].depth+open[i].stepNumber)<(bestNode.depth+bestNode.stepNumber) && !open[i].isUsed) 
            {                                                                                              //测试是否用过
                bestNode =open[i]; 
            } 
        } 
        
        //从open表中取出最优节点,放入closed表中 
       
        shortestPath[closednum]=bestNode; 
        closednum = closednum+1; 
        f=0;//重置扩展数组下标
        
        return bestNode; 
     } 
public static int NumberNode(Node m[])//open  close 表中  确定节点内的个数 
    { 
        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; 
    } 
    		
    
}