On an overhead or LCD projector, present the Road Trip Overhead.
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
- 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 Nearest Neighbor Activity Sheet to students.
Nearest Neighbor Activity Sheet
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
Cheapest Link Algorithm
Distribute the Cheapest Link Activity Sheet to students.
Cheapest Link Activity Sheet
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
- 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 Brute Force Activity Sheet to students.
Brute Force Activity Sheet
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)÷2 = 3.
- Using this idea for 5 cities we get (4·3·2·1)÷2=12, and for 6 cities we get (5·4·3·2·1)÷2=60.
- Thus, for n cities we get [(n-1)(n-2)···3·2·1]÷2=(n-1)!÷2
Allow students to complete Questions 5 and 6 independently.
Distribute the Best Route Activity Sheet to students.
Best Route Activity Sheet
Depending on timing and pacing, you may choose to allow students to complete this in class or assign it as homework.
Road Trip Answer Keys
Consortium for Mathematics and Its Applications. 1987. For All Practical Purposes. Bedford, MA: COMAP.
Since the explanation of the algorithms will most likely take a full
period or more, the Best Route Activity can be used as an assessment of
students' understanding of the material.
- Given current gas prices and the mileage of an average car, have
students estimate the amount of money saved by taking the shortest
route instead of the longest.
- Have students determine the number of years it would take for
a computer that can check 10 billion round-trips a second to find the
shortest round-trip visiting all the capitals of the lower 48 states.