Students will plan a road trip, starting in Cleveland, to visit friends in Cincinnati, Pittsburgh, Baltimore, and Boston. However, with the price of gas over \$3.00 a gallon, they will figure out the shortest travel route to save on expenses. This lesson investigates three different methods to determine the shortest route: the Nearest Neighbor method, the Cheapest Link method, and the Brute Force method.

### Learning Objectives

 Students will: Interpret numerical information presented in table format and graph format Follow steps in a variety of settings to arrive at an optimal solution Sort a list of data in ascending order Use factorial to determine the total number of possible solutions

### Instructional Plan

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.

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.

• 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.

### Questions for Students

 Explain why the algorithms are given the names they are: Nearest Neighbor, Cheapest Link, and Brute Force. Besides planning a road trip to visit friends, list at least 3 other situations in which finding the shortest round-trip among a set of points would be useful. Which algorithm do you think you would use when planning a trip, and why? What factors other than the mathematical ones might influence your route decision?

### Assessment Options

 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.

### Extensions

 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. Have students create their own list of 5 or more cities in the USA, and then determine the shortest round-trip of those cities using various algorithms. You can find the solutions to their trips by using the TSP Generator.

### Teacher Reflection

 Was studentsâ€™ level of enthusiasm/involvement high or low? Explain why. How did students demonstrate understanding of the materials presented? Were concepts presented too abstractly? too concretely? How would you change your approach? What were some of the ways in which students showed they were actively engaged in the learning process? What content areas did you integrate within the lesson? Was this integration appropriate and successful? Did you find it necessary to make adjustments while teaching the lesson? If so, what adjustments, and were they effective?

### NCTM Standards and Expectations

 Algebra 9-12Draw reasonable conclusions about a situation being modeled. Data Analysis & Probability 9-12Understand the differences among various kinds of studies and which types of inferences can legitimately be drawn from each. Measurement 9-12Make decisions about units and scales that are appropriate for problem situations involving measurement. Number & Operations 9-12Judge the reasonableness of numerical computations and their results.

### References

 Consortium for Mathematics and Its Applications. 1987. For All Practical Purposes. Bedford, MA: COMAP.
 This lesson was prepared by James Reeder.

2 periods

### Web Sites

 More and Better Mathematics for All Students
 © 2000 National Council of Teachers of Mathematics Use of this Web site constitutes acceptance of the Terms of Use The National Council of Teachers of Mathematics is a public voice of mathematics education, providing vision, leadership, and professional development to support teachers in ensuring mathematics learning of the highest quality for all students. The views expressed or implied, unless otherwise noted, should not be interpreted as official positions of the Council.