Main MRPT website > C++ reference
MRPT logo

CAStarAlgorithm.h

Go to the documentation of this file.
00001 /* +---------------------------------------------------------------------------+
00002    |          The Mobile Robot Programming Toolkit (MRPT) C++ library          |
00003    |                                                                           |
00004    |                   http://mrpt.sourceforge.net/                            |
00005    |                                                                           |
00006    |   Copyright (C) 2005-2011  University of Malaga                           |
00007    |                                                                           |
00008    |    This software was written by the Machine Perception and Intelligent    |
00009    |      Robotics Lab, University of Malaga (Spain).                          |
00010    |    Contact: Jose-Luis Blanco  <jlblanco@ctima.uma.es>                     |
00011    |                                                                           |
00012    |  This file is part of the MRPT project.                                   |
00013    |                                                                           |
00014    |     MRPT is free software: you can redistribute it and/or modify          |
00015    |     it under the terms of the GNU General Public License as published by  |
00016    |     the Free Software Foundation, either version 3 of the License, or     |
00017    |     (at your option) any later version.                                   |
00018    |                                                                           |
00019    |   MRPT is distributed in the hope that it will be useful,                 |
00020    |     but WITHOUT ANY WARRANTY; without even the implied warranty of        |
00021    |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         |
00022    |     GNU General Public License for more details.                          |
00023    |                                                                           |
00024    |     You should have received a copy of the GNU General Public License     |
00025    |     along with MRPT.  If not, see <http://www.gnu.org/licenses/>.         |
00026    |                                                                           |
00027    +---------------------------------------------------------------------------+ */
00028 #ifndef CASTARALGORITHM_H
00029 #define CASTARALGORITHM_H
00030 #include <map>
00031 #include <vector>
00032 #include <cmath>
00033 #include <mrpt/utils/CTicTac.h>
00034 
00035 namespace mrpt  {       namespace math  {
00036         /**
00037           * 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
00038           * so that it contains all the information about any partial or complete solution. Then, a class inheriting from CAStarAlgorithm<Solution class> must also be
00039           * implemented, overriding five virtual methods which define the behaviour of the solutions. These methods are isSolutionEnded, isSolutionValid,
00040           * generateChildren, getHeuristic and getCost.
00041           * Once both classes are generated, each object of the class inheriting from CAStarAlgorithm represents a problem who can be solved by calling
00042           * getOptimalSolution. See http://en.wikipedia.org/wiki/A*_search_algorithm for details about how this algorithm works.
00043           * \sa CAStarAlgorithm::isSolutionEnded
00044           * \sa CAStarAlgorithm::isSolutionValid
00045           * \sa CAStarAlgorithm::generateChildren
00046           * \sa CAStarAlgorithm::getHeuristic
00047           * \sa CAStarAlgorithm::getCost
00048           */
00049 template<typename T> class CAStarAlgorithm      {
00050 public:
00051         /**
00052           * Client code must implement this method.
00053           * Returns true if the given solution is complete.
00054           */
00055         virtual bool isSolutionEnded(const T &sol)=0;
00056         /**
00057           * Client code must implement this method.
00058           * Returns true if the given solution is acceptable, that is, doesn't violate the problem logic.
00059           */
00060         virtual bool isSolutionValid(const T &sol)=0;
00061         /**
00062           * Client code must implement this method.
00063           * Given a partial solution, returns all its children solution, regardless of their validity or completeness.
00064           */
00065         virtual void generateChildren(const T &sol,std::vector<T> &sols)=0;
00066         /**
00067           * Client code must implement this method.
00068           * Given a partial solution, estimates the cost of the remaining (unknown) part.
00069           * 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.
00070           */
00071         virtual double getHeuristic(const T &sol)=0;
00072         /**
00073           * Client code must implement this method.
00074           * Given a (possibly partial) solution, calculates its cost so far.
00075           * 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.
00076           */
00077         virtual double getCost(const T &sol)=0;
00078 private:
00079         /**
00080           * Calculates the total cost (known+estimated) of a solution.
00081           */
00082         inline double getTotalCost(const T &sol)        {
00083                 return getHeuristic(sol)+getCost(sol);
00084         }
00085 public:
00086         /**
00087           * Finds the optimal solution for a problem, using the A* algorithm. Returns whether an optimal solution was actually found.
00088           * 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.
00089           */
00090         int getOptimalSolution(const T &initialSol,T &finalSol,double upperLevel=HUGE_VAL,double maxComputationTime=HUGE_VAL)   {
00091                 //Time measuring object is defined.
00092                 mrpt::utils::CTicTac time;
00093                 time.Tic();
00094                 //The partial solution set is initialized with a single element (the starting solution).
00095                 std::multimap<double,T> partialSols;
00096                 partialSols.insert(std::pair<double,T>(getTotalCost(initialSol),initialSol));
00097                 //The best known solution is set to the upper bound (positive infinite, if there is no given parameter).
00098                 double currentOptimal=upperLevel;
00099                 bool found=false;
00100                 std::vector<T> children;
00101                 //Main loop. Each iteration checks an element of the set, with minimum estimated cost.
00102                 while (!partialSols.empty())    {
00103                         //Return if elapsed time has been reached.
00104                         if (time.Tac()>=maxComputationTime) return found?2:0;
00105                         typename std::multimap<double,T>::iterator it=partialSols.begin();
00106                         double tempCost=it->first;
00107                         //If the minimum estimated cost is higher than the upper bound, then also is every solution in the set. So the algorithm returns immediately.
00108                         if (tempCost>=currentOptimal) return found?1:0;
00109                         T tempSol=it->second;
00110                         partialSols.erase(it);
00111                         //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.
00112                         if (isSolutionEnded(tempSol))   {
00113                                 currentOptimal=tempCost;
00114                                 finalSol=tempSol;
00115                                 found=true;
00116                                 continue;
00117                         }
00118                         //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.
00119                         generateChildren(tempSol,children);
00120                         for (typename std::vector<T>::const_iterator it2=children.begin();it2!=children.end();it2++) if (isSolutionValid(*it2)) {
00121                                 bool alreadyPresent=false;
00122                                 double cost=getTotalCost(*it2);
00123                                 typename std::pair<typename std::multimap<double,T>::const_iterator,typename std::multimap<double,T>::const_iterator> range = partialSols.equal_range(cost);
00124                                 for (typename std::multimap<double,T>::const_iterator it3=range.first;it3!=range.second;it3++) if (it3->second==*it2)   {
00125                                         alreadyPresent=true;
00126                                         break;
00127                                 }
00128                                 if (!alreadyPresent) partialSols.insert(std::pair<double,T>(getTotalCost(*it2),*it2));
00129                         }
00130                 }
00131                 //No more solutions to explore...
00132                 return found?1:0;
00133         }
00134 };
00135 }}      //End of namespaces
00136 #endif



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:40:17 UTC 2011