findbestpath.java

寻找最短路径A_算法的实现

/*
 * FindBestPath.java
 *
 * Created on 2004年9月24日, 下午8:53
 */

/**
 *
 * @author  xhuad
 */

public class FindBestPath {    
    private char[][] map = null;//地图
    private int maxX,maxY;//最大的地图边界大小
    Node startNode = null;//入口
    Node endNode = null;//出口
    private int endX,endY;
   /*初始化
    *@param setMap 地图
    *@param setX,setY 边界值
    //////////*@param startNode 入口
    //////////*param endNode   出口    
    *@param sX,sY:开始点
    *@param eX,eY:结束点
    */
    public FindBestPath(char[][] setMap,int setX,int setY,int sX,int sY,int eX,int eY) {
        this.map = setMap;
        this.maxY = setX - 1; //x,y互换
        this.maxX = setY - 1; //x,y互换
        //this.startNode = sNode;
        //this.endNode = eNode;        
        
        Node sNode = new Node();
        Node eNode = new Node();
        
        sNode.setFarther(null);
        sNode.setPos(posToNum(sX,sY));
        sNode.setStep(0);
        eNode.setPos(posToNum(eX,eY));
        
        this.startNode = sNode;
        this.endNode = eNode;
        
        this.endX = eX;//numToX(eNode.getPos());
        this.endY = eY;//numToY(eNode.getPos());
        
    }
    
    public int posToNum(int x,int y){//从xy坐标获得编号
        return (x+y*(this.maxY+1));
    }
    
    public int numToX(int num){//从编号获得x坐标        
       return (num%(this.maxY+1));
    }
    
    public int numToY(int num){//从编号获得y坐标
       return (int)(num/(this.maxY+1));
    }
    
    public boolean checkVal(int x,int y){//判断是否为障碍     
        //System.out.println("map["+x+"]["+y+"]="+map[x][y]);
        if(this.map[x][y] == 'N')
            return false;
        else
            return true;
    }
    
    public int judge(Node nowNode){//一定要比实际距离小
        //System.out.println("nowNodePos:"+nowNode.getPos());
        int nowX = numToX(nowNode.getPos());
        int nowY = numToY(nowNode.getPos());        
        int distance = Math.abs((nowX-this.endX))+Math.abs((nowY-this.endY));
      //  System.out.println("distance:"+distance);        
        return distance;
    }
    

    public Node getLeft(Node nowNode){//取得左节点
        int nowX = numToX(nowNode.getPos());
        int nowY = numToY(nowNode.getPos());
        Node tmpNode = new Node();
        if(nowY > 0){//判断节点是否到最左                
            if(checkVal(nowX,nowY-1)){
                tmpNode.setFarther(nowNode);
                tmpNode.setPos(posToNum(nowX,nowY-1));
                tmpNode.setStep(nowNode.getStep()+1);
                tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
                return tmpNode;
            }            
        }
        return null;
    }
    
    public Node getRight(Node nowNode){//取得右节点
        int nowX = numToX(nowNode.getPos());
        int nowY = numToY(nowNode.getPos());
        Node tmpNode = new Node();
        if(nowY < this.maxX){//判断节点是否到最左                
            if(checkVal(nowX,nowY+1)){
                tmpNode.setFarther(nowNode);
                tmpNode.setPos(posToNum(nowX,nowY+1));
                tmpNode.setStep(nowNode.getStep()+1);
                tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
                return tmpNode;
            }            
        }
        return null;
    }
    
    public Node getTop(Node nowNode){//取得上节点
        int nowX = numToX(nowNode.getPos());
        int nowY = numToY(nowNode.getPos());
        Node tmpNode = new Node();
        if(nowX > 0){//判断节点是否到最左                
            if(checkVal(nowX-1,nowY)){
                tmpNode.setFarther(nowNode);
                tmpNode.setPos(posToNum(nowX-1,nowY));
                tmpNode.setStep(nowNode.getStep()+1);
                tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
                return tmpNode;
            }            
        }
        return null;
    }
    
