The Travelling Salesman problem

The Travelling Salesman problem Flashcards

Spec 3.2 · Edexcel A-Level Further Maths: Flashcards

Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.

12 cards

Tap a card to flip it. Swipe right if you knew it, left if not.

See all 12 cards
What does the classical TSP require?
A Hamiltonian cycle: every vertex visited exactly once, returning to the start, on a complete network.
How does the practical TSP differ?
Every vertex is visited at least once, so vertices and arcs can be repeated.
What is the triangle inequality?
The direct distance between two vertices is no more than the distance via a third.
How do you make a network complete?
Use the least distance between each pair of vertices as the arc weight.
What does any tour give?
An upper bound for the shortest tour.
State the nearest neighbour algorithm.
Go to the nearest unvisited vertex each time, then return to the start.
Upper bound from a minimum spanning tree?
Twice the weight of the tree.
What is a shortcut?
A direct arc replacing part of a route, which can improve the upper bound.
Method for a lower bound?
Delete a vertex, find the MST of the rest, then add the two shortest arcs at the deleted vertex.
How do you choose the best lower bound?
Try deleting different vertices and take the largest value.
How do you write the final answer using bounds?
Lower bound ≤ shortest tour ≤ best upper bound.
When is a tour known to be optimal?
When the lower bound equals its length.

Flashcards