Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/astar_search.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

updated boost from 1_33_1 to 1_34_1
File size: 17.3 KB
Line 
1<HTML>
2<!--
3  -- Copyright (c) 2004 Kris Beevers
4  --
5  -- Distributed under the Boost Software License, Version 1.0.
6  -- (See accompanying file LICENSE_1_0.txt or copy at
7  -- http://www.boost.org/LICENSE_1_0.txt)
8  -->
9<Head>
10<Title>Boost Graph Library: A* Heuristic Search</Title>
11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
12        ALINK="#ff0000"> 
13<IMG SRC="../../../boost.png" 
14     ALT="C++ Boost" width="277" height="86"> 
15
16<BR Clear>
17
18<H1><A NAME="sec:astar"></A>
19<TT>astar_search</TT>
20</H1>
21
22
23<P>
24<PRE>
25<i>// Named parameter interface</i>
26template &lt;typename VertexListGraph,
27          typename AStarHeuristic,
28          typename P, typename T, typename R&gt;
29void
30astar_search
31  (VertexListGraph &amp;g,
32   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
33   <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params&lt;P, T, R&gt;&amp; params);
34
35<i>// Non-named parameter interface</i>
36template &lt;typename VertexListGraph, typename AStarHeuristic,
37          typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
38          typename CostMap, typename DistanceMap,
39          typename WeightMap, typename VertexIndexMap,
40          typename ColorMap,
41          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>,
42          typename CostInf, typename CostZero&gt;
43inline void
44astar_search
45  (VertexListGraph &amp;g,
46   typename graph_traits&lt;VertexListGraph&gt;::vertex_descriptor s,
47   AStarHeuristic h, AStarVisitor vis,
48   PredecessorMap predecessor, CostMap cost,
49   DistanceMap distance, WeightMap weight,
50   VertexIndexMap index_map, ColorMap color,
51   CompareFunction compare, CombineFunction combine,
52   CostInf inf, CostZero zero);
53</PRE>
54
55<P>
56This algorithm implements a heuristic search on a weighted, directed
57or undirected graph for the case where all edge weights are
58non-negative.
59</P>
60
61<P>
62The A* algorithm is a <i>heuristic graph search algorithm</i>: an A*
63search is "guided" by a <i>heuristic function</i>.  A heuristic
64function <i>h(v)</i> is one which estimates the cost from a non-goal
65state (<i>v</i>) in the graph to some goal state, <i>g</i>.
66Intuitively, A* follows paths (through the graph) to the goal that are
67estimated by the heuristic function to be the best paths.  Unlike
68best-first search, A* takes into account the known cost from the start
69of the search to <i>v</i>; the paths A* takes are guided by a function
70<i>f(v) = g(v) + h(v)</i>, where <i>h(v)</i> is the heuristic
71function, and <i>g(v)</i> (sometimes denoted <i>c(s, v)</i>) is the
72known cost from the start to <i>v</i>.  Clearly, the efficiency of A*
73is highly dependent on the heuristic function with which it is used.
74</P>
75
76<P>
77The A* algorithm is very similar to Dijkstra's Shortest Paths
78algorithm.  This implementation finds all the shortest paths from the
79start vertex to every other vertex by creating a search tree,
80examining vertices according to their remaining cost to some goal, as
81estimated by a heuristic function.  Most commonly, A* is used to find
82some specific goal vertex or vertices in a graph, after which the
83search is terminated.
84</P>
85
86<P>
87A* is particularly useful for searching <i>implicit</i> graphs.
88Implicit graphs are graphs that are not completely known at the
89beginning of the search.  Upon visiting a vertex, its neighbors are
90"generated" and added to the search.  Implicit graphs are particularly
91useful for searching large state spaces -- in gameplaying scenarios
92(e.g. chess), for example -- in which it may not be possible to store
93the entire graph.  Implicit searches can be performed with this
94implementation of A* by creating special visitors that generate
95neighbors of newly-expanded vertices.
96</P>
97
98<P>
99This implementation of A* is based on an OPEN/CLOSED list formulation
100of the algorithm.  Vertices on the OPEN list have been ``discovered''
101by the algorithm, but not ``expanded'' (we have not discovered their
102adjacent vertices).  Vertices on the CLOSED list have been completely
103examined by our search (we have expanded them and added their children
104to the OPEN list).  Vertices that are on neither list have not been
105encountered in any context so far in our search.  A major advantage of
106this formulation of the A* algorithm over other approaches is that it
107avoids ``cycles'' in the state space; the search will not become
108trapped by loops in the graph.  The OPEN/CLOSED lists are implemented
109using BGL's vertex coloring mechanisms.  Vertices in OPEN are colored
110gray, vertices in CLOSED are colored black, and undiscovered vertices
111are colored white.
112</P>
113
114<P>
115The criteria for expanding a vertex on the OPEN list is that it has
116the lowest <i>f(v) = g(v) + h(v)</i> value of all vertices on OPEN.
117Cost information about vertices is stored in a property map.
118</P>
119
120<P>
121The following is the pseudocode for the A* heuristic search algorithm.
122In the pseudocode, <i>h</i> is the heuristic function, <i>w</i> is the
123edge weight, <i>d</i> is the distance of a vertex from <i>s</i>, and
124<i>Q</i> is a priority queue, sorted by <i>f</i>, the estimated cost
125to the goal of the path through a vertex.  <i>p</i> is a predecessor
126map.  The visitor event points for the algorithm are indicated by the
127labels on the right.
128</P>
129
130<table>
131<tr>
132<td valign="top">
133<pre>
134A*(<i>G</i>, <i>s</i>, <i>h</i>)
135  <b>for</b> each vertex <i>u in V</i>
136    <i>d[u] := f[u] := infinity</i>
137    <i>color[u] :=</i> WHITE
138    <i>p[u] := u</i>
139  <b>end for</b>
140  <i>color[s] :=</i> GRAY
141  <i>d[s] := 0</i>
142  <i>f[s] := h(s)</i>
143  INSERT(<i>Q, s</i>)
144  <b>while</b> (<i>Q != &Oslash;</i>)
145    <i>u :=</i> EXTRACT-MIN(<i>Q</i>)
146    <b>for</b> each vertex <i>v in Adj[u]</i>
147      <b>if</b> (<i>w(u,v) + d[u] &lt; d[v]</i>)
148        <i>d[v] := w(u,v) + d[u]</i>
149        <i>f[v] := d[v] + h(v)</i>
150        <i>p[v] := u</i>
151        <b>if</b> (<i>color[v] =</i> WHITE)
152          <i>color[v] :=</i> GRAY
153          INSERT(<i>Q, v</i>)
154        <b>else if</b> (<i>color[v] =</i> BLACK)
155          <i>color[v] :=</i> GRAY
156          INSERT(<i>Q, v</i>)
157        <b>end if</b>
158      <b>else</b>
159        <i>...</i>
160    <b>end for</b>
161    <i>color[u] :=</i> BLACK
162  <b>end while</b>
163</pre>
164</td>
165<td valign="top">
166<pre>
167
168initialize vertex <i>u</i>
169
170
171
172
173
174
175
176discover vertex <i>s</i>
177
178examine vertex <i>u</i>
179examine edge <i>(u,v)</i>
180
181edge <i>(u,v)</i> relaxed
182
183
184
185
186discover vertex <i>v</i>
187
188
189reopen vertex <i>v</i>
190
191
192edge <i>(u,v)</i> not relaxed
193
194finish vertex <i>u</i>
195</pre>
196</td>
197</tr>
198</table>
199
200<h3>Where Defined</h3>
201
202<a href="../../../boost/graph/astar_search.hpp"><tt>boost/graph/astar_search.hpp</tt></a>
203
204<h3>Parameters</h3>
205
206IN: <tt>VertexListGraph&amp; g</tt>
207<blockquote>
208  The graph object on which the algorithm will be applied.  The type
209  <tt>VertexListGraph</tt> must be a model of the <a
210  href="VertexListGraph.html">
211  Vertex List Graph</a> concept.
212</blockquote>
213
214IN: <tt>vertex_descriptor s</tt>
215<blockquote>
216  The start vertex for the search.  All distances will be calculated
217  from this vertex, and the shortest paths tree (recorded in the
218  predecessor map) will be rooted at this vertex.
219</blockquote>
220
221IN: <tt>AStarHeuristic h</tt>
222<blockquote>
223  The heuristic function that guides the search.  The type
224  <tt>AStarHeuristic</tt> must be a model of the <a href="AStarHeuristic.html">AStarHeuristic</a>
225  concept.
226</blockquote>
227
228<h3>Named Parameters</h3>
229
230IN: <tt>weight_map(WeightMap w_map)</tt>
231<blockquote>
232   The weight or ``length'' of each edge in the graph.  The weights
233   must all be non-negative; the algorithm will throw a <a
234   href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
235   exception if one of the edges is negative.  The type
236   <tt>WeightMap</tt> must be a model of <a
237   href="../../property_map/ReadablePropertyMap.html"><tt>Readable
238   Property Map</tt></a>.  The edge descriptor type of the graph needs
239   to be usable as the key type for the weight map.  The value type
240   for this map must be the same as the value type of the distance
241   map.<br>
242   <b>Default:</b> <tt>get(edge\_weight, g)</tt>
243</blockquote>
244
245IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt>
246<blockquote>
247  This maps each vertex to an integer in the range <tt>[0,
248  num_vertices(g))</tt>.  This is necessary for efficient updates of
249  the heap data structure when an edge is relaxed.  The type
250  <tt>VertexIndexMap</tt> must be a model of <a
251  href="../../property_map/ReadablePropertyMap.html"><tt>Readable
252  Property Map</tt></a>.  The value type of the map must be an integer
253  type.  The vertex descriptor type of the graph needs to be usable as
254  the key type of the map.<br>
255
256  <b>Default:</b> <tt>get(vertex_index, g)</tt>.
257   Note: if you use this default, make sure your graph has
258   an internal <tt>vertex_index</tt> property. For example,
259   <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does
260   not have an internal <tt>vertex_index</tt> property.
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.