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: AStarHeuristic</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>AStar Heuristic Concept</H1> 19 20This concept defines the interface for the heuristic function of an A* 21search, which is responsible for estimating the remaining cost from 22some vertex to a goal. The user can create a class that matches this 23interface, and then pass objects of the class into <a 24href="./astar_search.html"><tt>astar_search()</tt></a> to guide the 25order of vertex examination of the search. The heuristic instance 26must incorporate any necessary information about goal vertices in the 27graph. 28 29For further discussion of the use of heuristics in an A* search, see 30the documentation of <a 31href="./astar_search.html">astar_search()</a>. 32 33<h3>Refinement of</h3> 34 35<a href="http://www.boost.org/sgi/stl/UnaryFunction.html">Unary 36Function</a> (must take a single argument -- a graph vertex -- and 37return a cost value) and <a 38href="../../utility/CopyConstructible.html">Copy Constructible</a> 39(copying a heuristic should be a lightweight operation). 40 41 42<h3>Notation</h3> 43 44<Table> 45<TR> 46<TD><tt>H</tt></TD> 47<TD>A type that is a model of AStar Heuristic.</TD> 48</TR> 49 50<TR> 51<TD><tt>h</tt></TD> 52<TD>An object of type <tt>H</tt>.</TD> 53</TR> 54 55<TR> 56<TD><tt>G</tt></TD> 57<TD>A type that is a model of Graph.</TD> 58</TR> 59 60<TR> 61<TD><tt>g</tt></TD> 62<TD>An object of type <tt>G</tt>.</TD> 63</TR> 64 65<TR> 66<TD><tt>u</tt></TD> 67<TD>An object of type <tt>boost::graph_traits<G>::vertex_descriptor</tt>.</TD> 68</TR> 69 70<TR> 71<TD><tt>CostType</tt></TD> 72<TD>A type that can be used with the <tt>compare</tt> and 73<tt>combine</tt> functions passed to A*.</TD> 74</TR> 75 76<TR> 77<TD><tt>c</tt></TD> 78<TD>An object of type <tt>CostType</tt>.</TD> 79</TR> 80 81</table> 82 83<h3>Associated Types</h3> 84 85none 86<p> 87 88<h3>Valid Expressions</h3> 89 90<table border> 91<tr> 92<th>Name</th><th>Expression</th><th>Return Type</th><th>Description</th> 93</tr> 94 95<tr> 96<td>Call Heuristic</td> 97<td><tt>CostType c = h(u)</tt></td> 98<td><tt>CostType</tt></td> 99<td> 100Called for the target of every out edge of a vertex being examined. 101</td> 102</tr> 103 104</table> 105 106<h3>Models</h3> 107 108<ul> 109 <li><a href="./astar_heuristic.html"><tt>astar_heuristic</tt></a> 110</ul> 111 112<h3>Concept Checking Class</h3> 113 114<pre> 115 template <class Heuristic, class Graph> 116 struct AStarHeuristicConcept { 117 void constraints() 118 { 119 BOOST_CONCEPT_ASSERT(( CopyConstructibleConcept<Heuristic> )); 120 h(u); 121 } 122 Heuristic h; 123 typename graph_traits<Graph>::vertex_descriptor u; 124 }; 125</pre> 126 127<br> 128<HR> 129<TABLE> 130<TR valign=top> 131<TD nowrap>Copyright © 2004</TD><TD> 132<A HREF="http://cs.krisbeevers.com/">Kristopher Beevers</A>, 133Rensselaer Polytechnic Institute (<A 134HREF="mailto:beevek@cs.rpi.edu">beevek@cs.rpi.edu</A>) 135</TD></TR></TABLE> 136 137</BODY> 138</HTML> 139
