Travelling Salesperson Problem

Question 1

Tour

Answer 1

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

Question 2

Classical problem

Answer 2

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

Question 3

Practical problem

Answer 3

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

Question 4

When to use edges b and c instead of direct a

Answer 4

b + c < a

Arc lengths

Question 5

Table of least distances

Answer 5

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

Question 6

MST Upper bounds

Answer 6

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

Question 7

What problem does MST upper bound work for?

Answer 7

The practical problem

Question 8

MST Lower bounds

Answer 8

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

Question 9

What problem does MST lower bound work for?

Answer 9

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

Question 10

How to know if your lower bound is the optimal solution

Answer 10

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

Question 11

Nearest Neighbour Upper Bounds

Answer 11

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

Question 12

Nearest Neighbour Upper Bounds workings

Answer 12

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