java.lang.Object |
↳ |
es.usc.citius.hipster.algorithm.Algorithm<A, S, N extends es.usc.citius.hipster.model.Node<A, S, N>> |
|
↳ |
es.usc.citius.hipster.algorithm.AStar<A, S, C extends java.lang.Comparable<C>, N extends es.usc.citius.hipster.model.HeuristicNode<A, S, C, N>> |
Class Overview
Implementation of the A* algorithm. The A* algorithm extends the original
Dijkstra's algorithm by including heuristics to improve the search. By default,
the implementation uses a java.util.PriorityQueue for the nodes, which requires
O(log n) time for insertions. The queue can be changed to use another
type of queue, for example a fibonacci heap as a queue, which works with constant amortized
time for insertions.
Original paper:
Hart, Peter E., Nils J. Nilsson, and Bertram Raphael.
"A formal basis for the heuristic determination of minimum cost paths.".
IEEE Transactions on Systems Science and Cybernetics 4.2 (1968): 100-107.
Summary
Nested Classes |
class |
AStar.Iterator |
Internal iterator that implements all the logic of the A* search
|
Public Constructors |
|
AStar(N initialNode, NodeExpander<A, S, N> expander)
Default constructor for ADStarForward.
|
[Expand]
Inherited Methods |
From class
es.usc.citius.hipster.algorithm.Algorithm
static
<A, N extends Node<A, ?, N>>
List<A>
|
recoverActionPath(N node)
Returns a path of the actions applied from the initial state
to the state of the provided node ( state() ).
|
static
<S, N extends Node<?, S, N>>
List<S>
|
recoverStatePath(N node)
Returns a path with all the states of the path.
|
SearchResult
|
search(S goalState)
Run the algorithm until the goal is found or no more states are
available.
|
SearchResult
|
search(Predicate<N> condition)
Executes the search algorithm until the predicate condition is
satisfied or there are no more nodes to explore.
|
void
|
search(SearchListener<N> listener)
Executes the search algorithm and invokes the method
handle(Object) passing the current
explored node to the listener.
|
|
From class
java.lang.Object
Object
|
clone()
|
boolean
|
equals(Object arg0)
|
void
|
finalize()
|
final
Class<?>
|
getClass()
|
int
|
hashCode()
|
final
void
|
notify()
|
final
void
|
notifyAll()
|
String
|
toString()
|
final
void
|
wait()
|
final
void
|
wait(long arg0, int arg1)
|
final
void
|
wait(long arg0)
|
|
From interface
java.lang.Iterable
abstract
Iterator<T>
|
iterator()
|
|
Fields
protected
final
N extends HeuristicNode<A, S, C extends Comparable<C>, N>
initialNode
Public Constructors
public
AStar
(N initialNode, NodeExpander<A, S, N> expander)
Default constructor for ADStarForward. Requires the initial state, the successor function to generate
the neighbor states of a current one and the factory to instantiate new nodes.
Parameters
initialNode |
the initial node (which contains the initial state of the search). |
expander |
function to obtain (expand) a node to obtain the successor nodes.
|
Public Methods