Traveling Salesman Problem — Definition, Formula & Examples
The Traveling Salesman Problem (TSP) asks: given a list of cities and the distances between each pair, what is the shortest possible route that visits every city exactly once and returns to the starting city? It is one of the most studied problems in combinatorial optimization because no known algorithm solves it efficiently for all cases.
Given a complete weighted graph with vertices and a cost function , the Traveling Salesman Problem seeks a Hamiltonian cycle (a cycle visiting every vertex exactly once) of minimum total cost. TSP is NP-hard, meaning no polynomial-time algorithm is known to exist that solves every instance optimally.
Key Formula
Where:
- = Number of cities to visit
- = Permutations of the remaining cities after fixing a start city
- = Accounts for the fact that a tour and its reverse have equal cost
How It Works
A brute-force approach evaluates every possible ordering of cities. For cities, there are distinct tours (dividing by 2 because a tour and its reverse have the same cost). This grows explosively: 10 cities yield 181,440 tours, while 20 cities yield over . In practice, exact methods like dynamic programming (Held–Karp algorithm) run in time, which is far better than brute force but still exponential. For large instances, heuristics and approximation algorithms — such as nearest-neighbor, 2-opt, or Christofides' algorithm — produce good (though not guaranteed optimal) solutions in reasonable time.
Worked Example
Problem: A salesperson must visit 4 cities — A, B, C, D — and return to A. The distances are: A–B = 10, A–C = 15, A–D = 20, B–C = 35, B–D = 25, C–D = 30. Find the shortest tour.
Count tours: With 4 cities, the number of distinct tours is:
List all tours: Starting from A, the three distinct tours and their total distances are:
A \to B \to C \to D \to A: 10 + 35 + 30 + 20 = 95$$ $$A \to B \to D \to C \to A: 10 + 25 + 30 + 15 = 80$$ $$A \to C \to B \to D \to A: 15 + 35 + 25 + 20 = 95
Select minimum: The tour A → B → D → C → A has the smallest total distance of 80.
Answer: The shortest tour is A → B → D → C → A with a total distance of 80.
Why It Matters
TSP models real logistics problems: delivery route planning, circuit board drilling, and DNA sequencing all reduce to variants of it. Understanding TSP is essential in algorithms courses because it is the canonical example of NP-hard optimization — the problem that motivates the study of approximation algorithms, heuristics, and computational complexity theory.
Common Mistakes
Mistake: Assuming the nearest-neighbor heuristic always finds the optimal tour.
Correction: Nearest-neighbor is a greedy heuristic that can produce tours significantly longer than optimal. It runs fast but offers no guaranteed optimality ratio for general TSP instances.