123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138 |
- <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: AStarHeuristic</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>AStar Heuristic Concept</H1>
- This concept defines the interface for the heuristic function of an A*
- search, which is responsible for estimating the remaining cost from
- some vertex to a goal. The user can create a class that matches this
- interface, and then pass objects of the class into <a
- href="./astar_search.html"><tt>astar_search()</tt></a> to guide the
- order of vertex examination of the search. The heuristic instance
- must incorporate any necessary information about goal vertices in the
- graph.
- For further discussion of the use of heuristics in an A* search, see
- the documentation of <a
- href="./astar_search.html">astar_search()</a>.
- <h3>Refinement of</h3>
- <a href="http://www.boost.org/sgi/stl/UnaryFunction.html">Unary
- Function</a> (must take a single argument -- a graph vertex -- and
- return a cost value) and <a
- href="../../utility/CopyConstructible.html">Copy Constructible</a>
- (copying a heuristic should be a lightweight operation).
- <h3>Notation</h3>
- <Table>
- <TR>
- <TD><tt>H</tt></TD>
- <TD>A type that is a model of AStar Heuristic.</TD>
- </TR>
- <TR>
- <TD><tt>h</tt></TD>
- <TD>An object of type <tt>H</tt>.</TD>
- </TR>
- <TR>
- <TD><tt>G</tt></TD>
- <TD>A type that is a model of Graph.</TD>
- </TR>
- <TR>
- <TD><tt>g</tt></TD>
- <TD>An object of type <tt>G</tt>.</TD>
- </TR>
- <TR>
- <TD><tt>u</tt></TD>
- <TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD>
- </TR>
- <TR>
- <TD><tt>CostType</tt></TD>
- <TD>A type that can be used with the <tt>compare</tt> and
- <tt>combine</tt> functions passed to A*.</TD>
- </TR>
- <TR>
- <TD><tt>c</tt></TD>
- <TD>An object of type <tt>CostType</tt>.</TD>
- </TR>
- </table>
- <h3>Associated Types</h3>
- none
- <p>
- <h3>Valid Expressions</h3>
- <table border>
- <tr>
- <th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th>
- </tr>
- <tr>
- <td>Call Heuristic</td>
- <td><tt>CostType c = h(u)</tt></td>
- <td><tt>CostType</tt></td>
- <td>
- Called for the target of every out edge of a vertex being examined.
- </td>
- </tr>
- </table>
- <h3>Models</h3>
- <ul>
- <li><a href="./astar_heuristic.html"><tt>astar_heuristic</tt></a>
- </ul>
- <h3>Concept Checking Class</h3>
- <pre>
- template <class Heuristic, class Graph>
- struct AStarHeuristicConcept {
- void constraints()
- {
- BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> ));
- h(u);
- }
- Heuristic h;
- typename graph_traits<Graph>::vertex_descriptor u;
- };
- </pre>
- <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>
|