| |
Students explore a variation of the traveling salesman problem based on cost: What is the cheapest path through a network that will hit all nodes and return to the starting point? Activity sheets guide students through a brute-force approach and then a nearest-neighbor algorithm to find the cheapest route for a college recruiter to follow in visiting several cities. Students discover that the brute-force method always provides the optimal solution but is too inefficient to use in most applications.
Students explore a variation of the traveling salesman problem based on cost: What is the cheapest path through a network that will hit all nodes and return to the starting point? Activity sheets guide students through a brute-force approach and then a nearest-neighbor algorithm to find the cheapest route for a college recruiter to follow in visiting several cities. Students discover that the brute-force method always provides the optimal solution but is too inefficient to use in most applications. A 30-page resource for the teacher provides background to the lesson, describes several extensions including adding a city to an already established route, and poses a number of real-life business applications. Blackline masters, complete solutions to problems, and Internet extensions are also included. (sw)
|
|
| |
With this lesson, career-technical students can discover that using a mathematics algorithm provides the best and simplest solution to this complex problem. One of the lesson's values is that students can see the difference between the brute-force approach to a complicated problem and the use of an established algorithm.
With this lesson, career-technical students can discover that using a mathematics algorithm provides the best and simplest solution to this complex problem. One of the lesson's values is that students can see the difference between the brute-force approach to a complicated problem and the use of an established algorithm. Career-technical teachers might want to find an application of networking theory in their content area.
|
|
|  |
|
| Mathematics Academic Content Standards |
|
|
| Measurement Standard |  |
|
| Benchmarks (8 - 10) |
|
| F. | Write and solve real-world, multi-step problems involving money, elapsed time and temperature, and verify reasonableness of solutions. |
|
|
| Patterns, Functions and Algebra Standard | |
|
| Benchmarks (8 - 10) |
|
| A. | Generalize and explain patterns and sequences in order to find the next term and the nth term. |
|
| Benchmarks (11 - 12) |
|
| C. | Use recursive functions to model and solve problems; e.g., home mortgages, annuities. |
|
| Grade Level Indicators (Grade 8) |
|
| 2. | Generalize patterns and sequences by describing how to find the nth term. |
|
| Grade Level Indicators (Grade 11) |
|
| 1. | Identify and describe problem situations involving an iterative process that can be represented as a recursive function; e.g., compound interest. |
|
|
| Data Analysis and Probability Standard | |
|
| Benchmarks (8 - 10) |
|
| H. | Use counting techniques, such as permutations and combinations, to determine the total number of options and possible outcomes. |
|
| Grade Level Indicators (Grade 8) |
|
| 10. | Calculate the number of possible outcomes for a situation, recognizing and accounting for when items may occur more than once or when order is important. |
|
| Grade Level Indicators (Grade 9) |
|
| 7. | Use counting techniques and the Fundamental Counting principle to determine the total number of possible outcomes for mathematical situations. |
|
|
| Mathematical Processes Standard | |
|
| Benchmarks (8 - 10) |
|
| A. | Formulate a problem or mathematical model in response to a specific need or situation, determine information required to solve the problem, choose method for obtaining this information, and set limits for acceptable solution. |
| B. | Apply mathematical knowledge and skills routinely in other content areas and practical situations. |
|
| Benchmarks (11 - 12) |
|
| A. | Construct algorithms for multi-step and non-routine problems. |
| J. | Apply mathematical modeling to workplace and consumer situations, including problem formulation, identification of a mathematical model, interpretation of solution within the model, and validation to original problem situation. |
|
|
|
| |
| Principles and Standards for School Mathematics |
|
|
| Algebra Standard | |
|
| Understand patterns, relations, and functions |
|
| Expectations (9 - 12) |
| generalize patterns using explicitly defined and recursively defined functions; |
|
|
| Geometry Standard | |
|
| Use visualization, spatial reasoning, and geometric modeling to solve problems |
|
| Expectations (6 - 8) |
| use visual tools such as networks to represent and solve problems; |
|
| Expectations (9 - 12) |
| use vertex-edge graphs to model and solve problems; |
|
|
| Problem Solving Standard | |
|
| Build new mathematical knowledge through problem solving |
|
| Solve problems that arise in mathematics and in other contexts |
|
| Apply and adapt a variety of appropriate strategies to solve problems |
|
|
| Connections Standard | |
|
| Recognize and apply mathematics in contexts outside of mathematics |
|
|
|
|
|
 |
| RESOURCE TYPE |
| Instructional Resource |
| PRACTICE LEVEL |
| Best Practice |
| STANDARDS ALIGNMENT |
| Grades 8 - 12 |
| CAREER FIELDS |
Construction Technologies;
Finance;
Hospitality & Tourism;
Manufacturing Technologies;
Transportation Systems;
General Career Skills |
| TOPICS |
Mathematics --
Discrete Mathematics;
Connections, applications;
Problem Solving |
| FOUND IN |
| Standards First |
| KEYWORDS |
Hamiltonian path;
network;
graph theory;
path;
Dijkstra's algorithm |
|
Author: Kenneth Chelst and Tom Edwards
Publisher: High School Operations Research
|
|