Travelling Salesperson Problem Flashcards Preview

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

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

Tour

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

2

Classical problem

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

3

Practical problem

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

4

When to use edges b and c instead of direct a

b + c < a
(Arc lengths)

5

Table of least distances

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

6

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

7

What problem does MST upper bound work for?

The practical problem

8

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

9

What problem does MST lower bound work for?

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

10

How to know if your lower bound is the optimal solution

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

11

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

12

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