Traveling Salesman Problem
Read the book chapters first, then make sure you can answer the questions in the notes. Following that, work on some skills-check problems and exercises. Then take the online quizzes.
- Reading
- 2.2, 2.3
- Skills Check
- 3, 4, 6, 8, 10, 15
- Exercises
- 39, 40, 43, 44, 46, 48, 50, 51, 52
- Quiz
- Take the quiz
This day’s reading assignment also includes a file on minimum-cost spanning trees. Don’t miss it.
2.2
- What is the Traveling Salesman Problem? What kinds of graphs does it refer to?
- Think of some personal experience situations that you might represent as traveling salesman problems.
- What are some of the things that might be represented by “cost” in a TSP?
2.3
- Describe how the Nearest-Neighbor Algorithm works for the TSP.
- Demonstrate what results the Nearest-Neighbor Algorithm produces in some concrete examples.
- the NNA is an example of a greedy algorithm. Explain what this term refers to.
- Does NNA always produce the optimal route?
- Does the starting vertex matter for the NNA? Or do we always end up with the same circuit?
- Describe the Sorted-Edges Algorithm for the TSP.
- Demonstrate what results the Sorted-Edges Algorithm produces in some concrete examples.
- Does the Sorted-Edges Algorithm always produce the optimal route?