    public Node getBottom(Node nowNode){//取得下节点
        int nowX = numToX(nowNode.getPos());
        int nowY = numToY(nowNode.getPos());
        Node tmpNode = new Node();
        if(nowX < this.maxY){//判断节点是否到最左                
            if(checkVal(nowX+1,nowY)){
                tmpNode.setFarther(nowNode);
                tmpNode.setPos(posToNum(nowX+1,nowY));
                tmpNode.setStep(nowNode.getStep()+1);
                tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));
                return tmpNode;
            }            
        }
        return null;
    }
    
    
    public Link getBestPath(){//寻找路径
        Link openLink = new Link();//没有访问的路径
        Link closeLink = new Link();//访问过的路径
        Link path = null;//最短路径
        Node bestNode = null;     
        
        Node tmpNode = null;
        
        openLink.addNode(this.startNode);                
        while(!openLink.isEmpty())//openLink is not null
        {                    
            bestNode = openLink.getBestNode();//取得最好的节点
            //System.out.println("bestNode:("+numToX(bestNode.getPos())+","+numToY(bestNode.getPos())+")step:"+bestNode.getJudgeNum());
            if(bestNode.getPos()==this.endNode.getPos())
            {
                /*this.endNode.setStep(bestNode.getStep()+1);
                this.endNode.setFarther(bestNode);
                this.endNode.setJudgeNum(bestNode.getStep()+1);*/
                path = makePath(bestNode);
                break;
            }
            else
            {   
                tmpNode = closeLink.checkNode(getLeft(bestNode));
                if(tmpNode != null)
                    //System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
                    openLink.addNode(tmpNode);
                
                tmpNode = closeLink.checkNode(getRight(bestNode));
                if(tmpNode != null)
                //    System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
                    openLink.addNode(tmpNode);
                
                tmpNode = closeLink.checkNode(getTop(bestNode));
                if(tmpNode != null)
                  //  System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
                    openLink.addNode(tmpNode);
                
                tmpNode = closeLink.checkNode(getBottom(bestNode));
                if(tmpNode != null)
                 //   System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");
                    openLink.addNode(tmpNode);         
                
                openLink.delNode(bestNode);
                closeLink.addNode(bestNode);                
            }
        }       
        return path;        
    }
    
    public Link makePath(Node lastNode){//制造路径
        Link tmpLink = new Link();
        Node tmpNode = new Node();
        int x,y;
        tmpNode = lastNode;
        if(tmpNode != null){
            do{           
                x=numToX(tmpNode.getPos());
                y=numToY(tmpNode.getPos());
                System.out.println("map["+x+"]["+y+"]="+map[x][y]);
                tmpLink.addNode(tmpNode);
                tmpNode = tmpNode.getFarther();            
            }while(tmpNode != null);        
        }else
        {
            System.out.println("Couldn't find the path!");
        }
        return tmpLink;
    }
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        char[][] map ={
            {'Y', 'N', 'z', 'y', 'x', 'w', 'v', 'N', 'N', 'N'},
            {'Y', 'N', '1', 'N', 'N', 'N', 'u', 't', 'N', 'N'},
            {'N', '1', '2', '1', '1', '1', 'N', 's', 'N', 'N'},
            {'N', 'N', '1', 'N', '9', 'N', 'q', 'r', 'N', 'N'},
            {'N', 'N', '1', 'N', 'n', 'o', 'p', 'N', 'N', 'N'},
            {'N', '4', '5', '6', 'm', 'N', 'N', 'N', 'N', 'N'},
            {'N', '3', 'N', '5', 'l', 'k', 'j', 'N', 'N', 'N'},
            {'N', 'N', '3', '4', 'N', 'd', 'i', 'd', 'N', 'N'},
            {'N', '1', 'N', 'N', '1', 'N', 'h', 'N', 'N', 'N'},
            {'N', '1', 'N', 'N', '1', 'N', 'g', 'N', 'N', 'N'},
            {'N', 'a', 'b', 'c', 'd', 'e', 'f', 'N', 'N', 'N'}
        };
        /*map[x][y] 
         *如上所示：maxY=10 maxX=11 横的代表maxY,竖的代表maxX 可以自己替换
         *地图的读取是
         *for(i=1;i<行的最大值;i++)
         *  for(j=1;j<列的最大值;j++)         
         *    map[i][j] = 地图[i][j]
         */       
        Link bestPath = new Link();
        /*startNode.setFarther(null);
        startNode.setPos(21);
        startNode.setStep(0);
        
        //endNode.setFarther(startNode);
        endNode.setPos(79);
        //endNode.setStep(0);*/
        
        FindBestPath path =  new FindBestPath(map, 11, 10, 10, 1, 0, 2);
        //FindBestPath path =  new FindBestPath(map, 11, 10, startNode, endNode);
        
        bestPath = path.getBestPath();
        //bestPath.printLink();

    }
    
}