The Travelling Salesman

This year we are doing the module “Decision 2”, D2 for short. And I’m really, really enjoying teaching it. This week’s topic has been the Travelling Salesman problem, which is a fantastic springboard into a whole host of other areas of maths. When we looked at route inspection during the last module I made mention of the traveling salesman problem and the fact there is no known way to solve it in a reasonable amount of time and I briefly mentioned P vs NP and the millenium prize.

When we started this week with a slide that had the title on the class were automatically hooked. They had been eager to reach the traveling salesman and had even looked up P vs NP and the aforementioned millenium prizes. This meant before we even started d the lesson we had an awesome conversation about these amazing unsolved mathematical problems, with the class telling me what they had read and what they thought they understood of it and me filling in the gaps around it a bit and linking to other areas of maths.

Towards the end of this discussion one asked “but what are we going to study?  We all already know it can’t be solved quickly enough for an exam!” Which led me onto the discussion of lower and upper bounds and optimal regions, and how we can find a good solution (within 1% of an optimal solution) within a reasonably short time.

This left around enough time to discuss least differences and tackle the nearest neighbour algorithm for an upper bound. The following lesson we looked at using minimum connectors for upprbounds and how we could identify the best upper bound. Then we looked at lower bounds, and how to identify of we had found an optimal solution or an optimal region. I do hope TSP makes it into the optional content of further maths when the new specification starts.

This post was cross-posted to Cavmaths here.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s