Chapter 5: The Travelling Salesman Problem

Question 1

What does the travelling salesman problem find?

Answer 1

The travelling salesman problem involves finding a tour( a walk which visits every vertex and ends at it starting vertex) of minimum total weight

Question 2

What is the classical travelling salesman problem?

Answer 2

Each vertex is visited exactly once before returning to the start

Question 3

What is the practical travelling salesman problem?

Answer 3

Each vertex must be visited at least once before returning to its starting vertex

Question 4

Can you always find the optimal solution for the travelling salesman problem?

Answer 4

There is no efficient algorithm so instead we can find an upper bound and a lower bound for the solution and then the optimal solution will be in between the upper and lower bound

Question 5

What two methods can we use to work out an upper bound?

Answer 5

1) use a minimum spanning tree

2) use the nearest neighbour algorithms

Question 6

How to use a minimum spanning tree method to find an upper bound?

Answer 6

1) find a minimum spanning tree using either kruskal’s or prim’s as this guarantees each vertex is visited at least once
2) we need to double this so it is guaranteed that we complete the cycle
3) we can then seek shortcuts in between vertices to decrease the upper bound

The aim is to make the initial upper bound as low as possible to reduce the interval in which the optimal solution lies in

Question 7

How to use the nearest neighbour algorithm to find an upper bound?

Answer 7

1) select each vertex in turn as a starting point
2) go to the nearest vertex that hasn’t been selected or visited yet
3) repeat this until all vertices have been visited and then return directly to the start vertex
4) once all vertices have been used as a starting point, choose the one with the lowest length to use as an upper bound

Question 8

How to use the minimum spanning tree method to find an upper lower bound?

Answer 8

1) remove each vertex in turn with its arcs
2) find the residual minimum spanning tree and its length
3) add the RMST to two connecting shortest vertices to the vertex we removed
4) Do this for all the vertices and use the greatest total (to reduce interval containing optimal solution)

Optimal solution is if the lower bound gives an hamiltonian cycle