net.sourceforge.jsl
Class AStarSearch

java.lang.Object
  |
  +--net.sourceforge.jsl.AbstractOpenClosedListSearch
        |
        +--net.sourceforge.jsl.AbstractScoringSearch
              |
              +--net.sourceforge.jsl.AStarSearch
All Implemented Interfaces:
ScoringSearch, Search

public class AStarSearch
extends AbstractScoringSearch

Scoring Search using A* strategy. Score is cost of current node SearchNode.getCost() plus estimated rest cost SearchNode.getEstimatedRestCost().

If heuristic of estimated rest cost - as implemented by the custom search node - is admissive this strategy guarantees to find the shallowest goal. A heuristic is admissive if it's estimation of the rest cost is never higher than the actual rest cost.
If heuristic is set to 0 (which of course is admissive) and current cost is set to the depth of the node this strategy is equal to BreadthFirstSearch. These values are default in AbstractSearchNode.

See Also:
BreadthFirstSearch

Field Summary
 
Fields inherited from class net.sourceforge.jsl.AbstractOpenClosedListSearch
closedList, closeGoal, expandCnt, expandGoal, maxClosed, maxDepth, maxExpands, maxOpen, openList, seed, useHashSet
 
Constructor Summary
AStarSearch()
           
 
Method Summary
 double score(SearchNode node)
          Calculates the score of the given node.
 
Methods inherited from class net.sourceforge.jsl.AbstractScoringSearch
sortList, writeState, writeStates
 
Methods inherited from class net.sourceforge.jsl.AbstractOpenClosedListSearch
checkForEmergencyStop, cutOff, expand, getClosedList, getCloseGoal, getExpandGoal, getMaxClosed, getMaxDepth, getMaxExpands, getMaxOpen, getOpenList, search, search, setCloseGoal, setExpandGoal, setMaxClosed, setMaxDepth, setMaxExpands, setMaxOpen, setSeed, setUseHashSet
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface net.sourceforge.jsl.Search
search, search, setSeed
 

Constructor Detail

AStarSearch

public AStarSearch()
Method Detail

score

public double score(SearchNode node)
Description copied from interface: ScoringSearch
Calculates the score of the given node. The score indicates the preference for the expansion of a specidic node, the lower the score, the better.

Specified by:
score in interface ScoringSearch
Specified by:
score in class AbstractScoringSearch
Parameters:
node - the node to calculate the score for
Returns:
the score for the node in double precision


Copyright 2003-2004 Henrik Heine, Oliver Zeigermann. All Rights Reserved.