72 virtual double getCost(
const T& sol) = 0;
92 const T& initialSol, T& finalSol,
double upperLevel = HUGE_VAL,
93 double maxComputationTime = HUGE_VAL)
100 std::multimap<double, T> partialSols;
102 std::pair<double, T>(
getTotalCost(initialSol), initialSol));
105 double currentOptimal = upperLevel;
107 std::vector<T> children;
110 while (!partialSols.empty())
113 if (time.
Tac() >= maxComputationTime)
return found ? 2 : 0;
114 typename std::multimap<double, T>::iterator it =
116 double tempCost = it->first;
120 if (tempCost >= currentOptimal)
return found ? 1 : 0;
121 T tempSol = it->second;
122 partialSols.erase(it);
128 currentOptimal = tempCost;
137 for (
typename std::vector<T>::const_iterator it2 = children.begin();
138 it2 != children.end(); ++it2)
141 bool alreadyPresent =
false;
144 typename std::multimap<double, T>::const_iterator,
145 typename std::multimap<double, T>::const_iterator>
146 range = partialSols.equal_range(cost);
147 for (
typename std::multimap<double, T>::const_iterator it3 =
149 it3 != range.second; ++it3)
150 if (it3->second == *it2)
152 alreadyPresent =
true;
161 return found ? 1 : 0;
double Tac() noexcept
Stops the stopwatch.
Abstract graph and tree data structures, plus generic graph algorithms.
virtual bool isSolutionEnded(const T &sol)=0
Client code must implement this method.
A high-performance stopwatch, with typical resolution of nanoseconds.
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.
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.
virtual double getHeuristic(const T &sol)=0
Client code must implement this method.
void Tic() noexcept
Starts the stopwatch.