Dynamic programming is great for constraint satisfaction problems. However, better solutions can be found using something akin to systematic guessing, or metaheuristics. These problem-agnostic solution generators can be classified in several ways, for instance, whether they are population-based, inspired by nature, and searching globally or locally.
Whichever optimization algorithm is chosen, it will treat the problem like a search problem, trying to find the best possible solution within the solutions provided. Absent of any guarantees to find the best solution possible, it will typically find a good enough solution. Thanks to the expensive runtimes of NP-hard problems, a wide variety of ways can lead to a better solution than a more specific solution.
Popular metaheuristics include the following:
- Simulated annealing
- Genetic algorithms
- Particle swarm optimization
- Ant colony optimization
- Tabu search
Rust's ecosystem features several crates that implement...
