Bounds for the travelling salesman problem

Bounds for the travelling salesman problem Flashcards

Spec 3.3–4 · Edexcel International A Level 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 is an upper bound for the TSP?
The length of an actual tour; the shortest tour cannot be longer.
What is a lower bound for the TSP?
A value that the shortest tour cannot be less than.
What does it mean if the upper and lower bounds are equal?
The tour found is the shortest possible (optimal).
How do you make an incomplete network complete?
Join every missing pair by an arc whose length is the shortest distance between them.
State the nearest neighbour algorithm.
Start at a vertex, always go to the nearest unvisited vertex, then return to the start.
Does the nearest neighbour algorithm give the shortest tour?
Not always. It gives an upper bound.
How do you get the best nearest neighbour upper bound?
Start from each vertex in turn and take the smallest tour.
How does an MST give an upper bound?
A walk round the tree uses every arc twice, so a tour of length 2×2\times the MST weight exists.
What is a shortcut?
Going directly to the next new vertex instead of revisiting a vertex, shortening the tour.
State the steps for a lower bound.
Delete a vertex, find the MST of the rest, add the two shortest arcs at the deleted vertex.
Why is the deleted-vertex method a lower bound?
Every tour has two arcs at the vertex, and the rest is at least as long as the MST of the others.
Which deleted vertex gives the best lower bound?
The one giving the largest value.

Flashcards