| <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.sgi.com/tech/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() |
| { |
| function_requires< 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://www.cs.rpi.edu/~beevek/">Kristopher Beevers</A>, |
| Rensselaer Polytechnic Institute (<A |
| HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>) |
| </TD></TR></TABLE> |
| |
| </BODY> |
| </HTML> |
