9#ifndef CASTARALGORITHM_H
10#define CASTARALGORITHM_H
13#define _USE_MATH_DEFINES
75 int getOptimalSolution(
const T &initialSol,T &finalSol,
double upperLevel=HUGE_VAL,
double maxComputationTime=HUGE_VAL) {
80 std::multimap<double,T> partialSols;
81 partialSols.insert(std::pair<double,T>(
getTotalCost(initialSol),initialSol));
83 double currentOptimal=upperLevel;
85 std::vector<T> children;
87 while (!partialSols.empty()) {
89 if (time.
Tac()>=maxComputationTime)
return found?2:0;
90 typename std::multimap<double,T>::iterator it=partialSols.begin();
91 double tempCost=it->first;
93 if (tempCost>=currentOptimal)
return found?1:0;
95 partialSols.erase(it);
98 currentOptimal=tempCost;
105 for (
typename std::vector<T>::const_iterator it2=children.begin();it2!=children.end();++it2)
if (
isSolutionValid(*it2)) {
106 bool alreadyPresent=
false;
108 typename std::pair<typename std::multimap<double,T>::const_iterator,
typename std::multimap<double,T>::const_iterator> range = partialSols.equal_range(cost);
109 for (
typename std::multimap<double,T>::const_iterator it3=range.first;it3!=range.second;++it3)
if (it3->second==*it2) {
113 if (!alreadyPresent) partialSols.insert(std::pair<double,T>(
getTotalCost(*it2),*it2));
This class is intended to efficiently solve graph-search problems using heuristics to determine the b...
double getTotalCost(const T &sol)
Calculates the total cost (known+estimated) of a solution.
virtual bool isSolutionEnded(const T &sol)=0
Client code must implement this method.
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.
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.
This class implements a high-performance stopwatch.
double Tac()
Stops the stopwatch.
void Tic()
Starts the stopwatch.
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.