The Travelling Salesman problem 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.