What is the Traveling Salesman Problem?
Learn the traveling salesman problem, why it is NP-hard, Held-Karp DP, and heuristics used to solve it in this interview guide.
Expected Interview Answer
The Traveling Salesman Problem (TSP) asks for the shortest possible route that visits every city exactly once and returns to the start, and it is NP-hard, meaning no known algorithm solves it exactly in polynomial time for all inputs.
Brute force checks all (n-1)!/2 possible tours, which is only feasible for a handful of cities; dynamic programming with bitmasking (Held-Karp) improves this to O(n² · 2ⁿ) by tracking the shortest path to each subset of visited cities ending at each vertex, still exponential but far better than factorial. Because exact solutions do not scale, real-world routing systems use approximation algorithms, like the nearest-neighbor heuristic or 2-opt local search, that trade a small amount of tour quality for speed, and metaheuristics like simulated annealing or genetic algorithms for larger instances. TSP is the classic example used to teach NP-hardness because it is easy to state, has enormous practical relevance (logistics, circuit board drilling, DNA sequencing), and clearly separates 'find any valid tour' (easy) from 'find the provably shortest tour' (hard).
- Canonical example for teaching NP-hardness and approximation tradeoffs
- Held-Karp DP reduces brute force from factorial to exponential-but-tighter time
- Heuristics like nearest-neighbor and 2-opt give fast, good-enough real-world routes
- Directly powers logistics, delivery routing, and manufacturing path optimization
AI Mentor Explanation
A board wants the shortest possible tour that visits every stadium in a series exactly once and returns the team to the starting city, minimizing total travel distance across the whole trip. Checking every possible ordering of stadiums to find the provably shortest tour explodes factorially as more cities are added to the schedule. So travel planners instead start at one city and repeatedly jump to the nearest unvisited stadium, then refine the tour by swapping pairs of legs that cross over each other to shorten the total distance. This nearest-neighbor-plus-swap approach gets a very good tour quickly, even though it cannot guarantee it is the absolute shortest possible.
Step-by-Step Explanation
Step 1
Model as a complete weighted graph
Each city is a vertex; each edge weight is the distance or cost between two cities.
Step 2
Brute force for tiny inputs
Enumerate all (n-1)!/2 distinct tours and pick the minimum-cost one; only feasible for very small n.
Step 3
Held-Karp DP for exact mid-size solutions
Track the shortest path to each (visited-subset, endpoint) pair, reducing time to O(n² · 2ⁿ).
Step 4
Heuristics for large-scale routing
Use nearest-neighbor construction plus 2-opt or genetic-algorithm refinement to get a fast, near-optimal tour.
What Interviewer Expects
- State the goal: shortest tour visiting every city exactly once, returning to start
- Explain why brute force is factorial and infeasible beyond small n
- Describe at least one exact method (Held-Karp DP) and one heuristic (nearest-neighbor, 2-opt)
- Correctly classify TSP as NP-hard and explain what that means practically
Common Mistakes
- Confusing NP-hard with "impossible to solve" rather than "no known polynomial-time exact algorithm"
- Proposing brute force as a practical solution for realistic city counts
- Not distinguishing the decision version (is there a tour under length L) from the optimization version
- Forgetting that TSP requires returning to the starting city, unlike a simple Hamiltonian path
Best Answer (HR Friendly)
“The traveling salesman problem is about finding the shortest route that visits a set of places exactly once and comes back to the start. I know it is a classic hard problem because checking every possible order gets unmanageable fast, so in practice I would reach for a smart heuristic that gets a very good route quickly instead of guaranteeing the perfect one.”
Code Example
import itertools
def tsp_held_karp(dist):
n = len(dist)
C = {(frozenset([0, k]), k): (dist[0][k], [0, k]) for k in range(1, n)}
for subset_size in range(3, n + 1):
new_C = {}
for subset in itertools.combinations(range(1, n), subset_size - 1):
subset = frozenset(subset) | {0}
for k in subset - {0}:
best = min(
(C[(subset - {k}, m)][0] + dist[m][k], C[(subset - {k}, m)][1] + [k])
for m in subset - {0, k}
)
new_C[(subset, k)] = best
C = new_C
full = frozenset(range(n))
return min(C[(full, k)][0] + dist[k][0] for k in range(1, n))Follow-up Questions
- How does the Held-Karp algorithm improve on brute force, and what is its time complexity?
- What is the 2-opt heuristic, and how does it refine a nearest-neighbor tour?
- How does TSP relate to the Hamiltonian cycle problem?
- When would you accept an approximate TSP solution instead of an exact one in production?
MCQ Practice
1. What complexity class does the Traveling Salesman Problem belong to?
TSP is NP-hard; no known algorithm solves it exactly in polynomial time for all inputs.
2. What is the time complexity of the Held-Karp dynamic programming algorithm for TSP with n cities?
Held-Karp tracks shortest paths per (visited-subset, endpoint) pair, giving O(n² · 2ⁿ) time — exponential but far better than factorial.
3. What does the nearest-neighbor heuristic for TSP guarantee?
Nearest-neighbor always produces a valid tour quickly, but offers no guarantee of optimality — it can be far from the shortest tour.
Flash Cards
What must a TSP tour do? — Visit every city exactly once and return to the starting city, minimizing total distance.
What complexity class is TSP in? — NP-hard.
What does the Held-Karp algorithm reduce brute force to? — O(n² · 2ⁿ) instead of O(n!).
Name one heuristic used to approximate TSP. — Nearest-neighbor construction, often refined with 2-opt local search.