590 lines
23 KiB
HTML
590 lines
23 KiB
HTML
<HTML>
|
|
<!--
|
|
Copyright (c) 2004 Kris Beevers
|
|
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
-->
|
|
<Head>
|
|
<Title>Boost Graph Library: A* Heuristic Search</Title>
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../boost.png"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<BR Clear>
|
|
|
|
<H1><A NAME="sec:astar"></A>
|
|
<TT>astar_search</TT>
|
|
</H1>
|
|
|
|
|
|
<P>
|
|
<PRE>
|
|
<i>// Named parameter interfaces</i>
|
|
template <typename VertexListGraph,
|
|
typename AStarHeuristic,
|
|
typename P, typename T, typename R>
|
|
void
|
|
astar_search
|
|
(const VertexListGraph &g,
|
|
typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
|
<a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params);
|
|
|
|
template <typename VertexListGraph,
|
|
typename AStarHeuristic,
|
|
typename P, typename T, typename R>
|
|
void
|
|
astar_search_no_init
|
|
(const IncidenceGraph &g,
|
|
typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
|
<a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params);
|
|
|
|
template <typename VertexListGraph,
|
|
typename AStarHeuristic,
|
|
typename P, typename T, typename R>
|
|
void
|
|
astar_search_tree
|
|
(const VertexListGraph &g,
|
|
typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
|
<a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params);
|
|
|
|
template <typename VertexListGraph,
|
|
typename AStarHeuristic,
|
|
typename P, typename T, typename R>
|
|
void
|
|
astar_search_no_init_tree
|
|
(const IncidenceGraph &g,
|
|
typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
|
<a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params);
|
|
|
|
<i>// Non-named parameter interface</i>
|
|
template <typename VertexListGraph, typename AStarHeuristic,
|
|
typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
|
|
typename CostMap, typename DistanceMap,
|
|
typename WeightMap, typename VertexIndexMap,
|
|
typename ColorMap,
|
|
typename <a href="http://www.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/stl/BinaryFunction.html">CombineFunction</a>,
|
|
typename CostInf, typename CostZero>
|
|
inline void
|
|
astar_search
|
|
(const VertexListGraph &g,
|
|
typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
|
AStarHeuristic h, AStarVisitor vis,
|
|
PredecessorMap predecessor, CostMap cost,
|
|
DistanceMap distance, WeightMap weight,
|
|
VertexIndexMap index_map, ColorMap color,
|
|
CompareFunction compare, CombineFunction combine,
|
|
CostInf inf, CostZero zero);
|
|
|
|
template <typename VertexListGraph, typename AStarHeuristic,
|
|
typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
|
|
typename CostMap, typename DistanceMap,
|
|
typename WeightMap,
|
|
typename <a href="http://www.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/stl/BinaryFunction.html">CombineFunction</a>,
|
|
typename CostInf, typename CostZero>
|
|
inline void
|
|
astar_search_tree
|
|
(const VertexListGraph &g,
|
|
typename graph_traits<VertexListGraph>::vertex_descriptor s,
|
|
AStarHeuristic h, AStarVisitor vis,
|
|
PredecessorMap predecessor, CostMap cost,
|
|
DistanceMap distance, WeightMap weight,
|
|
CompareFunction compare, CombineFunction combine,
|
|
CostInf inf, CostZero zero);
|
|
|
|
<i>// Versions that do not initialize property maps (used for implicit graphs)</i>
|
|
template <typename IncidenceGraph, typename AStarHeuristic,
|
|
typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
|
|
typename CostMap, typename DistanceMap,
|
|
typename WeightMap, typename ColorMap,
|
|
typename VertexIndexMap,
|
|
typename <a href="http://www.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/stl/BinaryFunction.html">CombineFunction</a>,
|
|
typename CostInf, typename CostZero>
|
|
inline void
|
|
astar_search_no_init
|
|
(const IncidenceGraph &g,
|
|
typename graph_traits<IncidenceGraph>::vertex_descriptor s,
|
|
AStarHeuristic h, AStarVisitor vis,
|
|
PredecessorMap predecessor, CostMap cost,
|
|
DistanceMap distance, WeightMap weight,
|
|
ColorMap color, VertexIndexMap index_map,
|
|
CompareFunction compare, CombineFunction combine,
|
|
CostInf inf, CostZero zero);
|
|
|
|
<b>Note that the index_map and color parameters are swapped in
|
|
astar_search_no_init() relative to astar_search(); the named parameter
|
|
interfaces are not affected.</b>
|
|
|
|
template <typename IncidenceGraph, typename AStarHeuristic,
|
|
typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
|
|
typename CostMap, typename DistanceMap,
|
|
typename WeightMap,
|
|
typename <a href="http://www.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/stl/BinaryFunction.html">CombineFunction</a>,
|
|
typename CostInf, typename CostZero>
|
|
inline void
|
|
astar_search_no_init_tree
|
|
(const IncidenceGraph &g,
|
|
typename graph_traits<IncidenceGraph>::vertex_descriptor s,
|
|
AStarHeuristic h, AStarVisitor vis,
|
|
PredecessorMap predecessor, CostMap cost,
|
|
DistanceMap distance, WeightMap weight,
|
|
CompareFunction compare, CombineFunction combine,
|
|
CostInf inf, CostZero zero);
|
|
</PRE>
|
|
|
|
<P>
|
|
This algorithm implements a heuristic search on a weighted, directed
|
|
or undirected graph for the case where all edge weights are
|
|
non-negative.
|
|
</P>
|
|
|
|
<P>
|
|
The A* algorithm is a <i>heuristic graph search algorithm</i>: an A*
|
|
search is "guided" by a <i>heuristic function</i>. A heuristic
|
|
function <i>h(v)</i> is one which estimates the cost from a non-goal
|
|
state (<i>v</i>) in the graph to some goal state, <i>g</i>.
|
|
Intuitively, A* follows paths (through the graph) to the goal that are
|
|
estimated by the heuristic function to be the best paths. Unlike
|
|
best-first search, A* takes into account the known cost from the start
|
|
of the search to <i>v</i>; the paths A* takes are guided by a function
|
|
<i>f(v) = g(v) + h(v)</i>, where <i>h(v)</i> is the heuristic
|
|
function, and <i>g(v)</i> (sometimes denoted <i>c(s, v)</i>) is the
|
|
known cost from the start to <i>v</i>. Clearly, the efficiency of A*
|
|
is highly dependent on the heuristic function with which it is used.
|
|
</P>
|
|
|
|
<P>
|
|
The A* algorithm is very similar to Dijkstra's Shortest Paths
|
|
algorithm. This implementation finds all the shortest paths from the
|
|
start vertex to every other vertex by creating a search tree,
|
|
examining vertices according to their remaining cost to some goal, as
|
|
estimated by a heuristic function. Most commonly, A* is used to find
|
|
some specific goal vertex or vertices in a graph, after which the
|
|
search is terminated.
|
|
</P>
|
|
|
|
<P>
|
|
A* is particularly useful for searching <i>implicit</i> graphs.
|
|
Implicit graphs are graphs that are not completely known at the
|
|
beginning of the search. Upon visiting a vertex, its neighbors are
|
|
"generated" and added to the search. Implicit graphs are particularly
|
|
useful for searching large state spaces -- in game-playing scenarios
|
|
(e.g. chess), for example -- in which it may not be possible to store
|
|
the entire graph. Implicit searches can be performed with this
|
|
implementation of A* by creating special visitors that generate
|
|
neighbors of newly-expanded vertices. Please note that
|
|
<tt>astar_search_no_init()</tt> or <tt>astar_search_no_init_tree()</tt> must be
|
|
used for implicit graphs; the basic
|
|
<tt>astar_search()</tt> function requires a graph that models
|
|
the <a href="VertexListGraph.html">Vertex List Graph</a> concept. Both
|
|
versions
|
|
also require the graph type to model the <a
|
|
href="IncidenceGraph.html">Incidence Graph</a> concept.
|
|
</P>
|
|
|
|
<P>
|
|
For the non-tree versions of the algorithm,
|
|
this implementation of A* is based on an OPEN/CLOSED list formulation.
|
|
Vertices on the OPEN list have been ``discovered''
|
|
by the algorithm, but not ``expanded'' (we have not discovered their
|
|
adjacent vertices). Vertices on the CLOSED list have been completely
|
|
examined by our search (we have expanded them and added their children
|
|
to the OPEN list). Vertices that are on neither list have not been
|
|
encountered in any context so far in our search. A major advantage of
|
|
this formulation of the A* algorithm over other approaches is that it
|
|
avoids ``cycles'' in the state space; the search will not become
|
|
trapped by loops in the graph. The OPEN/CLOSED lists are implemented
|
|
using BGL's vertex coloring mechanisms. Vertices in OPEN are colored
|
|
gray, vertices in CLOSED are colored black, and undiscovered vertices
|
|
are colored white. For the versions of the algorithm whose names end in
|
|
<tt>_tree</tt>, all vertices are assumed to always be white, leading to
|
|
checking for repeated vertices being done using the distance map. If a dummy
|
|
value is used for the distance map and the graph contains cycles, the algorithm
|
|
will probably enter an infinite loop.
|
|
</P>
|
|
|
|
<P>
|
|
The criteria for expanding a vertex on the OPEN list is that it has
|
|
the lowest <i>f(v) = g(v) + h(v)</i> value of all vertices on OPEN.
|
|
Cost information about vertices is stored in a property map.
|
|
</P>
|
|
|
|
<P>
|
|
The following is the pseudocode for the A* heuristic search algorithm.
|
|
In the pseudocode, <i>h</i> is the heuristic function, <i>w</i> is the
|
|
edge weight, <i>d</i> is the distance of a vertex from <i>s</i>, and
|
|
<i>Q</i> is a priority queue, sorted by <i>f</i>, the estimated cost
|
|
to the goal of the path through a vertex. <i>p</i> is a predecessor
|
|
map. The visitor event points for the algorithm are indicated by the
|
|
labels on the right.
|
|
</P>
|
|
|
|
<table>
|
|
<tr>
|
|
<td valign="top">
|
|
<pre>
|
|
A*(<i>G</i>, <i>s</i>, <i>h</i>)
|
|
<b>for</b> each vertex <i>u in V</i>
|
|
<i>d[u] := f[u] := infinity</i>
|
|
<i>color[u] :=</i> WHITE
|
|
<i>p[u] := u</i>
|
|
<b>end for</b>
|
|
<i>color[s] :=</i> GRAY
|
|
<i>d[s] := 0</i>
|
|
<i>f[s] := h(s)</i>
|
|
INSERT(<i>Q, s</i>)
|
|
<b>while</b> (<i>Q != Ø</i>)
|
|
<i>u :=</i> EXTRACT-MIN(<i>Q</i>)
|
|
<b>for</b> each vertex <i>v in Adj[u]</i>
|
|
<b>if</b> (<i>w(u,v) + d[u] < d[v]</i>)
|
|
<i>d[v] := w(u,v) + d[u]</i>
|
|
<i>f[v] := d[v] + h(v)</i>
|
|
<i>p[v] := u</i>
|
|
<b>if</b> (<i>color[v] =</i> WHITE)
|
|
<i>color[v] :=</i> GRAY
|
|
INSERT(<i>Q, v</i>)
|
|
<b>else if</b> (<i>color[v] =</i> BLACK)
|
|
<i>color[v] :=</i> GRAY
|
|
INSERT(<i>Q, v</i>)
|
|
<b>end if</b>
|
|
<b>else</b>
|
|
<i>...</i>
|
|
<b>end for</b>
|
|
<i>color[u] :=</i> BLACK
|
|
<b>end while</b>
|
|
</pre>
|
|
</td>
|
|
<td valign="top">
|
|
<pre>
|
|
|
|
initialize vertex <i>u</i>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
discover vertex <i>s</i>
|
|
|
|
examine vertex <i>u</i>
|
|
examine edge <i>(u,v)</i>
|
|
|
|
edge <i>(u,v)</i> relaxed
|
|
|
|
|
|
|
|
|
|
discover vertex <i>v</i>
|
|
|
|
|
|
reopen vertex <i>v</i>
|
|
|
|
|
|
edge <i>(u,v)</i> not relaxed
|
|
|
|
finish vertex <i>u</i>
|
|
</pre>
|
|
</td>
|
|
</tr>
|
|
</table>
|
|
|
|
<h3>Where Defined</h3>
|
|
|
|
<a href="../../../boost/graph/astar_search.hpp"><tt>boost/graph/astar_search.hpp</tt></a>
|
|
|
|
<h3>Parameters</h3>
|
|
|
|
IN: <tt>const VertexListGraph& g</tt>
|
|
<blockquote>
|
|
The graph object on which the algorithm will be applied for <tt>astar_search()</tt>. The type
|
|
<tt>VertexListGraph</tt> must be a model of the <a
|
|
href="VertexListGraph.html">
|
|
Vertex List Graph</a> and <a href="IncidenceGraph.html">Incidence Graph</a>
|
|
concepts.
|
|
</blockquote>
|
|
|
|
IN: <tt>const IncidenceGraph& g</tt>
|
|
<blockquote>
|
|
The graph object on which the algorithm will be applied for <tt>astar_search_no_init()</tt>. The type
|
|
<tt>IncidenceGraph</tt> must be a model of the
|
|
<a href="IncidenceGraph.html">Incidence Graph</a>
|
|
concept.
|
|
</blockquote>
|
|
|
|
IN: <tt>vertex_descriptor s</tt>
|
|
<blockquote>
|
|
The start vertex for the search. All distances will be calculated
|
|
from this vertex, and the shortest paths tree (recorded in the
|
|
predecessor map) will be rooted at this vertex.
|
|
</blockquote>
|
|
|
|
IN: <tt>AStarHeuristic h</tt>
|
|
<blockquote>
|
|
The heuristic function that guides the search. The type
|
|
<tt>AStarHeuristic</tt> must be a model of the <a href="AStarHeuristic.html">AStarHeuristic</a>
|
|
concept.
|
|
</blockquote>
|
|
|
|
<h3>Named Parameters</h3>
|
|
|
|
IN: <tt>weight_map(WeightMap w_map)</tt>
|
|
<blockquote>
|
|
The weight or ``length'' of each edge in the graph. The weights
|
|
must all be non-negative; the algorithm will throw a <a
|
|
href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
|
|
exception if one of the edges is negative. The type
|
|
<tt>WeightMap</tt> must be a model of <a
|
|
href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable
|
|
Property Map</tt></a>. The edge descriptor type of the graph needs
|
|
to be usable as the key type for the weight map. The value type
|
|
for this map must be the same as the value type of the distance
|
|
map.<br>
|
|
<b>Default:</b> <tt>get(edge\_weight, g)</tt>
|
|
</blockquote>
|
|
|
|
IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
|
|
<blockquote>
|
|
This maps each vertex to an integer in the range <tt>[0,
|
|
num_vertices(g))</tt>. This is necessary in non-tree versions of the
|
|
algorithm for efficient updates of
|
|
the heap data structure when an edge is relaxed. The type
|
|
<tt>VertexIndexMap</tt> must be a model of <a
|
|
href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable
|
|
Property Map</tt></a>. The value type of the map must be an integer
|
|
type. The vertex descriptor type of the graph needs to be usable as
|
|
the key type of the map.<br>
|
|
|
|
<b>Default:</b> <tt>get(vertex_index, g)</tt>.
|
|
Note: if you use this default, make sure your graph has
|
|
an internal <tt>vertex_index</tt> property. For example,
|
|
<tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
|
|
not have an internal <tt>vertex_index</tt> property.
|
|
</blockquote>
|
|
|
|
OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
|
|
<blockquote>
|
|
|
|
The predecessor map records the edges in the minimum spanning tree.
|
|
Upon completion of the algorithm, the edges <tt>(p[u],u)</tt> for
|
|
all <tt>u</tt> in <tt>V</tt> are in the minimum spanning tree. If
|
|
<tt>p[u] = u</tt> then <tt>u</tt> is either the start vertex or a
|
|
vertex that is not reachable from the start. The
|
|
<tt>PredecessorMap</tt> type must be a <a
|
|
href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
|
|
Property Map</tt></a> with key and vertex types the same as the
|
|
vertex descriptor type of the graph.<br>
|
|
|
|
<b>Default:</b> <tt>dummy_property_map</tt>
|
|
</blockquote>
|
|
|
|
UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt>
|
|
<blockquote>
|
|
|
|
The shortest path weight from the start vertex <tt>s</tt> to each
|
|
vertex in the graph <tt>g</tt> is recorded in this property map.
|
|
The shortest path weight is the sum of the edge weights along the
|
|
shortest path. The type <tt>DistanceMap</tt> must be a model of <a
|
|
href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
|
|
Property Map</tt></a>. The vertex descriptor type of the graph
|
|
needs to be usable as the key type of the distance map. The value
|
|
type of the distance map is the element type of a <a
|
|
href="./Monoid.html"><tt>Monoid</tt></a> formed with the
|
|
<tt>combine</tt> function object and the zero object for the
|
|
identity element. Also the distance value type must have a <a
|
|
href="http://www.boost.org/sgi/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
|
|
provided by the <tt>compare</tt> function object. A
|
|
<tt>constant_writable_property_map</tt> returning the infinity value can be
|
|
used for this parameter in tree versions of the algorithm when the graph does
|
|
not contain a directed cycle.<br>
|
|
|
|
<b>Default:</b> <tt>shared_array_property_map</tt>
|
|
with the same value type as the
|
|
<tt>WeightMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
|
|
the <tt>i_map</tt> for the index map.
|
|
</blockquote>
|
|
|
|
UTIL/OUT: <tt>rank_map(CostMap c_map)</tt>
|
|
<blockquote>
|
|
|
|
The <i>f</i>-value for each vertex. The <i>f</i>-value is defined
|
|
as the sum of the cost to get to a vertex from the start vertex, and
|
|
the estimated cost (as returned by the heuristic function
|
|
<tt>h</tt>) from the vertex to a goal. The type <tt>CostMap</tt>
|
|
must be a model of <a
|
|
href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
|
|
Property Map</tt></a> in non-tree versions of the algorithm, and <a
|
|
href="../../property_map/doc/WritablePropertyMap.html"><tt>Writable Property
|
|
Map</tt></a> in tree versions of the algorithm. The vertex descriptor type
|
|
of the graph
|
|
needs to be usable as the key type of the distance map. The value
|
|
type of the distance map is the element type of a <a
|
|
href="./Monoid.html"><tt>Monoid</tt></a> formed with the
|
|
<tt>combine</tt> function object and the zero object for the
|
|
identity element. Also the distance value type must have a <a
|
|
href="http://www.boost.org/sgi/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
|
|
provided by the <tt>compare</tt> function object. The value type
|
|
for this map must be the same as the value type for the distance
|
|
map. In tree versions of the algorithm, <tt>null_property_map</tt> can be
|
|
used for this parameter.<br>
|
|
|
|
<b>Default:</b> <tt>shared_array_property_map</tt>
|
|
with the same value type as the
|
|
<tt>DistanceMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
|
|
the <tt>i_map</tt> for the index map.
|
|
</blockquote>
|
|
|
|
UTIL/OUT: <tt>color_map(ColorMap c_map)</tt>
|
|
<blockquote>
|
|
|
|
This is used during the execution of non-tree versions of the algorithm to
|
|
mark the
|
|
vertices, indicating whether they are on the OPEN or CLOSED lists.
|
|
The vertices start out white and become gray when they are inserted
|
|
into the OPEN list. They then turn black when they are examined and
|
|
placed on the CLOSED list. At the end of the algorithm, vertices
|
|
reachable from the source vertex will have been colored black. All
|
|
other vertices will still be white. The type <tt>ColorMap</tt> must
|
|
be a model of <a
|
|
href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write
|
|
Property Map</tt></a>. A vertex descriptor must be usable as the
|
|
key type of the map, and the value type of the map must be a model
|
|
of <a href="./ColorValue.html"><tt>Color Value</tt></a>.<br>
|
|
|
|
<b>Default:</b> <tt>shared_array_property_map</tt>
|
|
of value type <tt>default_color_type</tt>, with size
|
|
<tt>num_vertices(g)</tt>, and using
|
|
the <tt>i_map</tt> for the index map.
|
|
</blockquote>
|
|
|
|
IN: <tt>distance_compare(CompareFunction cmp)</tt>
|
|
<blockquote>
|
|
|
|
This function is use to compare distances to determine which vertex
|
|
is closer to the start vertex, and to compare <i>f</i>-values to
|
|
determine which vertex on the OPEN list to examine next. The
|
|
<tt>CompareFunction</tt> type must be a model of <a
|
|
href="http://www.boost.org/sgi/stl/BinaryPredicate.html"><tt>Binary
|
|
Predicate</tt></a> and have argument types that match the value type
|
|
of the <tt>DistanceMap</tt> property map.<br>
|
|
|
|
<b>Default:</b> <tt>std::less<D></tt> with <tt>D = typename
|
|
property_traits<DistanceMap>::value_type</tt>.
|
|
</blockquote>
|
|
|
|
IN: <tt>distance_combine(CombineFunction cmb)</tt>
|
|
<blockquote>
|
|
|
|
This function is used to combine distances to compute the distance
|
|
of a path, and to combine distance and heuristic values to compute
|
|
the <i>f</i>-value of a vertex. The <tt>CombineFunction</tt> type
|
|
must be a model of <a
|
|
href="http://www.boost.org/sgi/stl/BinaryFunction.html"><tt>Binary
|
|
Function</tt></a>. Both argument types of the binary function must
|
|
match the value type of the <tt>DistanceMap</tt> property map (which
|
|
is the same as that of the <tt>WeightMap</tt> and <tt>CostMap</tt>
|
|
property maps). The result type must be the same type as the
|
|
distance value type.<br>
|
|
|
|
<b>Default:</b> <tt>std::plus<D></tt> with <tt>D = typename
|
|
property_traits<DistanceMap>::value_type</tt>.
|
|
</blockquote>
|
|
|
|
IN: <tt>distance_inf(D inf)</tt>
|
|
<blockquote>
|
|
|
|
The <tt>inf</tt> object must be the greatest value of any <tt>D</tt>
|
|
object. That is, <tt>compare(d, inf) == true</tt> for any <tt>d !=
|
|
inf</tt>. The type <tt>D</tt> is the value type of the
|
|
<tt>DistanceMap</tt>.<br>
|
|
|
|
<b>Default:</b> <tt>std::numeric_limits<D>::max()</tt>
|
|
</blockquote>
|
|
|
|
IN: <tt>distance_zero(D zero)</tt>
|
|
<blockquote>
|
|
|
|
The <tt>zero</tt> value must be the identity element for the <a
|
|
href="./Monoid.html"><tt>Monoid</tt></a> formed by the distance
|
|
values and the <tt>combine</tt> function object. The type
|
|
<tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
|
|
|
|
<b>Default</b>: <tt>D()</tt> with <tt>D = typename
|
|
property_traits<DistanceMap>::value_type</tt>.
|
|
</blockquote>
|
|
|
|
OUT: <tt>visitor(AStarVisitor v)</tt>
|
|
<blockquote>
|
|
|
|
Use this to specify actions that you would like to happen during
|
|
certain event points within the algorithm. The type
|
|
<tt>AStarVisitor</tt> must be a model of the <a
|
|
href="AStarVisitor.html"><tt>AStarVisitor</tt></a> concept. The
|
|
visitor object is passed by value <a href="#1">[1]</a>.<br>
|
|
|
|
<b>Default:</b> <tt>astar_visitor<null_visitor></tt>
|
|
</blockquote>
|
|
|
|
<H3>Complexity</H3>
|
|
|
|
<P>
|
|
The time complexity is <i>O((E + V) log V)</i>.
|
|
|
|
<h3>Visitor Event Points</h3>
|
|
|
|
<ul>
|
|
<li><b><tt>vis.initialize_vertex(u, g)</tt></b>
|
|
is invoked on each vertex in the graph before the start of the
|
|
algorithm.
|
|
<li><b><tt>vis.discover_vertex(v, g)</tt></b>
|
|
is invoked when a vertex is first discovered and is added to the
|
|
OPEN list.
|
|
<li><b><tt>vis.examine_vertex(u, g)</tt></b>
|
|
is invoked when a vertex is popped from
|
|
the queue (i.e., it has the lowest cost on the OPEN list).
|
|
<li><b><tt>vis.examine_edge(e, g)</tt></b>
|
|
is invoked on each out-edge of a vertex immediately after it is
|
|
examined.
|
|
<li><b><tt>vis.edge_relaxed(e, g)</tt></b>
|
|
is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) < d[v]</i>.
|
|
<li><b><tt>vis.edge_not_relaxed(e, g)</tt></b>
|
|
is invoked if the edge is not relaxed (see above).
|
|
<li><b><tt>vis.black_target(e, g)</tt></b>
|
|
is invoked when a vertex that is on the CLOSED list is
|
|
"rediscovered" via a more efficient path, and is re-added to the
|
|
OPEN list.
|
|
<li><b><tt>vis.finish_vertex(u, g)</tt></b>
|
|
is invoked on a vertex when it is added to the CLOSED list, which
|
|
happens after all of its out edges have been examined.
|
|
</ul>
|
|
|
|
<H3>Example</H3>
|
|
|
|
<P>
|
|
See <a href="../example/astar-cities.cpp">
|
|
<TT>example/astar-cities.cpp</TT></a> for an example of
|
|
using A* search.
|
|
|
|
<H3>Notes</H3>
|
|
|
|
<a name="1">[1]</a> Since the visitor parameter is passed by value, if
|
|
your visitor contains state then any changes to the state during the
|
|
algorithm will be made to a copy of the visitor object, not the
|
|
visitor object passed in. Therefore you may want the visitor to hold
|
|
this state by pointer or reference.
|
|
|
|
<br>
|
|
<HR>
|
|
<TABLE>
|
|
<TR valign=top>
|
|
<TD nowrap>Copyright © 2004</TD><TD>
|
|
<A HREF="http://cs.krisbeevers.com/">Kristopher Beevers</A>,
|
|
Rensselaer Polytechnic Institute (<A
|
|
HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|