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. Also included are extension activities, homework problems, complete solutions to activities and problems, and a video discussing the value of the lesson’s mathematics to students. (sw/js)

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.