Main MRPT website > C++ reference
MRPT logo
CAStarAlgorithm.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | The Mobile Robot Programming Toolkit (MRPT) C++ library |
3  | |
4  | http://www.mrpt.org/ |
5  | |
6  | Copyright (C) 2005-2012 University of Malaga |
7  | |
8  | This software was written by the Machine Perception and Intelligent |
9  | Robotics Lab, University of Malaga (Spain). |
10  | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |
11  | |
12  | This file is part of the MRPT project. |
13  | |
14  | MRPT is free software: you can redistribute it and/or modify |
15  | it under the terms of the GNU General Public License as published by |
16  | the Free Software Foundation, either version 3 of the License, or |
17  | (at your option) any later version. |
18  | |
19  | MRPT is distributed in the hope that it will be useful, |
20  | but WITHOUT ANY WARRANTY; without even the implied warranty of |
21  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22  | GNU General Public License for more details. |
23  | |
24  | You should have received a copy of the GNU General Public License |
25  | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |
26  | |
27  +---------------------------------------------------------------------------+ */
28 #ifndef CASTARALGORITHM_H
29 #define CASTARALGORITHM_H
30 #include <map>
31 #include <vector>
32 #include <cmath>
33 #include <mrpt/utils/CTicTac.h>
34 
35 namespace mrpt
36 {
37  namespace graphs
38  {
39  /** 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
40  * so that it contains all the information about any partial or complete solution. Then, a class inheriting from CAStarAlgorithm<Solution class> must also be
41  * implemented, overriding five virtual methods which define the behaviour of the solutions. These methods are isSolutionEnded, isSolutionValid,
42  * generateChildren, getHeuristic and getCost.
43  * Once both classes are generated, each object of the class inheriting from CAStarAlgorithm represents a problem who can be solved by calling
44  * getOptimalSolution. See http://en.wikipedia.org/wiki/A*_search_algorithm for details about how this algorithm works.
45  * \sa CAStarAlgorithm::isSolutionEnded
46  * \sa CAStarAlgorithm::isSolutionValid
47  * \sa CAStarAlgorithm::generateChildren
48  * \sa CAStarAlgorithm::getHeuristic
49  * \sa CAStarAlgorithm::getCost
50  * \ingroup mrpt_graphs_grp
51  */
52  template<typename T> class CAStarAlgorithm {
53  public:
54  /**
55  * Client code must implement this method.
56  * Returns true if the given solution is complete.
57  */
58  virtual bool isSolutionEnded(const T &sol)=0;
59  /**
60  * Client code must implement this method.
61  * Returns true if the given solution is acceptable, that is, doesn't violate the problem logic.
62  */
63  virtual bool isSolutionValid(const T &sol)=0;
64  /**
65  * Client code must implement this method.
66  * Given a partial solution, returns all its children solution, regardless of their validity or completeness.
67  */
68  virtual void generateChildren(const T &sol,std::vector<T> &sols)=0;
69  /**
70  * Client code must implement this method.
71  * Given a partial solution, estimates the cost of the remaining (unknown) part.
72  * 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.
73  */
74  virtual double getHeuristic(const T &sol)=0;
75  /**
76  * Client code must implement this method.
77  * Given a (possibly partial) solution, calculates its cost so far.
78  * 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.
79  */
80  virtual double getCost(const T &sol)=0;
81  private:
82  /**
83  * Calculates the total cost (known+estimated) of a solution.
84  */
85  inline double getTotalCost(const T &sol) {
86  return getHeuristic(sol)+getCost(sol);
87  }
88  public:
89  /**
90  * Finds the optimal solution for a problem, using the A* algorithm. Returns whether an optimal solution was actually found.
91  * 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.
92  */
93  int getOptimalSolution(const T &initialSol,T &finalSol,double upperLevel=HUGE_VAL,double maxComputationTime=HUGE_VAL) {
94  //Time measuring object is defined.
95  mrpt::utils::CTicTac time;
96  time.Tic();
97  //The partial solution set is initialized with a single element (the starting solution).
98  std::multimap<double,T> partialSols;
99  partialSols.insert(std::pair<double,T>(getTotalCost(initialSol),initialSol));
100  //The best known solution is set to the upper bound (positive infinite, if there is no given parameter).
101  double currentOptimal=upperLevel;
102  bool found=false;
103  std::vector<T> children;
104  //Main loop. Each iteration checks an element of the set, with minimum estimated cost.
105  while (!partialSols.empty()) {
106  //Return if elapsed time has been reached.
107  if (time.Tac()>=maxComputationTime) return found?2:0;
108  typename std::multimap<double,T>::iterator it=partialSols.begin();
109  double tempCost=it->first;
110  //If the minimum estimated cost is higher than the upper bound, then also is every solution in the set. So the algorithm returns immediately.
111  if (tempCost>=currentOptimal) return found?1:0;
112  T tempSol=it->second;
113  partialSols.erase(it);
114  //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.
115  if (isSolutionEnded(tempSol)) {
116  currentOptimal=tempCost;
117  finalSol=tempSol;
118  found=true;
119  continue;
120  }
121  //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.
122  generateChildren(tempSol,children);
123  for (typename std::vector<T>::const_iterator it2=children.begin();it2!=children.end();it2++) if (isSolutionValid(*it2)) {
124  bool alreadyPresent=false;
125  double cost=getTotalCost(*it2);
126  typename std::pair<typename std::multimap<double,T>::const_iterator,typename std::multimap<double,T>::const_iterator> range = partialSols.equal_range(cost);
127  for (typename std::multimap<double,T>::const_iterator it3=range.first;it3!=range.second;it3++) if (it3->second==*it2) {
128  alreadyPresent=true;
129  break;
130  }
131  if (!alreadyPresent) partialSols.insert(std::pair<double,T>(getTotalCost(*it2),*it2));
132  }
133  }
134  //No more solutions to explore...
135  return found?1:0;
136  }
137  };
138  }
139 } //End of namespaces
140 #endif


Page generated by Doxygen 1.8.3 for MRPT 0.9.6 SVN: at Fri Feb 15 22:05:02 EST 2013