Traveling salesperson problem (TSP)

Definition

The Traveling Salesperson Problem (TSP) is a classic optimization problem in graph theory where the goal is to find the shortest possible route that visits each vertex exactly once and returns to the origin vertex. It has applications in logistics, planning, and network design.

5 Must Know Facts For Your Next Test

1. TSP is classified as an NP-hard problem, meaning there is no known polynomial-time solution.
2. Solutions to TSP can be exact or approximate; exact solutions are often impractical for large graphs due to computational complexity.
3. Common algorithms used to solve TSP include brute-force search, dynamic programming, and heuristic methods like the nearest neighbor algorithm.
4. The problem can be represented using a weighted complete graph where weights represent distances or costs between vertices.
5. Understanding TSP helps in studying other complex optimization problems and improving algorithms for practical applications.

Review Questions

• What type of problem classification does the Traveling Salesperson Problem fall under?
• Name two types of algorithms that can be used to solve the TSP.
• Explain why exact solutions for TSP are often impractical for large datasets.

Related terms

Graph: A collection of vertices connected by edges.

NP-hard: A classification of problems for which no polynomial-time solution is known.

Heuristic: An approach to solving problems that employs a practical method not guaranteed to be optimal but sufficient for reaching an immediate goal.