Main MRPT website > C++ reference for MRPT 1.4.0
CAStarAlgorithm.h
Go to the documentation of this file.
1/* +---------------------------------------------------------------------------+
2 | Mobile Robot Programming Toolkit (MRPT) |
3 | http://www.mrpt.org/ |
4 | |
5 | Copyright (c) 2005-2016, Individual contributors, see AUTHORS file |
6 | See: http://www.mrpt.org/Authors - All rights reserved. |
7 | Released under BSD License. See details in http://www.mrpt.org/License |
8 +---------------------------------------------------------------------------+ */
9#ifndef CASTARALGORITHM_H
10#define CASTARALGORITHM_H
11#include <map>
12#include <vector>
13#define _USE_MATH_DEFINES // (For VS to define M_PI, etc. in cmath)
14#include <cmath>
15#include <mrpt/utils/CTicTac.h>
16
17namespace mrpt
18{
19 namespace graphs
20 {
21 /** This class is intended to efficiently solve graph-search problems using heuristics to determine the best path. To use it, a solution class must be defined
22 * so that it contains all the information about any partial or complete solution. Then, a class inheriting from CAStarAlgorithm<Solution class> must also be
23 * implemented, overriding five virtual methods which define the behaviour of the solutions. These methods are isSolutionEnded, isSolutionValid,
24 * generateChildren, getHeuristic and getCost.
25 * Once both classes are generated, each object of the class inheriting from CAStarAlgorithm represents a problem who can be solved by calling
26 * getOptimalSolution. See http://en.wikipedia.org/wiki/A*_search_algorithm for details about how this algorithm works.
27 * \sa CAStarAlgorithm::isSolutionEnded
28 * \sa CAStarAlgorithm::isSolutionValid
29 * \sa CAStarAlgorithm::generateChildren
30 * \sa CAStarAlgorithm::getHeuristic
31 * \sa CAStarAlgorithm::getCost
32 * \ingroup mrpt_graphs_grp
33 */
34 template<typename T> class CAStarAlgorithm {
35 public:
36 /**
37 * Client code must implement this method.
38 * Returns true if the given solution is complete.
39 */
40 virtual bool isSolutionEnded(const T &sol)=0;
41 /**
42 * Client code must implement this method.
43 * Returns true if the given solution is acceptable, that is, doesn't violate the problem logic.
44 */
45 virtual bool isSolutionValid(const T &sol)=0;
46 /**
47 * Client code must implement this method.
48 * Given a partial solution, returns all its children solution, regardless of their validity or completeness.
49 */
50 virtual void generateChildren(const T &sol,std::vector<T> &sols)=0;
51 /**
52 * Client code must implement this method.
53 * Given a partial solution, estimates the cost of the remaining (unknown) part.
54 * 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.
55 */
56 virtual double getHeuristic(const T &sol)=0;
57 /**
58 * Client code must implement this method.
59 * Given a (possibly partial) solution, calculates its cost so far.
60 * 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.
61 */
62 virtual double getCost(const T &sol)=0;
63 private:
64 /**
65 * Calculates the total cost (known+estimated) of a solution.
66 */
67 inline double getTotalCost(const T &sol) {
68 return getHeuristic(sol)+getCost(sol);
69 }
70 public:
71 /**
72 * Finds the optimal solution for a problem, using the A* algorithm. Returns whether an optimal solution was actually found.
73 * 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.
74 */
75 int getOptimalSolution(const T &initialSol,T &finalSol,double upperLevel=HUGE_VAL,double maxComputationTime=HUGE_VAL) {
76 //Time measuring object is defined.
78 time.Tic();
79 //The partial solution set is initialized with a single element (the starting solution).
80 std::multimap<double,T> partialSols;
81 partialSols.insert(std::pair<double,T>(getTotalCost(initialSol),initialSol));
82 //The best known solution is set to the upper bound (positive infinite, if there is no given parameter).
83 double currentOptimal=upperLevel;
84 bool found=false;
85 std::vector<T> children;
86 //Main loop. Each iteration checks an element of the set, with minimum estimated cost.
87 while (!partialSols.empty()) {
88 //Return if elapsed time has been reached.
89 if (time.Tac()>=maxComputationTime) return found?2:0;
90 typename std::multimap<double,T>::iterator it=partialSols.begin();
91 double tempCost=it->first;
92 //If the minimum estimated cost is higher than the upper bound, then also is every solution in the set. So the algorithm returns immediately.
93 if (tempCost>=currentOptimal) return found?1:0;
94 T tempSol=it->second;
95 partialSols.erase(it);
96 //At this point, the solution cost is lesser than the upper bound. So, if the solution is complete, the optimal solution and the upper bound are updated.
97 if (isSolutionEnded(tempSol)) {
98 currentOptimal=tempCost;
99 finalSol=tempSol;
100 found=true;
101 continue;
102 }
103 //If the solution is not complete, check for its children. Each one is included in the set only if it's valid and it's not yet present in the set.
104 generateChildren(tempSol,children);
105 for (typename std::vector<T>::const_iterator it2=children.begin();it2!=children.end();++it2) if (isSolutionValid(*it2)) {
106 bool alreadyPresent=false;
107 double cost=getTotalCost(*it2);
108 typename std::pair<typename std::multimap<double,T>::const_iterator,typename std::multimap<double,T>::const_iterator> range = partialSols.equal_range(cost);
109 for (typename std::multimap<double,T>::const_iterator it3=range.first;it3!=range.second;++it3) if (it3->second==*it2) {
110 alreadyPresent=true;
111 break;
112 }
113 if (!alreadyPresent) partialSols.insert(std::pair<double,T>(getTotalCost(*it2),*it2));
114 }
115 }
116 //No more solutions to explore...
117 return found?1:0;
118 }
119 };
120 }
121} //End of namespaces
122#endif
This class is intended to efficiently solve graph-search problems using heuristics to determine the b...
double getTotalCost(const T &sol)
Calculates the total cost (known+estimated) of a solution.
virtual bool isSolutionEnded(const T &sol)=0
Client code must implement this method.
virtual void generateChildren(const T &sol, std::vector< T > &sols)=0
Client code must implement this method.
virtual bool isSolutionValid(const T &sol)=0
Client code must implement this method.
int getOptimalSolution(const T &initialSol, T &finalSol, double upperLevel=HUGE_VAL, double maxComputationTime=HUGE_VAL)
Finds the optimal solution for a problem, using the A* algorithm.
virtual double getCost(const T &sol)=0
Client code must implement this method.
virtual double getHeuristic(const T &sol)=0
Client code must implement this method.
This class implements a high-performance stopwatch.
Definition: CTicTac.h:25
double Tac()
Stops the stopwatch.
void Tic()
Starts the stopwatch.
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.



Page generated by Doxygen 1.9.6 for MRPT 1.4.0 SVN: at Wed Mar 22 08:20:48 UTC 2023