boost_1_45_0/libs/graph/doc/astar_search.html - nest-learning-thermostat/5.0/boost - Git at Google

 <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>
	<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 VertexListGraph &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.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>
	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);

	<i>// Version that does 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.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>
	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>
	</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 != Ø</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 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<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.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<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://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>