<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>mrpt::graphs::CAStarAlgorithm Class Reference</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<div align="left"><a href="http://www.mrpt.org/">Main MRPT website</a> > <b>C++ reference</b> </div>
<div align="right">
<a href="index.html"><img border="0" src="mrpt_logo.png" alt="MRPT logo"></a>
</div>
<!-- Generated by Doxygen 1.7.5 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li class="current"><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li>
<div id="MSearchBox" class="MSearchBoxInactive">
<div class="left">
<form id="FSearchBox" action="search.php" method="get">
<img id="MSearchSelect" src="search/mag.png" alt=""/>
<input type="text" id="MSearchField" name="query" value="Search" size="20" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"/>
</form>
</div><div class="right"></div>
</div>
</li>
</ul>
</div>
<div id="navrow2" class="tabs2">
<ul class="tablist">
<li><a href="annotated.html"><span>Class List</span></a></li>
<li><a href="classes.html"><span>Class Index</span></a></li>
<li><a href="inherits.html"><span>Class Hierarchy</span></a></li>
<li><a href="functions.html"><span>Class Members</span></a></li>
</ul>
</div>
<div id="nav-path" class="navpath">
<ul>
<li class="navelem"><a class="el" href="namespacemrpt.html">mrpt</a> </li>
<li class="navelem"><a class="el" href="namespacemrpt_1_1graphs.html">graphs</a> </li>
<li class="navelem"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html">CAStarAlgorithm</a> </li>
</ul>
</div>
</div>
<div class="header">
<div class="summary">
<a href="#pub-methods">Public Member Functions</a> |
<a href="#pri-methods">Private Member Functions</a> </div>
<div class="headertitle">
<div class="title">mrpt::graphs::CAStarAlgorithm Class Reference<div class="ingroups"><a class="el" href="group__mrpt__graphs__grp.html">[mrpt-graphs]</a></div></div> </div>
</div>
<div class="contents">
<!-- doxytag: class="mrpt::graphs::CAStarAlgorithm" --><hr/><a name="details" id="details"></a><h2>Detailed Description</h2>
<div class="textblock"><p>This class is intended to efficiently solve graph-search problems using heuristics to determine the best path. </p>
<p>To use it, a solution class must be defined so that it contains all the information about any partial or complete solution. Then, a class inheriting from CAStarAlgorithm<Solution class> must also be implemented, overriding five virtual methods which define the behaviour of the solutions. These methods are isSolutionEnded, isSolutionValid, generateChildren, getHeuristic and getCost. Once both classes are generated, each object of the class inheriting from <a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html" title="This class is intended to efficiently solve graph-search problems using heuristics to determine the b...">CAStarAlgorithm</a> represents a problem who can be solved by calling getOptimalSolution. See <a href="http://en.wikipedia.org/wiki/A">http://en.wikipedia.org/wiki/A</a>*_search_algorithm for details about how this algorithm works. </p>
<dl class="see"><dt><b>See also:</b></dt><dd><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a3cacbb941191dc5cbaf0effb443b91f4" title="Client code must implement this method.">CAStarAlgorithm::isSolutionEnded</a> </dd>
<dd>
<a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#ab6067bc6a713333fb507b18ce67ba81a" title="Client code must implement this method.">CAStarAlgorithm::isSolutionValid</a> </dd>
<dd>
<a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a31eba07eb05f33881575c5839a506dcf" title="Client code must implement this method.">CAStarAlgorithm::generateChildren</a> </dd>
<dd>
<a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a8958d2e9de1aa8f944edaafb662ab940" title="Client code must implement this method.">CAStarAlgorithm::getHeuristic</a> </dd>
<dd>
<a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a86474ca549124ada5fbe44884697952c" title="Client code must implement this method.">CAStarAlgorithm::getCost</a> </dd></dl>
</div>
<p><code>#include <<a class="el" href="_c_a_star_algorithm_8h_source.html">mrpt/graphs/CAStarAlgorithm.h</a>></code></p>
<p><a href="classmrpt_1_1graphs_1_1_c_a_star_algorithm-members.html">List of all members.</a></p>
<table class="memberdecls">
<tr><td colspan="2"><h2><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">virtual bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a3cacbb941191dc5cbaf0effb443b91f4">isSolutionEnded</a> (const T &sol)=0</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Client code must implement this method. <a href="#a3cacbb941191dc5cbaf0effb443b91f4"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">virtual bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#ab6067bc6a713333fb507b18ce67ba81a">isSolutionValid</a> (const T &sol)=0</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Client code must implement this method. <a href="#ab6067bc6a713333fb507b18ce67ba81a"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">virtual void </td><td class="memItemRight" valign="bottom"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a31eba07eb05f33881575c5839a506dcf">generateChildren</a> (const T &sol, <a class="el" href="classstd_1_1vector.html">std::vector</a>< T > &sols)=0</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Client code must implement this method. <a href="#a31eba07eb05f33881575c5839a506dcf"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">virtual double </td><td class="memItemRight" valign="bottom"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a8958d2e9de1aa8f944edaafb662ab940">getHeuristic</a> (const T &sol)=0</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Client code must implement this method. <a href="#a8958d2e9de1aa8f944edaafb662ab940"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">virtual double </td><td class="memItemRight" valign="bottom"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a86474ca549124ada5fbe44884697952c">getCost</a> (const T &sol)=0</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Client code must implement this method. <a href="#a86474ca549124ada5fbe44884697952c"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a490443150b04e71cb1466b92b6c16d24">getOptimalSolution</a> (const T &initialSol, T &finalSol, double upperLevel=HUGE_VAL, double maxComputationTime=HUGE_VAL)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Finds the optimal solution for a problem, using the A* algorithm. <a href="#a490443150b04e71cb1466b92b6c16d24"></a><br/></td></tr>
<tr><td colspan="2"><h2><a name="pri-methods"></a>
Private Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">double </td><td class="memItemRight" valign="bottom"><a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#aec123ec3e5afc6cad29736385c4c7c7a">getTotalCost</a> (const T &sol)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Calculates the total cost (known+estimated) of a solution. <a href="#aec123ec3e5afc6cad29736385c4c7c7a"></a><br/></td></tr>
</table>
<hr/><h2>Member Function Documentation</h2>
<a class="anchor" id="a31eba07eb05f33881575c5839a506dcf"></a><!-- doxytag: member="mrpt::graphs::CAStarAlgorithm::generateChildren" ref="a31eba07eb05f33881575c5839a506dcf" args="(const T &sol, std::vector< T > &sols)=0" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">virtual void mrpt::graphs::CAStarAlgorithm::generateChildren </td>
<td>(</td>
<td class="paramtype">const T & </td>
<td class="paramname"><em>sol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classstd_1_1vector.html">std::vector</a>< T > & </td>
<td class="paramname"><em>sols</em> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [pure virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Client code must implement this method. </p>
<p>Given a partial solution, returns all its children solution, regardless of their validity or completeness. </p>
<p>Referenced by <a class="el" href="_c_a_star_algorithm_8h_source.html#l00093">getOptimalSolution()</a>.</p>
</div>
</div>
<a class="anchor" id="a86474ca549124ada5fbe44884697952c"></a><!-- doxytag: member="mrpt::graphs::CAStarAlgorithm::getCost" ref="a86474ca549124ada5fbe44884697952c" args="(const T &sol)=0" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">virtual double mrpt::graphs::CAStarAlgorithm::getCost </td>
<td>(</td>
<td class="paramtype">const T & </td>
<td class="paramname"><em>sol</em></td><td>)</td>
<td><code> [pure virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Client code must implement this method. </p>
<p>Given a (possibly partial) solution, calculates its cost so far. This cost must not decrease with each step. That is, a solution cannot have a smaller cost than the previous one from which it was generated. </p>
<p>Referenced by <a class="el" href="_c_a_star_algorithm_8h_source.html#l00085">getTotalCost()</a>.</p>
</div>
</div>
<a class="anchor" id="a8958d2e9de1aa8f944edaafb662ab940"></a><!-- doxytag: member="mrpt::graphs::CAStarAlgorithm::getHeuristic" ref="a8958d2e9de1aa8f944edaafb662ab940" args="(const T &sol)=0" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">virtual double mrpt::graphs::CAStarAlgorithm::getHeuristic </td>
<td>(</td>
<td class="paramtype">const T & </td>
<td class="paramname"><em>sol</em></td><td>)</td>
<td><code> [pure virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Client code must implement this method. </p>
<p>Given a partial solution, estimates the cost of the remaining (unknown) part. This cost must always be greater or equal to zero, and not greater than the actual cost. Thus, must be 0 if the solution is complete. </p>
<p>Referenced by <a class="el" href="_c_a_star_algorithm_8h_source.html#l00085">getTotalCost()</a>.</p>
</div>
</div>
<a class="anchor" id="a490443150b04e71cb1466b92b6c16d24"></a><!-- doxytag: member="mrpt::graphs::CAStarAlgorithm::getOptimalSolution" ref="a490443150b04e71cb1466b92b6c16d24" args="(const T &initialSol, T &finalSol, double upperLevel=HUGE_VAL, double maxComputationTime=HUGE_VAL)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">int mrpt::graphs::CAStarAlgorithm::getOptimalSolution </td>
<td>(</td>
<td class="paramtype">const T & </td>
<td class="paramname"><em>initialSol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">T & </td>
<td class="paramname"><em>finalSol</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">double </td>
<td class="paramname"><em>upperLevel</em> = <code>HUGE_VAL</code>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">double </td>
<td class="paramname"><em>maxComputationTime</em> = <code>HUGE_VAL</code> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td><code> [inline]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Finds the optimal solution for a problem, using the A* algorithm. </p>
<p>Returns whether an optimal solution was actually found. Returns 0 if no solution was found, 1 if an optimal solution was found and 2 if a (possibly suboptimal) solution was found but the time lapse ended. </p>
<p>Definition at line <a class="el" href="_c_a_star_algorithm_8h_source.html#l00093">93</a> of file <a class="el" href="_c_a_star_algorithm_8h_source.html">CAStarAlgorithm.h</a>.</p>
<p>References <a class="el" href="classmrpt_1_1utils_1_1_c_tic_tac.html#aae7e29d8fc37e441960004c6ffe31e81">mrpt::utils::CTicTac::Tic()</a>, <a class="el" href="_c_a_star_algorithm_8h_source.html#l00085">getTotalCost()</a>, <a class="el" href="classmrpt_1_1utils_1_1_c_tic_tac.html#a7eef1a30d6fa540ef116cb978db7aed8">mrpt::utils::CTicTac::Tac()</a>, <a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a3cacbb941191dc5cbaf0effb443b91f4">isSolutionEnded()</a>, <a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a31eba07eb05f33881575c5839a506dcf">generateChildren()</a>, and <a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#ab6067bc6a713333fb507b18ce67ba81a">isSolutionValid()</a>.</p>
</div>
</div>
<a class="anchor" id="aec123ec3e5afc6cad29736385c4c7c7a"></a><!-- doxytag: member="mrpt::graphs::CAStarAlgorithm::getTotalCost" ref="aec123ec3e5afc6cad29736385c4c7c7a" args="(const T &sol)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">double mrpt::graphs::CAStarAlgorithm::getTotalCost </td>
<td>(</td>
<td class="paramtype">const T & </td>
<td class="paramname"><em>sol</em></td><td>)</td>
<td><code> [inline, private]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Calculates the total cost (known+estimated) of a solution. </p>
<p>Definition at line <a class="el" href="_c_a_star_algorithm_8h_source.html#l00085">85</a> of file <a class="el" href="_c_a_star_algorithm_8h_source.html">CAStarAlgorithm.h</a>.</p>
<p>References <a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a8958d2e9de1aa8f944edaafb662ab940">getHeuristic()</a>, and <a class="el" href="classmrpt_1_1graphs_1_1_c_a_star_algorithm.html#a86474ca549124ada5fbe44884697952c">getCost()</a>.</p>
<p>Referenced by <a class="el" href="_c_a_star_algorithm_8h_source.html#l00093">getOptimalSolution()</a>.</p>
</div>
</div>
<a class="anchor" id="a3cacbb941191dc5cbaf0effb443b91f4"></a><!-- doxytag: member="mrpt::graphs::CAStarAlgorithm::isSolutionEnded" ref="a3cacbb941191dc5cbaf0effb443b91f4" args="(const T &sol)=0" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">virtual bool mrpt::graphs::CAStarAlgorithm::isSolutionEnded </td>
<td>(</td>
<td class="paramtype">const T & </td>
<td class="paramname"><em>sol</em></td><td>)</td>
<td><code> [pure virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Client code must implement this method. </p>
<p>Returns true if the given solution is complete. </p>
<p>Referenced by <a class="el" href="_c_a_star_algorithm_8h_source.html#l00093">getOptimalSolution()</a>.</p>
</div>
</div>
<a class="anchor" id="ab6067bc6a713333fb507b18ce67ba81a"></a><!-- doxytag: member="mrpt::graphs::CAStarAlgorithm::isSolutionValid" ref="ab6067bc6a713333fb507b18ce67ba81a" args="(const T &sol)=0" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">virtual bool mrpt::graphs::CAStarAlgorithm::isSolutionValid </td>
<td>(</td>
<td class="paramtype">const T & </td>
<td class="paramname"><em>sol</em></td><td>)</td>
<td><code> [pure virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Client code must implement this method. </p>
<p>Returns true if the given solution is acceptable, that is, doesn't violate the problem logic. </p>
<p>Referenced by <a class="el" href="_c_a_star_algorithm_8h_source.html#l00093">getOptimalSolution()</a>.</p>
</div>
</div>
</div>
<br><hr><br> <table border="0" width="100%"> <tr> <td> Page generated by <a href="http://www.doxygen.org" target="_blank">Doxygen 1.7.5</a> for MRPT 0.9.5 SVN: at Sun Sep 25 17:20:18 UTC 2011</td><td></td> <td width="100"> </td> <td width="150"> </td></tr> </table> </body></html>
