Example: graphs_astar_example
Demo for the A* generic solver:
Example console output:
Input an integer number to solve a problem, or "e" to end. 761 An optimal solution has been found: 2 coins of 2 piastres. 0 coins of 7 piastres. 2 coins of 8 piastres. 39 coins of 19 piastres.
C++ example source code:
/* +------------------------------------------------------------------------+ | Mobile Robot Programming Toolkit (MRPT) | | https://www.mrpt.org/ | | | | Copyright (c) 2005-2023, Individual contributors, see AUTHORS file | | See: https://www.mrpt.org/Authors - All rights reserved. | | Released under BSD License. See: https://www.mrpt.org/License | +------------------------------------------------------------------------+ */ #include <mrpt/graphs/CAStarAlgorithm.h> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> using namespace std; using namespace mrpt::graphs; class CCoinDistribution { public: size_t coins2{0}; size_t coins7{0}; size_t coins8{0}; size_t coins19{0}; CCoinDistribution() {} size_t money() const { return 2 * coins2 + 7 * coins7 + 8 * coins8 + 19 * coins19; } inline bool operator==(const CCoinDistribution& mon) const { return (coins2 == mon.coins2) && (coins7 == mon.coins7) && (coins8 == mon.coins8) && (coins19 == mon.coins19); } }; class CAStarExample : public CAStarAlgorithm<CCoinDistribution> { private: const size_t N; public: CAStarExample(size_t goal) : N(goal) {} bool isSolutionEnded(const CCoinDistribution& s) override { // True if the solution is complete. return s.money() == N; } bool isSolutionValid(const CCoinDistribution& s) override { // True if the solution is valid. return s.money() <= N; } void generateChildren( const CCoinDistribution& s, vector<CCoinDistribution>& sols) override { // Get all the children of a solution. // Complex classes might want to define a copy constructor (note how the // vector in the following line is created by cloning this object four // times). sols = vector<CCoinDistribution>(4, s); sols[0].coins2++; // Misma solución, más una moneda de 2. sols[1].coins7++; // Misma solución, más una moneda de 7. sols[2].coins8++; // Misma solución, más una moneda de 8... sols[3].coins19++; // Y misma solución, más una moneda de 19. } double getHeuristic(const CCoinDistribution& s) override { // Heuristic cost of the remaining part of the solution. // Check the documentation of CAStarAlgorithm to know which // characteristics does this function need to comply. return static_cast<double>(N - s.money()) / 19.0; } double getCost(const CCoinDistribution& s) override { // Known cost of the partial solution. return s.coins2 + s.coins7 + s.coins8 + s.coins19; } }; int main(int argc, char** argv) { for (;;) { char text[11]; printf( "Input an integer number to solve a problem, or \"e\" to end.\n"); if (1 != scanf( "%10s", text)) // GCC warning: scanf -> return cannot be ignored! { printf("Please, input a positive integer.\n\n"); continue; } if (strlen(text) == 1 && (text[0] == 'e' || text[0] == 'E')) break; int val = atoi(text); if (val <= 0) { printf("Please, input a positive integer.\n\n"); continue; } // The solution objects and the problem are created... CCoinDistribution solIni, solFin; // Initial solution automatically initialized to (0,0,0,0). CAStarExample prob(static_cast<size_t>(val)); switch (prob.getOptimalSolution(solIni, solFin, HUGE_VAL, 15)) { case 0: printf( "No solution has been found. Either the number is too " "small, or the time elapsed has exceeded 15 seconds.\n\n"); break; case 1: printf("An optimal solution has been found:\n"); printf( "\t%u coins of 2 piastres.\n\t%u coins of 7 " "piastres.\n\t%u coins of 8 piastres.\n\t%u coins of 19 " "piastres.\n\n", (unsigned)solFin.coins2, (unsigned)solFin.coins7, (unsigned)solFin.coins8, (unsigned)solFin.coins19); break; case 2: printf( "A solution has been found, although it may not be " "optimal:\n"); printf( "\t%u coins of 2 piastres.\n\t%u coins of 7 " "piastres.\n\t%u coins of 8 piastres.\n\t%u coins of 19 " "piastres.\n\n", (unsigned)solFin.coins2, (unsigned)solFin.coins7, (unsigned)solFin.coins8, (unsigned)solFin.coins19); break; } } return 0; }