The travelling salesman problem (TSP) asks for the shortest possible route that visits every vertex exactly once and returns to the starting vertex. In IB Mathematics: Applications and Interpretation, it is HL-only content within AHL 3.16: Tree and cycle algorithms.
The Reasoning and Method
A TSP network is represented by a weighted complete graph, where vertices represent locations and edge weights represent distance, time, or cost. The required route is a minimum-weight Hamiltonian cycle: it includes every vertex once before returning to its starting point.
If the original graph is incomplete, a table of shortest distances between every pair of vertices may first be constructed. This converts the practical network into the complete graph needed for the classical TSP.
IB Mathematics AI uses bounds because checking every possible Hamiltonian cycle becomes inefficient as the number of vertices increases.
| Method | Purpose and procedure |
|---|---|
| Nearest-neighbour algorithm | Gives an upper bound. Start at a vertex, repeatedly travel to the nearest unvisited vertex, then return to the start. |
| Deleted-vertex algorithm | Gives a lower bound. Delete one vertex, find a minimum spanning tree for the remaining graph, then add the two least-weight edges connecting the deleted vertex. |
For example, suppose nearest neighbour produces a route of length , while the deleted-vertex method gives . If the true minimum length is , then