]>
Commit | Line | Data |
---|---|---|
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 interfaces</i> | |
26 | template <typename VertexListGraph, | |
27 | typename AStarHeuristic, | |
28 | typename P, typename T, typename R> | |
29 | void | |
30 | astar_search | |
31 | (const VertexListGraph &g, | |
32 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
33 | <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params); | |
34 | ||
35 | template <typename VertexListGraph, | |
36 | typename AStarHeuristic, | |
37 | typename P, typename T, typename R> | |
38 | void | |
39 | astar_search_no_init | |
40 | (const IncidenceGraph &g, | |
41 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
42 | <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params); | |
43 | ||
44 | template <typename VertexListGraph, | |
45 | typename AStarHeuristic, | |
46 | typename P, typename T, typename R> | |
47 | void | |
48 | astar_search_tree | |
49 | (const VertexListGraph &g, | |
50 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
51 | <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params); | |
52 | ||
53 | template <typename VertexListGraph, | |
54 | typename AStarHeuristic, | |
55 | typename P, typename T, typename R> | |
56 | void | |
57 | astar_search_no_init_tree | |
58 | (const IncidenceGraph &g, | |
59 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
60 | <a href="AStarHeuristic.html">AStarHeuristic</a> h, const bgl_named_params<P, T, R>& params); | |
61 | ||
62 | <i>// Non-named parameter interface</i> | |
63 | template <typename VertexListGraph, typename AStarHeuristic, | |
64 | typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap, | |
65 | typename CostMap, typename DistanceMap, | |
66 | typename WeightMap, typename VertexIndexMap, | |
67 | typename ColorMap, | |
68 | 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>, | |
69 | typename CostInf, typename CostZero> | |
70 | inline void | |
71 | astar_search | |
72 | (const VertexListGraph &g, | |
73 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
74 | AStarHeuristic h, AStarVisitor vis, | |
75 | PredecessorMap predecessor, CostMap cost, | |
76 | DistanceMap distance, WeightMap weight, | |
77 | VertexIndexMap index_map, ColorMap color, | |
78 | CompareFunction compare, CombineFunction combine, | |
79 | CostInf inf, CostZero zero); | |
80 | ||
81 | template <typename VertexListGraph, typename AStarHeuristic, | |
82 | typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap, | |
83 | typename CostMap, typename DistanceMap, | |
84 | typename WeightMap, | |
85 | 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>, | |
86 | typename CostInf, typename CostZero> | |
87 | inline void | |
88 | astar_search_tree | |
89 | (const VertexListGraph &g, | |
90 | typename graph_traits<VertexListGraph>::vertex_descriptor s, | |
91 | AStarHeuristic h, AStarVisitor vis, | |
92 | PredecessorMap predecessor, CostMap cost, | |
93 | DistanceMap distance, WeightMap weight, | |
94 | CompareFunction compare, CombineFunction combine, | |
95 | CostInf inf, CostZero zero); | |
96 | ||
97 | <i>// Versions that do not initialize property maps (used for implicit graphs)</i> | |
98 | template <typename IncidenceGraph, typename AStarHeuristic, | |
99 | typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap, | |
100 | typename CostMap, typename DistanceMap, | |
101 | typename WeightMap, typename ColorMap, | |
102 | typename VertexIndexMap, | |
103 | 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>, | |
104 | typename CostInf, typename CostZero> | |
105 | inline void | |
106 | astar_search_no_init | |
107 | (const IncidenceGraph &g, | |
108 | typename graph_traits<IncidenceGraph>::vertex_descriptor s, | |
109 | AStarHeuristic h, AStarVisitor vis, | |
110 | PredecessorMap predecessor, CostMap cost, | |
111 | DistanceMap distance, WeightMap weight, | |
112 | ColorMap color, VertexIndexMap index_map, | |
113 | CompareFunction compare, CombineFunction combine, | |
114 | CostInf inf, CostZero zero); | |
115 | ||
116 | <b>Note that the index_map and color parameters are swapped in | |
117 | astar_search_no_init() relative to astar_search(); the named parameter | |
118 | interfaces are not affected.</b> | |
119 | ||
120 | template <typename IncidenceGraph, typename AStarHeuristic, | |
121 | typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap, | |
122 | typename CostMap, typename DistanceMap, | |
123 | typename WeightMap, | |
124 | 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>, | |
125 | typename CostInf, typename CostZero> | |
126 | inline void | |
127 | astar_search_no_init_tree | |
128 | (const IncidenceGraph &g, | |
129 | typename graph_traits<IncidenceGraph>::vertex_descriptor s, | |
130 | AStarHeuristic h, AStarVisitor vis, | |
131 | PredecessorMap predecessor, CostMap cost, | |
132 | DistanceMap distance, WeightMap weight, | |
133 | CompareFunction compare, CombineFunction combine, | |
134 | CostInf inf, CostZero zero); | |
135 | </PRE> | |
136 | ||
137 | <P> | |
138 | This algorithm implements a heuristic search on a weighted, directed | |
139 | or undirected graph for the case where all edge weights are | |
140 | non-negative. | |
141 | </P> | |
142 | ||
143 | <P> | |
144 | The A* algorithm is a <i>heuristic graph search algorithm</i>: an A* | |
145 | search is "guided" by a <i>heuristic function</i>. A heuristic | |
146 | function <i>h(v)</i> is one which estimates the cost from a non-goal | |
147 | state (<i>v</i>) in the graph to some goal state, <i>g</i>. | |
148 | Intuitively, A* follows paths (through the graph) to the goal that are | |
149 | estimated by the heuristic function to be the best paths. Unlike | |
150 | best-first search, A* takes into account the known cost from the start | |
151 | of the search to <i>v</i>; the paths A* takes are guided by a function | |
152 | <i>f(v) = g(v) + h(v)</i>, where <i>h(v)</i> is the heuristic | |
153 | function, and <i>g(v)</i> (sometimes denoted <i>c(s, v)</i>) is the | |
154 | known cost from the start to <i>v</i>. Clearly, the efficiency of A* | |
155 | is highly dependent on the heuristic function with which it is used. | |
156 | </P> | |
157 | ||
158 | <P> | |
159 | The A* algorithm is very similar to Dijkstra's Shortest Paths | |
160 | algorithm. This implementation finds all the shortest paths from the | |
161 | start vertex to every other vertex by creating a search tree, | |
162 | examining vertices according to their remaining cost to some goal, as | |
163 | estimated by a heuristic function. Most commonly, A* is used to find | |
164 | some specific goal vertex or vertices in a graph, after which the | |
165 | search is terminated. | |
166 | </P> | |
167 | ||
168 | <P> | |
169 | A* is particularly useful for searching <i>implicit</i> graphs. | |
170 | Implicit graphs are graphs that are not completely known at the | |
171 | beginning of the search. Upon visiting a vertex, its neighbors are | |
172 | "generated" and added to the search. Implicit graphs are particularly | |
173 | useful for searching large state spaces -- in game-playing scenarios | |
174 | (e.g. chess), for example -- in which it may not be possible to store | |
175 | the entire graph. Implicit searches can be performed with this | |
176 | implementation of A* by creating special visitors that generate | |
177 | neighbors of newly-expanded vertices. Please note that | |
178 | <tt>astar_search_no_init()</tt> or <tt>astar_search_no_init_tree()</tt> must be | |
179 | used for implicit graphs; the basic | |
180 | <tt>astar_search()</tt> function requires a graph that models | |
181 | the <a href="VertexListGraph.html">Vertex List Graph</a> concept. Both | |
182 | versions | |
183 | also require the graph type to model the <a | |
184 | href="IncidenceGraph.html">Incidence Graph</a> concept. | |
185 | </P> | |
186 | ||
187 | <P> | |
188 | For the non-tree versions of the algorithm, | |
189 | this implementation of A* is based on an OPEN/CLOSED list formulation. | |
190 | Vertices on the OPEN list have been ``discovered'' | |
191 | by the algorithm, but not ``expanded'' (we have not discovered their | |
192 | adjacent vertices). Vertices on the CLOSED list have been completely | |
193 | examined by our search (we have expanded them and added their children | |
194 | to the OPEN list). Vertices that are on neither list have not been | |
195 | encountered in any context so far in our search. A major advantage of | |
196 | this formulation of the A* algorithm over other approaches is that it | |
197 | avoids ``cycles'' in the state space; the search will not become | |
198 | trapped by loops in the graph. The OPEN/CLOSED lists are implemented | |
199 | using BGL's vertex coloring mechanisms. Vertices in OPEN are colored | |
200 | gray, vertices in CLOSED are colored black, and undiscovered vertices | |
201 | are colored white. For the versions of the algorithm whose names end in | |
202 | <tt>_tree</tt>, all vertices are assumed to always be white, leading to | |
203 | checking for repeated vertices being done using the distance map. If a dummy | |
204 | value is used for the distance map and the graph contains cycles, the algorithm | |
205 | will probably enter an infinite loop. | |
206 | </P> | |
207 | ||
208 | <P> | |
209 | The criteria for expanding a vertex on the OPEN list is that it has | |
210 | the lowest <i>f(v) = g(v) + h(v)</i> value of all vertices on OPEN. | |
211 | Cost information about vertices is stored in a property map. | |
212 | </P> | |
213 | ||
214 | <P> | |
215 | The following is the pseudocode for the A* heuristic search algorithm. | |
216 | In the pseudocode, <i>h</i> is the heuristic function, <i>w</i> is the | |
217 | edge weight, <i>d</i> is the distance of a vertex from <i>s</i>, and | |
218 | <i>Q</i> is a priority queue, sorted by <i>f</i>, the estimated cost | |
219 | to the goal of the path through a vertex. <i>p</i> is a predecessor | |
220 | map. The visitor event points for the algorithm are indicated by the | |
221 | labels on the right. | |
222 | </P> | |
223 | ||
224 | <table> | |
225 | <tr> | |
226 | <td valign="top"> | |
227 | <pre> | |
228 | A*(<i>G</i>, <i>s</i>, <i>h</i>) | |
229 | <b>for</b> each vertex <i>u in V</i> | |
230 | <i>d[u] := f[u] := infinity</i> | |
231 | <i>color[u] :=</i> WHITE | |
232 | <i>p[u] := u</i> | |
233 | <b>end for</b> | |
234 | <i>color[s] :=</i> GRAY | |
235 | <i>d[s] := 0</i> | |
236 | <i>f[s] := h(s)</i> | |
237 | INSERT(<i>Q, s</i>) | |
238 | <b>while</b> (<i>Q != Ø</i>) | |
239 | <i>u :=</i> EXTRACT-MIN(<i>Q</i>) | |
240 | <b>for</b> each vertex <i>v in Adj[u]</i> | |
241 | <b>if</b> (<i>w(u,v) + d[u] < d[v]</i>) | |
242 | <i>d[v] := w(u,v) + d[u]</i> | |
243 | <i>f[v] := d[v] + h(v)</i> | |
244 | <i>p[v] := u</i> | |
245 | <b>if</b> (<i>color[v] =</i> WHITE) | |
246 | <i>color[v] :=</i> GRAY | |
247 | INSERT(<i>Q, v</i>) | |
248 | <b>else if</b> (<i>color[v] =</i> BLACK) | |
249 | <i>color[v] :=</i> GRAY | |
250 | INSERT(<i>Q, v</i>) | |
251 | <b>end if</b> | |
252 | <b>else</b> | |
253 | <i>...</i> | |
254 | <b>end for</b> | |
255 | <i>color[u] :=</i> BLACK | |
256 | <b>end while</b> | |
257 | </pre> | |
258 | </td> | |
259 | <td valign="top"> | |
260 | <pre> | |
261 | ||
262 | initialize vertex <i>u</i> | |
263 | ||
264 | ||
265 | ||
266 | ||
267 | ||
268 | ||
269 | ||
270 | discover vertex <i>s</i> | |
271 | ||
272 | examine vertex <i>u</i> | |
273 | examine edge <i>(u,v)</i> | |
274 | ||
275 | edge <i>(u,v)</i> relaxed | |
276 | ||
277 | ||
278 | ||
279 | ||
280 | discover vertex <i>v</i> | |
281 | ||
282 | ||
283 | reopen vertex <i>v</i> | |
284 | ||
285 | ||
286 | edge <i>(u,v)</i> not relaxed | |
287 | ||
288 | finish vertex <i>u</i> | |
289 | </pre> | |
290 | </td> | |
291 | </tr> | |
292 | </table> | |
293 | ||
294 | <h3>Where Defined</h3> | |
295 | ||
296 | <a href="../../../boost/graph/astar_search.hpp"><tt>boost/graph/astar_search.hpp</tt></a> | |
297 | ||
298 | <h3>Parameters</h3> | |
299 | ||
300 | IN: <tt>const VertexListGraph& g</tt> | |
301 | <blockquote> | |
302 | The graph object on which the algorithm will be applied for <tt>astar_search()</tt>. The type | |
303 | <tt>VertexListGraph</tt> must be a model of the <a | |
304 | href="VertexListGraph.html"> | |
305 | Vertex List Graph</a> and <a href="IncidenceGraph.html">Incidence Graph</a> | |
306 | concepts. | |
307 | </blockquote> | |
308 | ||
309 | IN: <tt>const IncidenceGraph& g</tt> | |
310 | <blockquote> | |
311 | The graph object on which the algorithm will be applied for <tt>astar_search_no_init()</tt>. The type | |
312 | <tt>IncidenceGraph</tt> must be a model of the | |
313 | <a href="IncidenceGraph.html">Incidence Graph</a> | |
314 | concept. | |
315 | </blockquote> | |
316 | ||
317 | IN: <tt>vertex_descriptor s</tt> | |
318 | <blockquote> | |
319 | The start vertex for the search. All distances will be calculated | |
320 | from this vertex, and the shortest paths tree (recorded in the | |
321 | predecessor map) will be rooted at this vertex. | |
322 | </blockquote> | |
323 | ||
324 | IN: <tt>AStarHeuristic h</tt> | |
325 | <blockquote> | |
326 | The heuristic function that guides the search. The type | |
327 | <tt>AStarHeuristic</tt> must be a model of the <a href="AStarHeuristic.html">AStarHeuristic</a> | |
328 | concept. | |
329 | </blockquote> | |
330 | ||
331 | <h3>Named Parameters</h3> | |
332 | ||
333 | IN: <tt>weight_map(WeightMap w_map)</tt> | |
334 | <blockquote> | |
335 | The weight or ``length'' of each edge in the graph. The weights | |
336 | must all be non-negative; the algorithm will throw a <a | |
337 | href="./exception.html#negative_edge"><tt>negative_edge</tt></a> | |
338 | exception if one of the edges is negative. The type | |
339 | <tt>WeightMap</tt> must be a model of <a | |
340 | href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable | |
341 | Property Map</tt></a>. The edge descriptor type of the graph needs | |
342 | to be usable as the key type for the weight map. The value type | |
343 | for this map must be the same as the value type of the distance | |
344 | map.<br> | |
345 | <b>Default:</b> <tt>get(edge\_weight, g)</tt> | |
346 | </blockquote> | |
347 | ||
348 | IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> | |
349 | <blockquote> | |
350 | This maps each vertex to an integer in the range <tt>[0, | |
351 | num_vertices(g))</tt>. This is necessary in non-tree versions of the | |
352 | algorithm for efficient updates of | |
353 | the heap data structure when an edge is relaxed. The type | |
354 | <tt>VertexIndexMap</tt> must be a model of <a | |
355 | href="../../property_map/doc/ReadablePropertyMap.html"><tt>Readable | |
356 | Property Map</tt></a>. The value type of the map must be an integer | |
357 | type. The vertex descriptor type of the graph needs to be usable as | |
358 | the key type of the map.<br> | |
359 | ||
360 | <b>Default:</b> <tt>get(vertex_index, g)</tt>. | |
361 | Note: if you use this default, make sure your graph has | |
362 | an internal <tt>vertex_index</tt> property. For example, | |
363 | <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does | |
364 | not have an internal <tt>vertex_index</tt> property. | |
365 | </blockquote> | |
366 | ||
367 | OUT: <tt>predecessor_map(PredecessorMap p_map)</tt> | |
368 | <blockquote> | |
369 | ||
370 | The predecessor map records the edges in the minimum spanning tree. | |
371 | Upon completion of the algorithm, the edges <tt>(p[u],u)</tt> for | |
372 | all <tt>u</tt> in <tt>V</tt> are in the minimum spanning tree. If | |
373 | <tt>p[u] = u</tt> then <tt>u</tt> is either the start vertex or a | |
374 | vertex that is not reachable from the start. The | |
375 | <tt>PredecessorMap</tt> type must be a <a | |
376 | href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write | |
377 | Property Map</tt></a> with key and vertex types the same as the | |
378 | vertex descriptor type of the graph.<br> | |
379 | ||
380 | <b>Default:</b> <tt>dummy_property_map</tt> | |
381 | </blockquote> | |
382 | ||
383 | UTIL/OUT: <tt>distance_map(DistanceMap d_map)</tt> | |
384 | <blockquote> | |
385 | ||
386 | The shortest path weight from the start vertex <tt>s</tt> to each | |
387 | vertex in the graph <tt>g</tt> is recorded in this property map. | |
388 | The shortest path weight is the sum of the edge weights along the | |
389 | shortest path. The type <tt>DistanceMap</tt> must be a model of <a | |
390 | href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write | |
391 | Property Map</tt></a>. The vertex descriptor type of the graph | |
392 | needs to be usable as the key type of the distance map. The value | |
393 | type of the distance map is the element type of a <a | |
394 | href="./Monoid.html"><tt>Monoid</tt></a> formed with the | |
395 | <tt>combine</tt> function object and the zero object for the | |
396 | identity element. Also the distance value type must have a <a | |
397 | href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a> | |
398 | provided by the <tt>compare</tt> function object. A | |
399 | <tt>constant_writable_property_map</tt> returning the infinity value can be | |
400 | used for this parameter in tree versions of the algorithm when the graph does | |
401 | not contain a directed cycle.<br> | |
402 | ||
403 | <b>Default:</b> <tt>shared_array_property_map</tt> | |
404 | with the same value type as the | |
405 | <tt>WeightMap</tt>, and of size <tt>num_vertices(g)</tt>, and using | |
406 | the <tt>i_map</tt> for the index map. | |
407 | </blockquote> | |
408 | ||
409 | UTIL/OUT: <tt>rank_map(CostMap c_map)</tt> | |
410 | <blockquote> | |
411 | ||
412 | The <i>f</i>-value for each vertex. The <i>f</i>-value is defined | |
413 | as the sum of the cost to get to a vertex from the start vertex, and | |
414 | the estimated cost (as returned by the heuristic function | |
415 | <tt>h</tt>) from the vertex to a goal. The type <tt>CostMap</tt> | |
416 | must be a model of <a | |
417 | href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write | |
418 | Property Map</tt></a> in non-tree versions of the algorithm, and <a | |
419 | href="../../property_map/doc/WritablePropertyMap.html"><tt>Writable Property | |
420 | Map</tt></a> in tree versions of the algorithm. The vertex descriptor type | |
421 | of the graph | |
422 | needs to be usable as the key type of the distance map. The value | |
423 | type of the distance map is the element type of a <a | |
424 | href="./Monoid.html"><tt>Monoid</tt></a> formed with the | |
425 | <tt>combine</tt> function object and the zero object for the | |
426 | identity element. Also the distance value type must have a <a | |
427 | href="http://www.sgi.com/tech/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a> | |
428 | provided by the <tt>compare</tt> function object. The value type | |
429 | for this map must be the same as the value type for the distance | |
430 | map. In tree versions of the algorithm, <tt>null_property_map</tt> can be | |
431 | used for this parameter.<br> | |
432 | ||
433 | <b>Default:</b> <tt>shared_array_property_map</tt> | |
434 | with the same value type as the | |
435 | <tt>DistanceMap</tt>, and of size <tt>num_vertices(g)</tt>, and using | |
436 | the <tt>i_map</tt> for the index map. | |
437 | </blockquote> | |
438 | ||
439 | UTIL/OUT: <tt>color_map(ColorMap c_map)</tt> | |
440 | <blockquote> | |
441 | ||
442 | This is used during the execution of non-tree versions of the algorithm to | |
443 | mark the | |
444 | vertices, indicating whether they are on the OPEN or CLOSED lists. | |
445 | The vertices start out white and become gray when they are inserted | |
446 | into the OPEN list. They then turn black when they are examined and | |
447 | placed on the CLOSED list. At the end of the algorithm, vertices | |
448 | reachable from the source vertex will have been colored black. All | |
449 | other vertices will still be white. The type <tt>ColorMap</tt> must | |
450 | be a model of <a | |
451 | href="../../property_map/doc/ReadWritePropertyMap.html"><tt>Read/Write | |
452 | Property Map</tt></a>. A vertex descriptor must be usable as the | |
453 | key type of the map, and the value type of the map must be a model | |
454 | of <a href="./ColorValue.html"><tt>Color Value</tt></a>.<br> | |
455 | ||
456 | <b>Default:</b> <tt>shared_array_property_map</tt> | |
457 | of value type <tt>default_color_type</tt>, with size | |
458 | <tt>num_vertices(g)</tt>, and using | |
459 | the <tt>i_map</tt> for the index map. | |
460 | </blockquote> | |
461 | ||
462 | IN: <tt>distance_compare(CompareFunction cmp)</tt> | |
463 | <blockquote> | |
464 | ||
465 | This function is use to compare distances to determine which vertex | |
466 | is closer to the start vertex, and to compare <i>f</i>-values to | |
467 | determine which vertex on the OPEN list to examine next. The | |
468 | <tt>CompareFunction</tt> type must be a model of <a | |
469 | href="http://www.sgi.com/tech/stl/BinaryPredicate.html"><tt>Binary | |
470 | Predicate</tt></a> and have argument types that match the value type | |
471 | of the <tt>DistanceMap</tt> property map.<br> | |
472 | ||
473 | <b>Default:</b> <tt>std::less<D></tt> with <tt>D = typename | |
474 | property_traits<DistanceMap>::value_type</tt>. | |
475 | </blockquote> | |
476 | ||
477 | IN: <tt>distance_combine(CombineFunction cmb)</tt> | |
478 | <blockquote> | |
479 | ||
480 | This function is used to combine distances to compute the distance | |
481 | of a path, and to combine distance and heuristic values to compute | |
482 | the <i>f</i>-value of a vertex. The <tt>CombineFunction</tt> type | |
483 | must be a model of <a | |
484 | href="http://www.sgi.com/tech/stl/BinaryFunction.html"><tt>Binary | |
485 | Function</tt></a>. Both argument types of the binary function must | |
486 | match the value type of the <tt>DistanceMap</tt> property map (which | |
487 | is the same as that of the <tt>WeightMap</tt> and <tt>CostMap</tt> | |
488 | property maps). The result type must be the same type as the | |
489 | distance value type.<br> | |
490 | ||
491 | <b>Default:</b> <tt>std::plus<D></tt> with <tt>D = typename | |
492 | property_traits<DistanceMap>::value_type</tt>. | |
493 | </blockquote> | |
494 | ||
495 | IN: <tt>distance_inf(D inf)</tt> | |
496 | <blockquote> | |
497 | ||
498 | The <tt>inf</tt> object must be the greatest value of any <tt>D</tt> | |
499 | object. That is, <tt>compare(d, inf) == true</tt> for any <tt>d != | |
500 | inf</tt>. The type <tt>D</tt> is the value type of the | |
501 | <tt>DistanceMap</tt>.<br> | |
502 | ||
503 | <b>Default:</b> <tt>std::numeric_limits<D>::max()</tt> | |
504 | </blockquote> | |
505 | ||
506 | IN: <tt>distance_zero(D zero)</tt> | |
507 | <blockquote> | |
508 | ||
509 | The <tt>zero</tt> value must be the identity element for the <a | |
510 | href="./Monoid.html"><tt>Monoid</tt></a> formed by the distance | |
511 | values and the <tt>combine</tt> function object. The type | |
512 | <tt>D</tt> is the value type of the <tt>DistanceMap</tt>.<br> | |
513 | ||
514 | <b>Default</b>: <tt>D()</tt> with <tt>D = typename | |
515 | property_traits<DistanceMap>::value_type</tt>. | |
516 | </blockquote> | |
517 | ||
518 | OUT: <tt>visitor(AStarVisitor v)</tt> | |
519 | <blockquote> | |
520 | ||
521 | Use this to specify actions that you would like to happen during | |
522 | certain event points within the algorithm. The type | |
523 | <tt>AStarVisitor</tt> must be a model of the <a | |
524 | href="AStarVisitor.html"><tt>AStarVisitor</tt></a> concept. The | |
525 | visitor object is passed by value <a href="#1">[1]</a>.<br> | |
526 | ||
527 | <b>Default:</b> <tt>astar_visitor<null_visitor></tt> | |
528 | </blockquote> | |
529 | ||
530 | <H3>Complexity</H3> | |
531 | ||
532 | <P> | |
533 | The time complexity is <i>O((E + V) log V)</i>. | |
534 | ||
535 | <h3>Visitor Event Points</h3> | |
536 | ||
537 | <ul> | |
538 | <li><b><tt>vis.initialize_vertex(u, g)</tt></b> | |
539 | is invoked on each vertex in the graph before the start of the | |
540 | algorithm. | |
541 | <li><b><tt>vis.discover_vertex(v, g)</tt></b> | |
542 | is invoked when a vertex is first discovered and is added to the | |
543 | OPEN list. | |
544 | <li><b><tt>vis.examine_vertex(u, g)</tt></b> | |
545 | is invoked when a vertex is popped from | |
546 | the queue (i.e., it has the lowest cost on the OPEN list). | |
547 | <li><b><tt>vis.examine_edge(e, g)</tt></b> | |
548 | is invoked on each out-edge of a vertex immediately after it is | |
549 | examined. | |
550 | <li><b><tt>vis.edge_relaxed(e, g)</tt></b> | |
551 | is invoked on edge <i>(u,v)</i> if <i>d[u] + w(u,v) < d[v]</i>. | |
552 | <li><b><tt>vis.edge_not_relaxed(e, g)</tt></b> | |
553 | is invoked if the edge is not relaxed (see above). | |
554 | <li><b><tt>vis.black_target(e, g)</tt></b> | |
555 | is invoked when a vertex that is on the CLOSED list is | |
556 | "rediscovered" via a more efficient path, and is re-added to the | |
557 | OPEN list. | |
558 | <li><b><tt>vis.finish_vertex(u, g)</tt></b> | |
559 | is invoked on a vertex when it is added to the CLOSED list, which | |
560 | happens after all of its out edges have been examined. | |
561 | </ul> | |
562 | ||
563 | <H3>Example</H3> | |
564 | ||
565 | <P> | |
566 | See <a href="../example/astar-cities.cpp"> | |
567 | <TT>example/astar-cities.cpp</TT></a> for an example of | |
568 | using A* search. | |
569 | ||
570 | <H3>Notes</H3> | |
571 | ||
572 | <a name="1">[1]</a> Since the visitor parameter is passed by value, if | |
573 | your visitor contains state then any changes to the state during the | |
574 | algorithm will be made to a copy of the visitor object, not the | |
575 | visitor object passed in. Therefore you may want the visitor to hold | |
576 | this state by pointer or reference. | |
577 | ||
578 | <br> | |
579 | <HR> | |
580 | <TABLE> | |
581 | <TR valign=top> | |
582 | <TD nowrap>Copyright © 2004</TD><TD> | |
583 | <A HREF="http://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>, | |
584 | Rensselaer Polytechnic Institute (<A | |
585 | HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>) | |
586 | </TD></TR></TABLE> | |
587 | ||
588 | </BODY> | |
589 | </HTML> |