2. Network Simplification

My plan in the next segment of the project is to write a computer program that will generate "tours" of the tube network automatically, with the hope that some of the routes thrown up might actually take less than a day. Maybe one might even be close to 17 hours.

The computer program will need to be fed with how long it takes to get from station to station in order that it can seek out the smallest overall time to visit each one. Mathematicians call this type of puzzle a Travelling Salesman Problem. Luckily I have 3 A-Levels in maths, and a numerate degree (Physics) so I've been reading up about this area of mathematics and have learnt a number of useful things:
  • I'm not nearly as clever as I thought I was
  • The Travelling Salesman Problem is classed as being somthing known as 'NP-Hard'
  • Apparently this makes it unlikely that my Sony Vaio will find the optimal route within the lifetime of the universe
I'd quite like to use my computer for other things - like doing actual work to earn a living - so I'm going to need to simplify this problem in some way.