Main MRPT website > C++ reference for MRPT 1.5.6
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 #define _USE_MATH_DEFINES // (For VS to define M_PI, etc. in cmath)
14 #include <cmath>
15 #include <mrpt/utils/CTicTac.h>
16 
17 namespace 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);
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
GLenum GLenum range
Definition: glew.h:7127
virtual bool isSolutionEnded(const T &sol)=0
Client code must implement this method.
Scalar * iterator
Definition: eigen_plugins.h:23
const Scalar * const_iterator
Definition: eigen_plugins.h:24
void Tic()
Starts the stopwatch.
Definition: CTicTac.cpp:77
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:24
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.
double Tac()
Stops the stopwatch.
Definition: CTicTac.cpp:92
virtual double getHeuristic(const T &sol)=0
Client code must implement this method.



Page generated by Doxygen 1.8.6 for MRPT 1.5.6 Git: 4c65e84 Tue Apr 24 08:18:17 2018 +0200 at mar abr 24 08:26:17 CEST 2018