astar.java

A*算法的一些资料

import java.util.*;
public class AStar {
    
    /** Creates a new instance of AStar */
    public AStar() {
    }
   
    /**
        Construct the path, not including the start node.
    */
    protected List constructPath(AStarNode node) {
        LinkedList path = new LinkedList();
        while (node.pathParent != null) {
            path.addFirst(node);
            node = node.pathParent;
        }
        return path;
    }

    public List findPath(AStarNode startNode, AStarNode goalNode) {
        
        LinkedList openList = new LinkedList();  //要访问的节点放到这个表
        LinkedList closedList = new LinkedList();  //已经访问过的节点放到这个表
        
        startNode.costFromStart = 0;    //设置起点到自己的距离是0
        startNode.estimatedCostToGoal =
         startNode.getEstimatedCost(goalNode);  //得到至终点的估计成本,赋值给起点
        startNode.pathParent = null;     //和广度优先一样pathParent用来记录,上一个节点,通过遍历就可以找到起点
        openList.add(startNode);  //把起点放入 即将用来搜索的表中
        
        while (!openList.isEmpty()) {
            AStarNode node = (AStarNode)openList.removeFirst();  //从要访问的表中取处一个来
//            if (node == goalNode) {
                // construct the path from start to goal
                //找到终点了,停止搜索,开始遍历路径
                
//            }
            
            List neighbors = node.getNeighbors();
            for (int i=0; i<neighbors.size(); i++) {    //遍历所有的邻居节点
                AStarNode neighborNode =
                        (AStarNode)neighbors.get(i);
                boolean isOpen = openList.contains(neighborNode); 
                //isOpen 用来判断邻居节点在不在即将访问的表中
                boolean isClosed =
                        closedList.contains(neighborNode);
                //isClosed  用来判断邻居节点在不在已经访问过的表中
                int costFromStart = node.costFromStart +node.getCost(neighborNode);  //获得该节点成本
                
                // check if the neighbor node has not been
                // traversed or if a shorter path to this
                // neighbor node is  found.
                if ((!isOpen && !isClosed) ||costFromStart < neighborNode.costFromStart) 
                    //检查邻居节点是否还未遍历,或找到了这个邻居节点的更短路径
                {
                    neighborNode.pathParent = node;
                    neighborNode.costFromStart = costFromStart;
                   // neighborNode.estimatedCostToGoal = neighborNode.getEstimatedCost(goalNode); 
                   //估计到终点的距离的方法,看使用A*的具体场合
                    if (node!= goalNode) {
                        if (isClosed) {
                            closedList.remove(neighborNode);
                            //找到该节点的更短路径,则该路径从已访问过的表中移走
                        }
                        if (!isOpen) {
                            openList.add(neighborNode);
                        }
                    }
                }
            }
            closedList.add(node);
        }
        return constructPath(goalNode);
        
        // no path found
     //   return null;
    }
    public static void main(String[] args) {
        AStarNode nodeA = new  AStarNode("A",0,10);
        AStarNode nodeB = new  AStarNode("B",5,15);
        AStarNode nodeC = new  AStarNode("C",10,20);
        AStarNode nodeD = new AStarNode("D",15,15);
        AStarNode nodeE = new AStarNode("E",20,10);
        AStarNode nodeF = new AStarNode("F",15,5);
        AStarNode nodeG = new AStarNode("G",10,0);
        AStarNode nodeH = new AStarNode("H",5,5);
        
        
        nodeA.neighbors.add(nodeF);
        nodeA.neighbors.add(nodeC);
        nodeA.neighbors.add(nodeE);
        
         nodeC.neighbors.add(nodeA);
         nodeC.neighbors.add(nodeE);
         
         nodeE.neighbors.add(nodeA);
         nodeE.neighbors.add(nodeC);
         nodeE.neighbors.add(nodeF);
         
         nodeF.neighbors.add(nodeA);        
         nodeF.neighbors.add(nodeE);

        
        AStar bfs = new AStar ();
        System.out.println("From A to F: " +
                bfs.findPath(nodeA, nodeF).toString());
        System.out.println("From C to F: " +
               bfs.findPath(nodeC, nodeF).toString());
       System.out.println("From F to C: " +
                bfs.findPath(nodeF, nodeC));
//        System.out.println("From A to G: " +
//                bfs.findPath(nodeH, nodeG).toString());
//        System.out.println("From A to unknown: " +
//                bfs.findPath(nodeA, new AStarNode("unknown",0,0)).toString());

    }
}