Appendix B. NP-hard problems
Both the set-covering and traveling salesperson problems have something in common: they are hard to solve. You have to check every possible iteration to find the smallest set cover or the shortest route.
Both of these problems are NP-hard. The terms NP, NP-hard, and NP-complete can cause a lot of confusion. They certainly confused me. In this appendix, I’ll try to explain what all these terms mean, but I need to explain some other concepts first. Here is a roadmap of the things we will learn and how they depend on each other:
But, first, I need to explain what a decision problem is because all the problems we will ...
Get Grokking Algorithms, Second Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
