Chapter 6: The Traveling-Salesman Problem: Hamilton Joins the Circuit
A successful student can...
- Identify and model Hamilton circuit and Hamilton path problems.
- Recognize complete graphs and state the number of Hamilton circuits that they have.
- Identify traveling-salesman problems and the difficulties faced in solving them.
- Implement brute-force, nearest-neighbor, repeated nearest-neighbor, and cheapest-link algorithms to find approximate solutions to traveling-salesman problems.
- Recognize the difference between efficient and inefficient algorithms.
- Recognize the difference between optimal and approximate algorithms.