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.2 for MRPT 0.9.4 SVN: at Mon Jan 10 22:30:30 UTC 2011 |