123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589 |
- <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 IncidenceGraph &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_tree
- (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_tree
- (const IncidenceGraph &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.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/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);
- template <typename VertexListGraph, typename AStarHeuristic,
- typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
- typename CostMap, typename DistanceMap,
- typename WeightMap,
- typename <a href="http://www.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/stl/BinaryFunction.html">CombineFunction</a>,
- typename CostInf, typename CostZero>
- inline void
- astar_search_tree
- (const VertexListGraph &g,
- typename graph_traits<VertexListGraph>::vertex_descriptor s,
- AStarHeuristic h, AStarVisitor vis,
- PredecessorMap predecessor, CostMap cost,
- DistanceMap distance, WeightMap weight,
- CompareFunction compare, CombineFunction combine,
- CostInf inf, CostZero zero);
- <i>// Versions that do 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.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/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>
- template <typename IncidenceGraph, typename AStarHeuristic,
- typename <a href="AStarVisitor.html">AStarVisitor</a>, typename PredecessorMap,
- typename CostMap, typename DistanceMap,
- typename WeightMap,
- typename <a href="http://www.boost.org/sgi/stl/BinaryPredicate.html">CompareFunction</a>, typename <a href="http://www.boost.org/sgi/stl/BinaryFunction.html">CombineFunction</a>,
- typename CostInf, typename CostZero>
- inline void
- astar_search_no_init_tree
- (const IncidenceGraph &g,
- typename graph_traits<IncidenceGraph>::vertex_descriptor s,
- AStarHeuristic h, AStarVisitor vis,
- PredecessorMap predecessor, CostMap cost,
- DistanceMap distance, WeightMap weight,
- CompareFunction compare, CombineFunction combine,
- CostInf inf, CostZero zero);
- </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> or <tt>astar_search_no_init_tree()</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>
- For the non-tree versions of the algorithm,
- this implementation of A* is based on an OPEN/CLOSED list formulation.
- 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. For the versions of the algorithm whose names end in
- <tt>_tree</tt>, all vertices are assumed to always be white, leading to
- checking for repeated vertices being done using the distance map. If a dummy
- value is used for the distance map and the graph contains cycles, the algorithm
- will probably enter an infinite loop.
- </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 in non-tree versions of the
- algorithm 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.boost.org/sgi/stl/StrictWeakOrdering.html"><tt>StrictWeakOrdering</tt></a>
- provided by the <tt>compare</tt> function object. A
- <tt>constant_writable_property_map</tt> returning the infinity value can be
- used for this parameter in tree versions of the algorithm when the graph does
- not contain a directed cycle.<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> in non-tree versions of the algorithm, and <a
- href="../../property_map/doc/WritablePropertyMap.html"><tt>Writable Property
- Map</tt></a> in tree versions of the algorithm. 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.boost.org/sgi/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. In tree versions of the algorithm, <tt>null_property_map</tt> can be
- used for this parameter.<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 non-tree versions 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.boost.org/sgi/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.boost.org/sgi/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://cs.krisbeevers.com/">Kristopher Beevers</A>,
- Rensselaer Polytechnic Institute (<A
- HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|