Main MRPT website > C++ reference for MRPT 1.9.9
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-2017, 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 #include <cmath>
14 #include <mrpt/utils/CTicTac.h>
15 
16 namespace mrpt
17 {
18 namespace graphs
19 {
20 /** This class is intended to efficiently solve graph-search problems using
21  * heuristics to determine the best path. To use it, a solution class must be
22  * defined
23  * so that it contains all the information about any partial or complete
24  * solution. Then, a class inheriting from CAStarAlgorithm<Solution class> must
25  * also be
26  * implemented, overriding five virtual methods which define the behaviour of
27  * the solutions. These methods are isSolutionEnded, isSolutionValid,
28  * generateChildren, getHeuristic and getCost.
29  * Once both classes are generated, each object of the class inheriting from
30  * CAStarAlgorithm represents a problem who can be solved by calling
31  * getOptimalSolution. See http://en.wikipedia.org/wiki/A*_search_algorithm for
32  * details about how this algorithm works.
33  * \sa CAStarAlgorithm::isSolutionEnded
34  * \sa CAStarAlgorithm::isSolutionValid
35  * \sa CAStarAlgorithm::generateChildren
36  * \sa CAStarAlgorithm::getHeuristic
37  * \sa CAStarAlgorithm::getCost
38  * \ingroup mrpt_graphs_grp
39  */
40 template <typename T>
42 {
43  public:
44  /**
45  * Client code must implement this method.
46  * Returns true if the given solution is complete.
47  */
48  virtual bool isSolutionEnded(const T& sol) = 0;
49  /**
50  * Client code must implement this method.
51  * Returns true if the given solution is acceptable, that is, doesn't
52  * violate the problem logic.
53  */
54  virtual bool isSolutionValid(const T& sol) = 0;
55  /**
56  * Client code must implement this method.
57  * Given a partial solution, returns all its children solution, regardless
58  * of their validity or completeness.
59  */
60  virtual void generateChildren(const T& sol, std::vector<T>& sols) = 0;
61  /**
62  * Client code must implement this method.
63  * Given a partial solution, estimates the cost of the remaining (unknown)
64  * part.
65  * This cost must always be greater or equal to zero, and not greater than
66  * the actual cost. Thus, must be 0 if the solution is complete.
67  */
68  virtual double getHeuristic(const T& sol) = 0;
69  /**
70  * Client code must implement this method.
71  * Given a (possibly partial) solution, calculates its cost so far.
72  * This cost must not decrease with each step. That is, a solution cannot
73  * have a smaller cost than the previous one from which it was generated.
74  */
75  virtual double getCost(const T& sol) = 0;
76 
77  private:
78  /**
79  * Calculates the total cost (known+estimated) of a solution.
80  */
81  inline double getTotalCost(const T& sol)
82  {
83  return getHeuristic(sol) + getCost(sol);
84  }
85 
86  public:
87  /**
88  * Finds the optimal solution for a problem, using the A* algorithm.
89  * Returns whether an optimal solution was actually found.
90  * Returns 0 if no solution was found, 1 if an optimal solution was found
91  * and 2 if a (possibly suboptimal) solution was found but the time lapse
92  * ended.
93  */
95  const T& initialSol, T& finalSol, double upperLevel = HUGE_VAL,
96  double maxComputationTime = HUGE_VAL)
97  {
98  // Time measuring object is defined.
100  time.Tic();
101  // The partial solution set is initialized with a single element (the
102  // starting solution).
103  std::multimap<double, T> partialSols;
104  partialSols.insert(
105  std::pair<double, T>(getTotalCost(initialSol), initialSol));
106  // The best known solution is set to the upper bound (positive infinite,
107  // if there is no given parameter).
108  double currentOptimal = upperLevel;
109  bool found = false;
110  std::vector<T> children;
111  // Main loop. Each iteration checks an element of the set, with minimum
112  // estimated cost.
113  while (!partialSols.empty())
114  {
115  // Return if elapsed time has been reached.
116  if (time.Tac() >= maxComputationTime) return found ? 2 : 0;
118  partialSols.begin();
119  double tempCost = it->first;
120  // If the minimum estimated cost is higher than the upper bound,
121  // then also is every solution in the set. So the algorithm returns
122  // immediately.
123  if (tempCost >= currentOptimal) return found ? 1 : 0;
124  T tempSol = it->second;
125  partialSols.erase(it);
126  // At this point, the solution cost is lesser than the upper bound.
127  // So, if the solution is complete, the optimal solution and the
128  // upper bound are updated.
129  if (isSolutionEnded(tempSol))
130  {
131  currentOptimal = tempCost;
132  finalSol = tempSol;
133  found = true;
134  continue;
135  }
136  // If the solution is not complete, check for its children. Each one
137  // is included in the set only if it's valid and it's not yet
138  // present in the set.
139  generateChildren(tempSol, children);
140  for (typename std::vector<T>::const_iterator it2 = children.begin();
141  it2 != children.end(); ++it2)
142  if (isSolutionValid(*it2))
143  {
144  bool alreadyPresent = false;
145  double cost = getTotalCost(*it2);
146  typename std::pair<
149  range = partialSols.equal_range(cost);
150  for (typename std::multimap<double, T>::const_iterator it3 =
151  range.first;
152  it3 != range.second; ++it3)
153  if (it3->second == *it2)
154  {
155  alreadyPresent = true;
156  break;
157  }
158  if (!alreadyPresent)
159  partialSols.insert(
160  std::pair<double, T>(getTotalCost(*it2), *it2));
161  }
162  }
163  // No more solutions to explore...
164  return found ? 1 : 0;
165  }
166 };
167 }
168 } // End of namespaces
169 #endif
GLsizei range
Definition: glext.h:5907
virtual bool isSolutionEnded(const T &sol)=0
Client code must implement this method.
Scalar * iterator
Definition: eigen_plugins.h:26
const Scalar * const_iterator
Definition: eigen_plugins.h:27
void Tic()
Starts the stopwatch.
Definition: CTicTac.cpp:82
double getTotalCost(const T &sol)
Calculates the total cost (known+estimated) of a solution.
virtual void generateChildren(const T &sol, std::vector< T > &sols)=0
Client code must implement this method.
This class implements a high-performance stopwatch.
Definition: CTicTac.h:23
virtual bool isSolutionValid(const T &sol)=0
Client code must implement this method.
This class is intended to efficiently solve graph-search problems using heuristics to determine the b...
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
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.
double Tac()
Stops the stopwatch.
Definition: CTicTac.cpp:97
virtual double getHeuristic(const T &sol)=0
Client code must implement this method.



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: ae4571287 Thu Nov 23 00:06:53 2017 +0100 at dom oct 27 23:51:55 CET 2019