NP-Hard Problem
"Given a list of cities. What is the shortest path that visits each city exactly once and returns back?"
Why is this hard?
For N cities, there exists
• 10 cities: ~181 thousand paths.
• 20 cities: ~6 × 10¹⁶ (60 quadrillion).
For N cities, there exists
(N-1)! / 2 possible routes.
• 10 cities: ~181 thousand paths.
• 20 cities: ~6 × 10¹⁶ (60 quadrillion).
We can't check all of them, so we use heuristics (approximate methods), such as random permutations or Genetic Algorithms, to find a "good enough" solution.
Cities: 20
0