While I was studying math (and some computer science) at Carleton, I came across the traveling salesman problem several times. It is one of the classic toy problems that computer scientists use to consider optimization algorithms and computational complexity.
In creating a lesson that would prompt our students to explore these ideas, I wanted to personalize it to their experience here at Conserve, thus, the wandering geocacher problem!
Here’s the scenario: On Conserve School’s campus, there are 11 geocaches (feel free to explore them at geocaching.com). On some beautiful Northwoods day, you decide to make it a mission to visit all 11 of these geocaches. You decide to be somewhat deliberate in the route you are going to take. Specifically, you would like to take the shortest route among these 11 geocaches. Which route should you choose?
Let’s begin by figuring out how to choose a route among a smaller number of geocaches. 3 seems manageable!
One approach you could take is to list all of the possible routes, calculate how long they each are, and then choose the shortest one. How many routes are there? Well, there are 3 ways to choose your first stop. Once that stop has been visited, there are 2 ways to choose your next stop. That leaves one unvisited geocache for you to visit last. So there are 3x2x1=6 possible routes to investigate. Not so bad!
Let’s see if we can apply the same strategy to our original problem. There are 11 ways to pick our first stop. Once we have picked our first stop, there are 10 ways to pick the second stop. Then 9 ways to pick the third, etc. When all is said and done, there are 11x10x9x8x7x6x5x4x3x2x1 = 39,916,800 routes to investigate (Side note: in the math world, we call this number 11 factorial and write 11! This is why you sometimes have to keep your enthusiasm in check when doing math. What a shame it would be if you were so excited to get 11 as your answer that you wrote 11!). The method we used before (which computer scientists would call a brute force method) seems like it will be a slow going and unpleasant process, even if we were computers. There has to be a better way!
At this point in the lesson, many students turned to the map of the geocaches for inspiration. We had discussions about what qualities our ideal route would have and then investigated how we could select a route with these properties using a table of the distances between each pair of geocaches. Some common qualities included choosing the next stop on your route to be the closest geocache to your current position that had not yet been visited (in computer science, this method is called the greedy strategy), and choosing one of the endpoints of the string of geocaches to be the starting point on the tour. Though routes found through these methods are not sure to find the shortest route, they did a pretty good job, and surely went faster than investigating all of the 39,916,800 possibilities!
Photos contributed by Kate Houle, Communications Specialist.