root/trunk/AStarSearch.java

// AStarSearch - copyright Tom Felker, <tfelker2@uiuc.edu>, December 2004
// implements an A* search algorithm
// fits into the UIUC pathways system

import java.util.*;

public class AStarSearch extends Search {

        // construct ourselves
        public AStarSearch() {
                super();
                open = new TreeSet();
                searchNodes = new HashMap();
        }

        // note that this method contains many println's, which can be comented
        // out in normal use, but are left in now to clarify what happens
        // and when comparisons are performed.  They are not indented so they
        // can be easily seen and commented out

        // this returns the lowest-cost path between the origin and destination
        // nodes (which were set earlier), or null if no path is found.
        public Path computeBestPath() {

                // for now, don't try to optimize by saving old searchnodes
                open.clear();
                searchNodes.clear();

                // put the start node on the open list
                SearchNode current = new SearchNode(origin);
                current.isOpen = true;
                searchNodes.put(current.node, current);
                open.add(current);

                // repeat as long as the open list isn't empty
                while(open.size() != 0) {

                        // set current to the node with the lowest f cost on open list

                        // we use an iterator, because this way, we can remove the lowest
                        // element with zero comparisons (possibly lg(n) pointer dereferences,
                        // though, depending on Java's TreeMap implementation).

                        Iterator iter = open.iterator();
                        current = (SearchNode)iter.next();
                        iter.remove();
                        current.isOpen = false;

                        // were we successful?  maybe.  hooray!
                        if(current.node == destination) break;

                        // for each node n adjacent to current (by edge e)...
                        iter = current.node.edges.iterator();
                        while(iter.hasNext()) {
                                Edge e = (Edge)iter.next();

                                // This is a hash, so the membership test runs in O(1) time
                                // Note that we never have to perform a membership test on the open list,
                                // which would be O(lg(n)), because if a node is in the open list, it's
                                // also in searchNodes and its isOpen property is true.
                                SearchNode n = (SearchNode)searchNodes.get(e.getOtherNode(current.node));

                                if(n == null) {
                                        // n wasn't on any list, so we calculate
                                        // its costs and add it to open
                                        n = new SearchNode(e.getOtherNode(current.node));

                                        // note that we cache h costs - memory access
                                        // is probably cheaper than the Pythagorean formula


                                        //changed for bus nodes!
                                        //g cost is already traversed cost. could represent
                                        // absolute time(ie, 3:30 pm). This is needed in H
                                        // cost for absolute time bus schedules
                                        // h cost is hard to envision as absolute.

                                        //cleanup SearchNode!!
                                        n.h = n.node.computeHCost(this, current.node);
                                        n.g = e.computeDeltaGCost(current.node, current.g, this);
                                        n.g.add(current.g);
                                        n.f = Cost.add(n.g, n.h);
                                        n.parent = e;
                                        n.isOpen = true;
                                        searchNodes.put(n.node, n);

                                        // we keep track of this to ensure that the open list grows
                                        // when we add to it, to ensure that the horrible hack we
                                        // do actually works.

                                        int oldOpenSize = open.size();
                                        open.add(n);

                                        if(open.size() != oldOpenSize + 1)
                                                throw new RuntimeException("Open list didn't grow!!!");

                                        continue;
                                }

                                // After some exerimentation, it seems that when the heuristic is
                                // nonzero, and only when the graph is relatively large, we
                                // do need to checked nodes on the closed list.  Whatever.

                                // in other words, don't uncomment the following line:
                                // if(!n.isOpen) continue;

                                Cost possibleG = e.computeDeltaGCost(current.node, current.g, this);
                                possibleG.add(current.g);
                                if(possibleG.compareTo(n.g) < 0) {

                                        // we must remove and re-add to the open list
                                        // otherwise, the list will get unsorted
                                        // This could be optimized, but java won't let us
                                        // get close enough to the tree to only compare
                                        // with parents.  Time is still O(lg(n)).
                                        if(n.isOpen) open.remove(n);
                                        n.g = possibleG;
                                        n.f = Cost.add(n.g, n.h);
                                        n.parent = e;

                                        int oldOpenSize = open.size();
                                        open.add(n);
                                        if(open.size() != oldOpenSize + 1)
                                                throw new RuntimeException("Open list didn't grow!!!");
                                }

                        } // end for(all current's neighbors)
                } // end while(open is nonempty)

                // if we didn't reach the destination, we probably didn't
                // have a path to it.
                if(current.node != destination) return null;

                // trace backwards, populating our path
                Path path = new Path();
                path.setTotalCost( current.g );
                for(; current.parent != null;
                    current = (SearchNode)searchNodes.get(current.parent.getOtherNode(current.node))) {
                        path.nodes.addFirst(current.node);
                        path.edges.addFirst(current.parent);
                }

                // Our loop will have left out the origin...
                path.nodes.addFirst(origin);

                // yay, we're done!
                return path;
        }

        // returns all the nodes that were searched in the last search.
        public Collection getSearchedNodes() {
                return searchNodes.keySet();
        }

        public Collection getOpenNodes() {
                Collection openNodes = new LinkedList();
                Iterator i = open.iterator();
                while(i.hasNext()) {
                        openNodes.add(((SearchNode)i.next()).node);
                }
                return openNodes;
        }

        // Data structures:
        //
        // We have searchNodes, which we create from nodes, and we want there
        // to be only one SearchNode per Node per AStarSearch.  So, we keep
        // a hashmap (O(1) addition, lookup, and deletion).  Because of the way
        // the algorithm works, as soon as we need to make a SearchNode, it will
        // be on either the open list or the closed list.  Therefore, we don't
        // need an explicit closed-list - anything that's not in the hash is known
        // to not be on either list

        // TreeSet is used because it has O(log n) running time for:
        // containsKey, get, put and remove, and it maintains the list sorted
        // so it has O(1) getting of the lowest cost element.

        SortedSet open;

        // maps Nodes to SearchNodes
        // A hashmap is used here, because it has constant time for get and put,
        // which will be done alot here.

        Map searchNodes;

        // Note - SortedMap and Map are used, because they are more general - we
        // can then choose which implementation we want at runtime.

}