Title
A Traveling Rock Band Problem (Jo Ann Ellerbrock)
Goals
(1) Students will explore methods of finding a Hamiltonian circuit of least total weight.
(2) Students will develop methods of solving problems for which there is no known practical algorithm.
Abstract
This activity asks students to solve a "traveling salesman" problem set in the context of a traveling rock band. Since there is no known fast algorithm to solve this type of problem, students are expected to devise their own methods that are easy to implement. This is an introductory problem.
Problem Statement
The concept of minimizing traveling costs is important to all levels of life: personal, recreational, and corporate.
Instructor Suggestions
(1) Discuss types of situations for which there is a need to minimize a factor such as cost, distance or time.
(2) Have students use the guess and check method, then develop methods that minimize the amount of time required without missing possible routes.
(3) Discuss the nearest neighbor rule (Always choose, from the cities yet to be visited, the one that costs the least to get to.) This strategy gives the trip Denver to New York to Cleveland to Memphis to Denver. The total transportation cost is $791, which is not the minimum.
(4) Discuss how to use a tree to list all possible circuits and their costs. This is a good "lead-in" activity to using trees in other situations.
(5) (Optional) Discuss the time factor involved in solving the problem as the number of cities increased. Following are approximations of the time required to list by computer all Hamiltonian circuits in a graph in which each pair of vertices is joined by an edge if the computer can compute 10 billion computations per second.
No. of Vertices Time to list circuits less than 1 second 1 min., 27 sec. 21 min., 48 sec. 5 hr., 49 min. 4 days 2 months, 16 days 3 years, 10 months more than 19 million years Materials
Materials
A Traveling Rock Band worksheet, pencils, erasers
Time
One class period
Mathematics Concepts
Discrete Mathematics Concepts
Hamiltonian Circuits, Traveling Salesman Problem, Nearest Neighbor Rule, Heuristic Algorithms
Related Mathematics Concepts
Permutations, Combinations, Trees, Optimal Solutions
NCTM Standards Addressed
Problem Solving, Communication, Reasoning, Discrete Mathematics
Colorado Model Content Standards Addressed
Geometric Techniques (4), Problem Solving Techniques (5), Linking Concepts and Procedures (6)
Curriculum Integration
This activity could be integrated into a traditional Algebra, Advanced Algebra, or Pre-Calculus class as part of a discussion on permutations and combinations, or as part of a discussion on trees as a method of finding all possible combinations. It also could coordinate with Social Studies classes studying exploration and building of cities in terms of building the most efficient roads.
Further Investigation
The early stages of this activity provides an opportunity to discuss counting methods and probability.
Variations/Comments
This exercise is based on a problem found in HiMap Module 6, Problem Solving Using Graphs, by Margaret B. Cozzens and Richard Porter, available from the Consortium for Mathematics and Its Applications (COMAP), 57 Bedford Street, Suite 210, Lexington, MA 02173. This activity could be extended to a variety of other situations such as routes for meter readers, production line (e.g. drilling holes in plates in the most efficient order).
References/Resources
Cozzens, Margaret B., & Porter, Richard, Problem Solving Using Graphs. MA: COMAP
Crisler, N., Fisher, P., & Froelich, G. (1994). Discrete mathematics through applications. New York: W.H. Freeman and Company
Kenney, M.J., & Hirsch, C.R. (Eds.). (1991). Discrete mathematics across the curriculum, K-12. Reston, VA: National Council of Teachers of Mathematics.
Steen, Lynn A. (Ed.). (1991). For All Practical Purposes. New York: W.H. Freeman and Company