• Lesson
9-12
2

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.

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 Nearest Neighbor Activity Sheet 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 Cheapest Link Activity Sheet 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 Brute Force Activity Sheet 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)÷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.

### Best Route

Distribute the Best Route Activity Sheet to students.

Depending on timing and pacing, you may choose to allow students to complete this in class or assign it as homework.

### Reference

Consortium for Mathematics and Its Applications. 1987. For All Practical Purposes. Bedford, MA: COMAP.

Assessment Option

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

1. 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.
2. 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.

Questions for Students

1. Explain why the algorithms are given the names they are: Nearest Neighbor, Cheapest Link, and Brute Force.
2. 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.
3. 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?

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?

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

### Common Core State Standards – Practice

• CCSS.Math.Practice.MP1
Make sense of problems and persevere in solving them.