1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
<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>
|
