...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

// Named parameter interfacetemplate <typename VertexListGraph, typename AStarHeuristic, typename P, typename T, typename R> void astar_search (VertexListGraph &g, typename graph_traits<VertexListGraph>::vertex_descriptor s, AStarHeuristic h, const bgl_named_params<P, T, R>& params);// Non-named parameter interfacetemplate <typename VertexListGraph, typename AStarHeuristic, typename AStarVisitor, typename PredecessorMap, typename CostMap, typename DistanceMap, typename WeightMap, typename VertexIndexMap, typename ColorMap, typename CompareFunction, typename CombineFunction, typename CostInf, typename CostZero> inline void astar_search (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);

This algorithm implements a heuristic search on a weighted, directed or undirected graph for the case where all edge weights are non-negative.

The A* algorithm is a *heuristic graph search algorithm*: an A*
search is "guided" by a *heuristic function*. A heuristic
function *h(v)* is one which estimates the cost from a non-goal
state (*v*) in the graph to some goal state, *g*.
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 *v*; the paths A* takes are guided by a function
*f(v) = g(v) + h(v)*, where *h(v)* is the heuristic
function, and *g(v)* (sometimes denoted *c(s, v)*) is the
known cost from the start to *v*. Clearly, the efficiency of A*
is highly dependent on the heuristic function with which it is used.

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.

A* is particularly useful for searching *implicit* 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 gameplaying 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.

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.

The criteria for expanding a vertex on the OPEN list is that it has
the lowest *f(v) = g(v) + h(v)* value of all vertices on OPEN.
Cost information about vertices is stored in a property map.

The following is the pseudocode for the A* heuristic search algorithm.
In the pseudocode, *h* is the heuristic function, *w* is the
edge weight, *d* is the distance of a vertex from *s*, and
*Q* is a priority queue, sorted by *f*, the estimated cost
to the goal of the path through a vertex. *p* is a predecessor
map. The visitor event points for the algorithm are indicated by the
labels on the right.

A*( |
initialize vertex |

The graph object on which the algorithm will be applied. The typeIN:VertexListGraphmust be a model of the Vertex List Graph concept.

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.IN:

The heuristic function that guides the search. The typeAStarHeuristicmust be a model of the AStarHeuristic concept.

The weight or ``length'' of each edge in the graph. The weights must all be non-negative; the algorithm will throw aIN:negative_edgeexception if one of the edges is negative. The typeWeightMapmust be a model ofReadable Property Map. 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.

Default:get(edge\_weight, g)

This maps each vertex to an integer in the rangeOUT:[0, num_vertices(g)). This is necessary for efficient updates of the heap data structure when an edge is relaxed. The typeVertexIndexMapmust be a model ofReadable Property Map. 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.

Default:get(vertex_index, g)

The predecessor map records the edges in the minimum spanning tree. Upon completion of the algorithm, the edgesUTIL/OUT:(p[u],u)for alluinVare in the minimum spanning tree. Ifp[u] = uthenuis either the start vertex or a vertex that is not reachable from the start. ThePredecessorMaptype must be aRead/Write Property Mapwith key and vertex types the same as the vertex descriptor type of the graph.

Default:dummy_property_map

The shortest path weight from the start vertexUTIL/OUT:sto each vertex in the graphgis recorded in this property map. The shortest path weight is the sum of the edge weights along the shortest path. The typeDistanceMapmust be a model ofRead/Write Property Map. 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 aMonoidformed with thecombinefunction object and the zero object for the identity element. Also the distance value type must have aStrictWeakOrderingprovided by thecomparefunction object.

Default:iterator_property_mapcreated from astd::vectorwith the same value type as theWeightMap, and of sizenum_vertices(g), and using thei_mapfor the index map.

TheUTIL/OUT:f-value for each vertex. Thef-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 functionh) from the vertex to a goal. The typeCostMapmust be a model ofRead/Write Property Map. 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 aMonoidformed with thecombinefunction object and the zero object for the identity element. Also the distance value type must have aStrictWeakOrderingprovided by thecomparefunction object. The value type for this map must be the same as the value type for the distance map.

Default:iterator_property_mapcreated from astd::vectorwith the same value type as theWeightMap, and of sizenum_vertices(g), and using thei_mapfor the index map.

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 typeIN:ColorMapmust be a model ofRead/Write Property Map. A vertex descriptor must be usable as the key type of the map, and the value type of the map must be a model ofColor Value.

Default:iterator_property_mapcreated from astd::vectorof value typedefault_color_type, with sizenum_vertices(g), and using thei_mapfor the index map.

This function is use to compare distances to determine which vertex is closer to the start vertex, and to compareIN:f-values to determine which vertex on the OPEN list to examine next. TheCompareFunctiontype must be a model ofBinary Predicateand have argument types that match the value type of theDistanceMapproperty map.

Default:std::less<D>withD = typename property_traits<DistanceMap>::value_type.

This function is used to combine distances to compute the distance of a path, and to combine distance and heuristic values to compute theIN:f-value of a vertex. TheCombineFunctiontype must be a model ofBinary Function. Both argument types of the binary function must match the value type of theDistanceMapproperty map (which is the same as that of theWeightMapandCostMapproperty maps). The result type must be the same type as the distance value type.

Default:std::plus<D>withD = typename property_traits<DistanceMap>::value_type.

TheIN:infobject must be the greatest value of anyDobject. That is,compare(d, inf) == truefor anyd != inf. The typeDis the value type of theDistanceMap.

Default:std::numeric_limits<D>::max()

TheOUT:zerovalue must be the identity element for theMonoidformed by the distance values and thecombinefunction object. The typeDis the value type of theDistanceMap.

Default:D()withD = typename property_traits<DistanceMap>::value_type.

Use this to specify actions that you would like to happen during certain event points within the algorithm. The typeAStarVisitormust be a model of theAStarVisitorconcept. The visitor object is passed by value [1].

Default:astar_visitor<null_visitor>

The time complexity is *O((E + V) log V)*.

is invoked on each vertex in the graph before the start of the algorithm.`vis.initialize_vertex(u, g)`is invoked when a vertex is first discovered and is added to the OPEN list.`vis.discover_vertex(v, g)`is invoked when a vertex is popped from the queue (i.e., it has the lowest cost on the OPEN list).`vis.examine_vertex(u, g)`is invoked on each out-edge of a vertex immediately after it is examined.`vis.examine_edge(e, g)`is invoked on edge`vis.edge_relaxed(e, g)`*(u,v)*if*d[u] + w(u,v) < d[v]*.is invoked if the edge is not relaxed (see above).`vis.edge_not_relaxed(e, g)`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.`vis.black_target(u, g)`is invoked on a vertex when it is added to the CLOSED list, which happens after all of its out edges have been examined.`vis.finish_vertex(u, g)`

See
`example/astar-cities.cpp` for an example of
using A* search.

Copyright © 2004 | Kristopher Beevers, Rensselaer Polytechnic Institute (beevek@cs.rpi.edu) |