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



Page generated by Doxygen 1.8.14 for MRPT 2.0.1 Git: 0fef1a6d7 Fri Apr 3 23:00:21 2020 +0200 at vie abr 3 23:20:28 CEST 2020