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