Travelling Salesman Problem

The Travelling Salesman Problem (TSP) asks: what is the shortest route that visits every vertex exactly once and returns to the starting vertex? Unlike the Chinese Postman (which traverses every edge), the TSP visits every vertex. It is one of the most famous problems in mathematics and computer science.

---

Why the TSP is Hard

The TSP is an NP-hard problem. For $n$n vertices, there are $(n-1)!/2$(n−1)!/2 possible tours (for an undirected complete graph). This grows extremely fast:

$n$n	Tours
4	3
5	12
10	181,440
20	$> 10^{16}$>1016

For large $n$n, finding the optimal solution by brute force is impractical. Instead, we use bounds and heuristics.

---

Upper Bounds: Nearest Neighbour Algorithm

The nearest neighbour algorithm provides an upper bound for the TSP.

Procedure

1. Start at a given vertex.
2. Move to the nearest unvisited vertex.
3. Repeat until all vertices are visited.
4. Return to the starting vertex.

Worked Example

Distance matrix for A, B, C, D: