Travelling Salesman

The travelling salesman is a classic maths problem that still interests scholars around the world.

How it Works

Travel from city to city, paying tolls based on what roads you take.

Things to Try or Ask Around the Exhibit

  • What is the cheapest route you can find?
  • How do you know if you've found the cheapest route?
  • Try using different maps; are some harder than others?

Background

For some problems it can be relatively easy to find a good solution, but may be very hard to find the best solution. The travelling salesman is a classic example of such a problem.

Finding the Science in Your World

Navigation software solves a version of the travelling salesman problem in many situations, from planning trips to designing delivery routes (substituting the tolls in the version presented here for 'distance' or 'travel time' perhaps in the real world).