Algorithms & EmergenceOptimization

The Traveling Salesman

Visiting every city once by the shortest route gets impossibly hard

A van with 20 stops has more possible routes than seconds have passed since the dinosaurs died. How does anyone pick one?

You'll find out

  • Why each extra stop makes routes explode
  • Why the nearest stop can be a trap
  • Why it's tied to a $1 million prize

Why it matters

Delivery vans, chip factories and DNA labs all face it: the best order is easy to ask for and hard to find.

About 4 min7 interactive slides · 5 questionsLesson 509 · Zone 57

Play this lesson

Free to play in your browser or on iPhone

More in this zone

  1. 505Information TheoryThe Counterfeit CoinTwelve coins, one fake, three weighings, and a lot of information
  2. 506Hardware BugsThe Chip That Couldn't DivideIntel's 1994 Pentium got some divisions wrong and cost $475 million
  3. 507Unsupervised LearningFinding Groups Nobody NamedAI can discover clusters in data without labels
  4. 508Cognitive PsychologyChoice BlindnessPeople defend choices they never made
  5. 510GeodesyThe Highest Point Isn't EverestEarth bulges, so a volcano in Ecuador is farthest from its center
  6. 511GeometryStacking OrangesGrocers knew the best stacking for centuries; proving it took a computer
  7. 512Online CommunitiesHow Wikipedia Fights VandalsAnyone can edit, and bad edits often vanish in seconds
  8. 513Anonymous CommunicationThe Onion RouteLayers of relays hide who is talking to whom