Metaheuristic approaches
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 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access