The travelling salesman problem
The shortest round trip through every city once: the explosion in the number of tours, construction by the nearest neighbour, improvement by swapping two edges, and the bound given by the minimum spanning tree.
- 23 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
Travelling salesman problem: what is it?
Show the answer
Given cities and the distances between them, find the shortest round trip that visits each city once and returns to its starting point.
It models delivery rounds, drilling circuit boards, the order of a machine's tasks. It is NP-hard: no polynomial algorithm is known.
Here are the distances between five cities. The nearest neighbour, from A, gives a tour of what length (return to A included)?
```text
A B C D E
A . 5 11 10 4
B 5 . 7 11 9
C 11 7 . 12 11
D 10 11 12 . 3
E 4 9 11 3 .`- 36
- 31
- 25
- 40
Show the answer
36
A → E (4), E → D (3), D → B (11, against 12 for C), B → C (7), C → A (11): 36. 31 is the optimal tour A-B-C-D-E-A; 25 forgets the return to A; 40 is the length of another tour, A-B-E-D-C-A.
With n cities and symmetric distances, there are … distinct tours: the starting city is fixed and the two directions of travel are not told apart.
Show the answer
With n cities and symmetric distances, there are (n − 1)! / 2 distinct tours: the starting city is fixed and the two directions of travel are not told apart.
(n − 1)! orders for the other cities, divided by 2 because a tour and its reverse have the same length. For 5 cities: 4! / 2 = 12.
Hamiltonian cycle: what is it?
Show the answer
A cycle of a graph that passes through every vertex exactly once.
A tour is a Hamiltonian cycle of the complete graph on the cities; its length is the sum of the distances of its edges.