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-2024, Individual contributors, see AUTHORS file     |
| 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;
}```