public class

AStar

extends Algorithm<A, S, N extends Node<A, S, N>>
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  
Fields
protected final NodeExpander<A, S, N extends HeuristicNode<A, S, C extends Comparable<C>, N>> expander
protected final N extends HeuristicNode<A, S, C extends Comparable<C>, N> initialNode
Public Constructors
AStar(N initialNode, NodeExpander<A, S, N> expander)
Default constructor for ADStarForward.
Public Methods
Iterator iterator()
[Expand]
Inherited Methods
From class es.usc.citius.hipster.algorithm.Algorithm
From class java.lang.Object
From interface java.lang.Iterable

Fields

protected final NodeExpander<A, S, N extends HeuristicNode<A, S, C extends Comparable<C>, N>> expander

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

public Iterator iterator ()