Class AStarIterator
Object
AbstractGraphIterator
SourceGraphIterator
AStarIterator
- All Implemented Interfaces:
GraphIterator
A path iterator that uses a function (usually denoted f(x)) to determine the order in which the algorithm visits
nodes, f(x) is a sum of two functions:
- The path-cost function (usually denoted g(x), which may or may not be a heuristic)
- An admissible "heuristic estimate" (usually denoted h(x)).
// COST(n,n') : the real cost to go from n to n'
OPEN = [Source]
CLOSE = []
while ( |OPEN| > 0 )
n = a node in OPEN with less f
remove n from OPEN
add n to CLOSE
if ( n == target ) {
return // path find
// if n != target
for each node n' that relates to n do
if n' in OPEN
if (g(n) + COST(n,n')) < g(n')
g(n') = g(n) + COST(n,n')
parent(n') = n
else
g(n') = g(n) + COST(n,n')
parent(n') = n
add n' to OPEN
// end while
For more details see http://en.wikipedia.org/wiki/A_star- Author:
- Germán E. Trouillet, Francisco G. Malbrán. Universidad Nacional de Córdoba (UNC)
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic class
Defines the functions needed by A Star.static class
Internal data structure used to track node costs, and parent nodes. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
cont
(Graphable current, GraphTraversal traversal) Makes a step of the A* algorithm.protected Iterator<?>
getRelated
(Graphable current) void
init
(Graph graph, GraphTraversal traversal) Does Nothing.void
killBranch
(Graphable current, GraphTraversal traversal) Kills the branch of the traversalnext
(GraphTraversal traversal) Returns the next node in the priority queue. if the queue is empty then there is no path from the source to the destiny in this graph.Methods inherited from class SourceGraphIterator
getSource, setSource
Methods inherited from class AbstractGraphIterator
getGraph, getTraversal, getWalker, setTraversal
-
Constructor Details
-
AStarIterator
-
-
Method Details
-
init
Does Nothing. All the work was already done by the constructor.- Parameters:
graph
- The graph being whose components are being iterated over.
-
next
Returns the next node in the priority queue. if the queue is empty then there is no path from the source to the destiny in this graph.- Returns:
- The next component in the iteration, or null if iteration is complete.
- See Also:
-
org.geotools.graph.traverse.GraphIterator#next()
-
cont
Makes a step of the A* algorithm. Takes the current node, looks for its neighbours. The ones which are closed are discarted. The ones "in" the opened queue are checked to see if its necessary to update them. The rest of the nodes are initialized as AStarNodes and inserted in the opened queue.- Parameters:
current
- The current component of the traversal.- See Also:
-
org.geotools.graph.traverse.GraphIterator#cont(Graphable)
-
killBranch
Kills the branch of the traversal- Parameters:
current
- The current component of the traversal.- See Also:
-
org.geotools.graph.traverse.GraphIterator#killBranch(Graphable)
-
getParent
-
getRelated
-