On an overhead or LCD projector, present the Road Trip Overhead. Have students brainstorm different ways of solving the problem. Write the different ways on the board. Some of the ideas may involve the following:
- Pick the closest city you haven't visited.
- Pick the lowest values from the table and use those to form a route.
- Determine all the possible routes and figure out which is the shortest.
Leave the overhead up or distribute paper copies of it so students have access to the data as they work through the activity sheets.
Nearest Neighbor Algorithm
Distribute the activity to students.
Go over the three steps of the method with students and demonstrate the steps with Question 1. When you have a map in front of you, a nice technique is to trace over each route with a colored pen as you work through the problem. That way, you know which points you have already visited. Allow students to work through Questions 2 and 3 individually. Have them compare answers with their neighbors when they are done.
Cheapest Link Algorithm
Distribute the activity to students.
Go over the steps with students and use Question 1 to show how to implement the method. Note: For this activity, route refers to a path from one city to another and mini-tour refers to a tour that does not include all cities.
Some questions you may choose to ask your students include:
- Why can't you have 3 routes going to and from the same city?
[In a road trip, you travel to and leave each city exactly once, which means you can have only 2 routes in and out of 1 city, not 3.]
- Why can't you have a route that creates a mini-tour of cities?
[The goal is to visit all the cities, not a subset of them.]
Either allow students to work on Question 2 alone or demonstrate the method again, engaging students to provide input. Have students work through Question 3 and have them compare answers with their neighbor. Note: It would be helpful for students to make a "hexagonal map" of the points to use for selecting the routes.
Brute Force Algorithm
Distribute the activity to students.
Go over the steps with students and use Question 1 to show how to implement the method. Have students work on Questions 2 and 3 individually, and then compare their answers with a neighbor.
Have students work together to answer Question 4. If they have studied probability before, hopefully they can figure out the answer as a class. If they have not, help them work through and understand the problem using the following explanation:
- In the 4 city example starting from city A, how many choices did we have for the next city?
[3] |
- After we visited that city, how many choices for the next city did we have?
[2] |
- After that city, how many choices remained?
[1] |
- Therefore, the number of ways was therefore 3 then 2 then 1, which can be expressed mathematically as n(ways) = 3 · 2 · 1 = 6
|
- However, remembering the duplicates from Question 3 we get
| 3 · 2 · 1 | = 3 |
| 2 |
- Using this idea for 5 cities we get
| 4 · 3 · 2 · 1 | = 12, and for 6 cities we get | 5 · 4 · 3 · 2 · 1 | = 60 |
| 2 | 2 |
- Thus, for n cities we get
| (n – 1)(n – 2) · · · 3 · 2 · 1 | = | (n – 1)! |
| 2 | 2 |
Allow students to complete Questions 5 and 6 independently.
Best Route
Distribute the activity to students.
Depending on timing and pacing, you may choose to allow students to complete this in class or assign it as homework.
