Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/astar_search.html @ 14

Last change on this file since 14 was 12, checked in by landauf, 18 years ago

added boost
File size: 17.4 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) 2004 Kris Beevers
4  --
5  -- Permission to use, copy, modify, distribute and sell this software
6  -- and its documentation for any purpose is hereby granted without fee,
7  -- provided that the above copyright notice appears in all copies and
8  -- that both that copyright notice and this permission notice appear
9  -- in supporting documentation.  We make no
10  -- representations about the suitability of this software for any
11  -- purpose.  It is provided "as is" without express or implied warranty.
12  -->
13<Head>
14<Title>Boost Graph Library: A* Heuristic Search</Title>
15<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
16        ALINK="#ff0000"> 
17<IMG SRC="../../../boost.png" 
18     ALT="C++ Boost" width="277" height="86"> 
19
20<BR Clear>
21
22<H1><A NAME="sec:astar"></A>
23<TT>astar_search</TT>
24</H1>
25
26
27<P>
28<PRE>
29<i>// Named parameter interface</i>
30template &lt;typename VertexListGraph,
31          typename AStarHeuristic,
32          typename P, typename T, typename R&gt;
33void
34astar_search
35  (VertexListGraph &amp;g,
36   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
37   <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
38
39<i>// Non-named parameter interface</i>
40template &lt;typename VertexListGraph, typename AStarHeuristic,
41          typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
42          typename CostMap, typename DistanceMap,
43          typename WeightMap, typename VertexIndexMap,
44          typename ColorMap,
45          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>,
46          typename CostInf, typename CostZero&gt;
47inline void
48astar_search
49  (VertexListGraph &amp;g,
50   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
51   AStarHeuristic h, AStarVisitor vis,
52   PredecessorMap predecessor, CostMap cost,
53   DistanceMap distance, WeightMap weight,
54   VertexIndexMap index_map, ColorMap color,
55   CompareFunction compare, CombineFunction combine,
56   CostInf inf, CostZero zero);
57</PRE>
58
59<P>
60This algorithm implements a heuristic search on a weighted, directed
61or undirected graph for the case where all edge weights are
62non-negative.
63</P>
64
65<P>
66The A* algorithm is a <i>heuristic graph search algorithm</i>: an A*
67search is "guided" by a <i>heuristic function</i>.  A heuristic
68function <i>h(v)</i> is one which estimates the cost from a non-goal
69state (<i>v</i>) in the graph to some goal state, <i>g</i>.
70Intuitively, A* follows paths (through the graph) to the goal that are
71estimated by the heuristic function to be the best paths.  Unlike
72best-first search, A* takes into account the known cost from the start
73of the search to <i>v</i>; the paths A* takes are guided by a function
74<i>f(v) = g(v) + h(v)</i>, where <i>h(v)</i> is the heuristic
75function, and <i>g(v)</i> (sometimes denoted <i>c(s, v)</i>) is the
76known cost from the start to <i>v</i>.  Clearly, the efficiency of A*
77is highly dependent on the heuristic function with which it is used.
78</P>
79
80<P>
81The A* algorithm is very similar to Dijkstra's Shortest Paths
82algorithm.  This implementation finds all the shortest paths from the
83start vertex to every other vertex by creating a search tree,
84examining vertices according to their remaining cost to some goal, as
85estimated by a heuristic function.  Most commonly, A* is used to find
86some specific goal vertex or vertices in a graph, after which the
87search is terminated.
88</P>
89
90<P>
91A* is particularly useful for searching <i>implicit</i> graphs.
92Implicit graphs are graphs that are not completely known at the
93beginning of the search.  Upon visiting a vertex, its neighbors are
94"generated" and added to the search.  Implicit graphs are particularly
95useful for searching large state spaces -- in gameplaying scenarios
96(e.g. chess), for example -- in which it may not be possible to store
97the entire graph.  Implicit searches can be performed with this
98implementation of A* by creating special visitors that generate
99neighbors of newly-expanded vertices.
100</P>
101
102<P>
103This implementation of A* is based on an OPEN/CLOSED list formulation
104of the algorithm.  Vertices on the OPEN list have been ``discovered''
105by the algorithm, but not ``expanded'' (we have not discovered their
106adjacent vertices).  Vertices on the CLOSED list have been completely
107examined by our search (we have expanded them and added their children
108to the OPEN list).  Vertices that are on neither list have not been
109encountered in any context so far in our search.  A major advantage of
110this formulation of the A* algorithm over other approaches is that it
111avoids ``cycles'' in the state space; the search will not become
112trapped by loops in the graph.  The OPEN/CLOSED lists are implemented
113using BGL's vertex coloring mechanisms.  Vertices in OPEN are colored
114gray, vertices in CLOSED are colored black, and undiscovered vertices
115are colored white.
116</P>
117
118<P>
119The criteria for expanding a vertex on the OPEN list is that it has
120the lowest <i>f(v) = g(v) + h(v)</i> value of all vertices on OPEN.
121Cost information about vertices is stored in a property map.
122</P>
123
124<P>
125The following is the pseudocode for the A* heuristic search algorithm.
126In the pseudocode, <i>h</i> is the heuristic function, <i>w</i> is the
127edge weight, <i>d</i> is the distance of a vertex from <i>s</i>, and
128<i>Q</i> is a priority queue, sorted by <i>f</i>, the estimated cost
129to the goal of the path through a vertex.  <i>p</i> is a predecessor
130map.  The visitor event points for the algorithm are indicated by the
131labels on the right.
132</P>
133
134<table>
135<tr>
136<td valign="top">
137<pre>
138A*(<i>G</i>, <i>s</i>, <i>h</i>)
139  <b>for</b> each vertex <i>u in V</i>
140    <i>d[u] := f[u] := infinity</i>
141    <i>color[u] :=</i> WHITE
142    <i>p[u] := u</i>
143  <b>end for</b>
144  <i>color[s] :=</i> GRAY
145  <i>d[s] := 0</i>
146  <i>f[s] := h(s)</i>
147  INSERT(<i>Q, s</i>)
148  <b>while</b> (<i>Q != &Oslash;</i>)
149    <i>u :=</i> EXTRACT-MIN(<i>Q</i>)
150    <b>for</b> each vertex <i>v in Adj[u]</i>
151      <b>if</b> (<i>w(u,v) + d[u] &lt; d[v]</i>)
152        <i>d[v] := w(u,v) + d[u]</i>
153        <i>f[v] := d[v] + h(v)</i>
154        <i>p[v] := u</i>
155        <b>if</b> (<i>color[v] =</i> WHITE)
156          <i>color[v] :=</i> GRAY
157          INSERT(<i>Q, v</i>)
158        <b>else if</b> (<i>color[v] =</i> BLACK)
159          <i>color[v] :=</i> GRAY
160          INSERT(<i>Q, v</i>)
161        <b>end if</b>
162      <b>else</b>
163        <i>...</i>
164    <b>end for</b>
165    <i>color[u] :=</i> BLACK
166  <b>end while</b>
167</pre>
168</td>
169<td valign="top">
170<pre>
171
172initialize vertex <i>u</i>
173
174
175
176
177
178
179
180discover vertex <i>s</i>
181
182examine vertex <i>u</i>
183examine edge <i>(u,v)</i>
184
185edge <i>(u,v)</i> relaxed
186
187
188
189
190discover vertex <i>v</i>
191
192
193reopen vertex <i>v</i>
194
195
196edge <i>(u,v)</i> not relaxed
197
198finish vertex <i>u</i>
199</pre>
200</td>
201</tr>
202</table>
203
204<h3>Where Defined</h3>
205
206<a href="../../../boost/graph/astar_search.hpp"><tt>boost/graph/astar_search.hpp</tt></a>
207
208<h3>Parameters</h3>
209
210IN: <tt>VertexListGraph&amp; g</tt>
211<blockquote>
212  The graph object on which the algorithm will be applied.  The type
213  <tt>VertexListGraph</tt> must be a model of the <a
214  href="VertexListGraph.html">
215  Vertex List Graph</a> concept.
216</blockquote>
217
218IN: <tt>vertex_descriptor s</tt>
219<blockquote>
220  The start vertex for the search.  All distances will be calculated
221  from this vertex, and the shortest paths tree (recorded in the
222  predecessor map) will be rooted at this vertex.
223</blockquote>
224
225IN: <tt>AStarHeuristic h</tt>
226<blockquote>
227  The heuristic function that guides the search.  The type
228  <tt>AStarHeuristic</tt> must be a model of the <a href="AStarHeuristic.html">AStarHeuristic</a>
229  concept.
230</blockquote>
231
232<h3>Named Parameters</h3>
233
234IN: <tt>weight_map(WeightMap w_map)</tt>
235<blockquote>
236   The weight or ``length'' of each edge in the graph.  The weights
237   must all be non-negative; the algorithm will throw a <a
238   href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
239   exception if one of the edges is negative.  The type
240   <tt>WeightMap</tt> must be a model of <a
241   href="../../property_map/ReadablePropertyMap.html"><tt>Readable
242   Property Map</tt></a>.  The edge descriptor type of the graph needs
243   to be usable as the key type for the weight map.  The value type
244   for this map must be the same as the value type of the distance
245   map.<br>
246   <b>Default:</b> <tt>get(edge\_weight, g)</tt>
247</blockquote>
248
249IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
250<blockquote>
251  This maps each vertex to an integer in the range <tt>[0,
252  num_vertices(g))</tt>.  This is necessary for efficient updates of
253  the heap data structure when an edge is relaxed.  The type
254  <tt>VertexIndexMap</tt> must be a model of <a
255  href="../../property_map/ReadablePropertyMap.html"><tt>Readable
256  Property Map</tt></a>.  The value type of the map must be an integer
257  type.  The vertex descriptor type of the graph needs to be usable as
258  the key type of the map.<br>
259
260  <b>Default:</b> <tt>get(vertex_index, g)</tt>
261</blockquote>
262
263OUT: <tt>predecessor_map(PredecessorMap p_map)</tt>
264<blockquote>
265
266  The predecessor map records the edges in the minimum spanning tree.
267  Upon completion of the algorithm, the edges <tt>(p[u],u)</tt> for
268  all <tt>u</tt> in <tt>V</tt> are in the minimum spanning tree.  If
269  <tt>p[u] = u</tt> then <tt>u</tt> is either the start vertex or a
270  vertex that is not reachable from the start.  The
271  <tt>PredecessorMap</tt> type must be a <a
272  href="../../property_map/ReadWritePropertyMap.html"><tt>Read/Write
273  Property Map</tt></a> with key and vertex types the same as the
274  vertex descriptor type of the graph.<br>
275
276  <b>Default:</b> <tt>dummy_property_map</tt>
277</blockquote>
278
279UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt>
280<blockquote>
281
282  The shortest path weight from the start vertex <tt>s</tt> to each
283  vertex in the graph <tt>g</tt> is recorded in this property map.
284  The shortest path weight is the sum of the edge weights along the
285  shortest path.  The type <tt>DistanceMap</tt> must be a model of <a
286  href="../../property_map/ReadWritePropertyMap.html"><tt>Read/Write
287  Property Map</tt></a>.  The vertex descriptor type of the graph
288  needs to be usable as the key type of the distance map.  The value
289  type of the distance map is the element type of a <a
290  href="./Monoid.html"><tt>Monoid</tt></a> formed with the
291  <tt>combine</tt> function object and the zero object for the
292  identity element.  Also the distance value type must have a <a
293  href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
294  provided by the <tt>compare</tt> function object.<br>
295
296  <b>Default:</b> <tt>iterator_property_map</tt> created from a
297  <tt>std::vector</tt> with the same value type as the
298  <tt>WeightMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
299  the <tt>i_map</tt> for the index map.
300</blockquote>
301
302UTIL/OUT: <tt>rank_map(CostMap c_map)</tt>
303<blockquote>
304
305  The <i>f</i>-value for each vertex.  The <i>f</i>-value is defined
306  as the sum of the cost to get to a vertex from the start vertex, and
307  the estimated cost (as returned by the heuristic function
308  <tt>h</tt>) from the vertex to a goal.  The type <tt>CostMap</tt>
309  must be a model of <a
310  href="../../property_map/ReadWritePropertyMap.html"><tt>Read/Write
311  Property Map</tt></a>.  The vertex descriptor type of the graph
312  needs to be usable as the key type of the distance map.  The value
313  type of the distance map is the element type of a <a
314  href="./Monoid.html"><tt>Monoid</tt></a> formed with the
315  <tt>combine</tt> function object and the zero object for the
316  identity element.  Also the distance value type must have a <a
317  href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
318  provided by the <tt>compare</tt> function object.  The value type
319  for this map must be the same as the value type for the distance
320  map.<br>
321
322  <b>Default:</b> <tt>iterator_property_map</tt> created from a
323  <tt>std::vector</tt> with the same value type as the
324  <tt>WeightMap</tt>, and of size <tt>num_vertices(g)</tt>, and using
325  the <tt>i_map</tt> for the index map.
326</blockquote>
327
328UTIL/OUT: <tt>color_map(ColorMap c_map)</tt>
329<blockquote>
330
331  This is used during the execution of the algorithm to mark the
332  vertices, indicating whether they are on the OPEN or CLOSED lists.
333  The vertices start out white and become gray when they are inserted
334  into the OPEN list.  They then turn black when they are examined and
335  placed on the CLOSED list.  At the end of the algorithm, vertices
336  reachable from the source vertex will have been colored black.  All
337  other vertices will still be white.  The type <tt>ColorMap</tt> must
338  be a model of <a
339  href="../../property_map/ReadWritePropertyMap.html"><tt>Read/Write
340  Property Map</tt></a>.  A vertex descriptor must be usable as the
341  key type of the map, and the value type of the map must be a model
342  of <a href="./ColorValue.html"><tt>Color Value</tt></a>.<br>
343
344  <b>Default:</b> <tt>iterator_property_map</tt> created from a
345  <tt>std::vector</tt> of value type <tt>default_color_type</tt>, with
346  size <tt>num_vertices(g)</tt>, and using the <tt>i_map</tt> for the
347  index map.
348</blockquote>
349
350IN: <tt>distance_compare(CompareFunction cmp)</tt>
351<blockquote>
352
353  This function is use to compare distances to determine which vertex
354  is closer to the start vertex, and to compare <i>f</i>-values to
355  determine which vertex on the OPEN list to examine next.  The
356  <tt>CompareFunction</tt> type must be a model of <a
357  href="http://www.sgi.com/tech/stl/BinaryPredicate.html"><tt>Binary
358  Predicate</tt></a> and have argument types that match the value type
359  of the <tt>DistanceMap</tt> property map.<br>
360
361  <b>Default:</b> <tt>std::less&lt;D&gt;</tt> with <tt>D = typename
362  property_traits&lt;DistanceMap&gt;::value_type</tt>.
363</blockquote>
364
365IN: <tt>distance_combine(CombineFunction cmb)</tt>
366<blockquote>
367
368  This function is used to combine distances to compute the distance
369  of a path, and to combine distance and heuristic values to compute
370  the <i>f</i>-value of a vertex.  The <tt>CombineFunction</tt> type
371  must be a model of <a
372  href="http://www.sgi.com/tech/stl/BinaryFunction.html"><tt>Binary
373  Function</tt></a>.  Both argument types of the binary function must
374  match the value type of the <tt>DistanceMap</tt> property map (which
375  is the same as that of the <tt>WeightMap</tt> and <tt>CostMap</tt>
376  property maps).  The result type must be the same type as the
377  distance value type.<br>
378
379  <b>Default:</b> <tt>std::plus&lt;D&gt;</tt> with <tt>D = typename
380  property_traits&lt;DistanceMap&gt;::value_type</tt>.
381</blockquote>
382
383IN: <tt>distance_inf(D inf)</tt>
384<blockquote>
385
386  The <tt>inf</tt> object must be the greatest value of any <tt>D</tt>
387  object.  That is, <tt>compare(d, inf) == true</tt> for any <tt>d !=
388  inf</tt>.  The type <tt>D</tt> is the value type of the
389  <tt>DistanceMap</tt>.<br>
390
391  <b>Default:</b> <tt>std::numeric_limits&lt;D&gt;::max()</tt>
392</blockquote>
393
394IN: <tt>distance_zero(D zero)</tt>
395<blockquote>
396
397  The <tt>zero</tt> value must be the identity element for the <a
398  href="./Monoid.html"><tt>Monoid</tt></a> formed by the distance
399  values and the <tt>combine</tt> function object.  The type
400  <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br>
401
402  <b>Default</b>: <tt>D()</tt> with <tt>D = typename
403  property_traits&lt;DistanceMap&gt;::value_type</tt>.
404</blockquote>
405
406OUT: <tt>visitor(AStarVisitor v)</tt>
407<blockquote>
408
409  Use this to specify actions that you would like to happen during
410  certain event points within the algorithm.  The type
411  <tt>AStarVisitor</tt> must be a model of the <a
412  href="AStarVisitor.html"><tt>AStarVisitor</tt></a> concept. The
413  visitor object is passed by value <a href="#1">[1]</a>.<br>
414
415  <b>Default:</b> <tt>astar_visitor&lt;null_visitor&gt;</tt>
416</blockquote>
417
418<H3>Complexity</H3>
419
420<P>
421The time complexity is <i>O((E + V) log V)</i>.
422
423<h3>Visitor Event Points</h3>
424
425<ul>
426<li><b><tt>vis.initialize_vertex(u, g)</tt></b>
427  is invoked on each vertex in the graph before the start of the
428  algorithm.
429<li><b><tt>vis.discover_vertex(v, g)</tt></b>
430  is invoked when a vertex is first discovered and is added to the
431  OPEN list.
432<li><b><tt>vis.examine_vertex(u, g)</tt></b>
433  is invoked when a vertex is popped from
434  the queue (i.e., it has the lowest cost on the OPEN list).
435<li><b><tt>vis.examine_edge(e, g)</tt></b>
436  is invoked on each out-edge of a vertex immediately after it is
437  examined.
438<li><b><tt>vis.edge_relaxed(e, g)</tt></b>
439  is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) < d[v]</i>.
440<li><b><tt>vis.edge_not_relaxed(e, g)</tt></b>
441  is invoked if the edge is not relaxed (see above).
442<li><b><tt>vis.black_target(u, g)</tt></b>
443   is invoked when a vertex that is on the CLOSED list is
444  "rediscovered" via a more efficient path, and is re-added to the
445  OPEN list.
446<li><b><tt>vis.finish_vertex(u, g)</tt></b>
447  is invoked on a vertex when it is added to the CLOSED list, which
448  happens after all of its out edges have been examined.
449</ul>
450
451<H3>Example</H3>
452
453<P>
454See <a href="../example/astar-cities.cpp">
455<TT>example/astar-cities.cpp</TT></a> for an example of
456using A* search.
457
458<H3>Notes</H3>
459
460<a name="1">[1]</a> Since the visitor parameter is passed by value, if
461your visitor contains state then any changes to the state during the
462algorithm will be made to a copy of the visitor object, not the
463visitor object passed in.  Therefore you may want the visitor to hold
464this state by pointer or reference.
465
466<br>
467<HR>
468<TABLE>
469<TR valign=top>
470<TD nowrap>Copyright &copy 2004</TD><TD>
471<A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>,
472Rensselaer Polytechnic Institute (<A
473HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
474</TD></TR></TABLE>
475
476</BODY>
477</HTML> 
Note: See TracBrowser for help on using the repository browser.