Travelling Salesperson Problem Flashcards Preview

A Level Further Maths Decision 1 > Travelling Salesperson Problem > Flashcards

Flashcards in Travelling Salesperson Problem Deck (12)
Loading flashcards...


A walk which visits every vertex at least once and returns to its starting vertex


Classical problem

Each vertex must be visited exactly once before returning to the start vertex


Practical problem

Each vertex must be visited at least once before returning to the start vertex


When to use edges b and c instead of direct a

b + c < a
(Arc lengths)


Table of least distances

A distance matrix where paths are included where there isn’t a direct edge


MST Upper bounds

1. Find an MST and draw
2. Double it so completing the cycle is guaranteed
3. Look for non-included arcs that are shorter than the repeated arcs it could replace


What problem does MST upper bound work for?

The practical problem


MST Lower bounds

1. Remove each vertex in turn along with the arcs that connect it
2. Find a residual minimum spanning tree (RMST)
3. Add the cost of the shortest 2 distinct arcs that connect the missed vertex to the tree
4. Use the one with the highest value


What problem does MST lower bound work for?

The classical problem, the practical if it is on a table of least distances


How to know if your lower bound is the optimal solution

If you have a Hamiltonian cycle or the same as the upper bound


Nearest Neighbour Upper Bounds

1. Select each vertex in turn as a starting point
2. Go to the nearest vertex which has not yet been visited
3. Repeat the next step until all vertices have been connected and return to the start vertex with the shortest route
4. Choose the shortest tour


Nearest Neighbour Upper Bounds workings

Very similar to Prim's algorithm, just choose the shortest distance in the column that is latest to be labelled and then the route back to the start
Then draw your graph