<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 &lt;typename VertexListGraph,
          typename AStarHeuristic,
          typename P, typename T, typename R&gt;
void
astar_search
  (const VertexListGraph &amp;g,
   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
   <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);

template &lt;typename VertexListGraph,
          typename AStarHeuristic,
          typename P, typename T, typename R&gt;
void
astar_search_no_init
  (const VertexListGraph &amp;g,
   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
   <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);

<i>// Non-named parameter interface</i>
template &lt;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.sgi.com/tech/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">CombineFunction</a>,
          typename CostInf, typename CostZero&gt;
inline void
astar_search
  (const VertexListGraph &amp;g,
   typename graph_traits&lt;VertexListGraph&gt;::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);

<i>// Version that does not initialize property maps (used for implicit graphs)</i>
template &lt;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.sgi.com/tech/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.sgi.com/tech/stl/BinaryFunction.html">CombineFunction</a>,
          typename CostInf, typename CostZero&gt;
inline void
astar_search_no_init
  (const IncidenceGraph &amp;g,
   typename graph_traits&lt;IncidenceGraph&gt;::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>
</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> 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>
This implementation of A* is based on an OPEN/CLOSED list formulation
of the algorithm.  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.
</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 != &Oslash;</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] &lt; 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&amp; 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&amp; 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 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.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
  provided by the <tt>compare</tt> function object.<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>.  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.sgi.com/tech/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.<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 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.sgi.com/tech/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&lt;D&gt;</tt> with <tt>D = typename
  property_traits&lt;DistanceMap&gt;::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.sgi.com/tech/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&lt;D&gt;</tt> with <tt>D = typename
  property_traits&lt;DistanceMap&gt;::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&lt;D&gt;::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&lt;DistanceMap&gt;::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&lt;null_visitor&gt;</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) &lt; 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 &copy; 2004</TD><TD>
<A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>,
Rensselaer Polytechnic Institute (<A
HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
</TD></TR></TABLE>

</BODY>
</HTML>