| <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> |