Decision - Travelling salesman problem

Question 1

What is a heuristic algorithm?

Answer 1

An algorithm which will find a good solution, however it may not necessarily be the best solution. Such as the travelling salesman problem

Question 2

What is a tour?

Answer 2

A walk which visits every vertex, returning to its starting vertex

Question 3

What is the difference between a tour and a cycle?

Answer 3

A tour must visit every vertex, but it may also visit vertices more than once

Question 4

What is a tour that visits every vertex exactly once?

Answer 4

A hamiltonian cycle

Question 5

What is the practical travelling salesman problem?

Answer 5

The practical travelling salesman problem involves finding a tour of minimum total weight. Each vertex must be visited at least once before returning to the start

Question 6

What is the classical travelling salesman problem?

Answer 6

The classical travelling salesman problem involves finding a hamiltonian cycle of minimum total weight. Each vertex must be visited exactly once before returning to the start

Question 7

What are the steps to finding an upper bound for the practical travelling salesman problem?

Answer 7

1. Turn the network into a complete network/matrix of least distances
2. Find the minimum spanning tree for the network (either by using Prim’s or Kruskal’s algorithm). This ensures each vertex is included.
3. Double the weight of this minimum spanning tree (in effect you are retracing your steps) so that completing the cycle is guaranteed. This is you intial upper bound
4. Finally, seek “shortcuts” by inspection. Make use of some of the non-include arcs that enable you to bypass a longer repeat of some of the minimum spanning tree. This is your new lower upper bound. (This is often made easier by redrawing the minimum spanning tree in a straight line)

Question 8

What are the steps to finding a lower bound for the classical travelling salesman problem?

Answer 8

1. Remove each vertex in turn, together with its arcs
2. Find the residual minimum spanning tree and its length (RMST) by using Prim’s or Kruskal’s algorithm on the resulting network (often easier to use Prim’s from a matrix)
3. Add to the RMST the “cost” of reconnecting the deleted vertex by the 2 shortest, distinct, arcs and note the totals
4. The greatest of these totals is used for the lower bound
5. Make the lower bound as high as possible to reduce the interval in which the optimal solution is contained
6. You have found an optimal solution if the lower bound gives a hamiltonian cycle, or if the lower bound has the same value as the upper bound

Question 9

What is a residual spanning tree?

Answer 9

The minimum spanning tree for the resulting network after removing a vertex

Question 10

How can you use the nearest neighbout algorithm to find an upper bound for the travelling salesman problem?

Answer 10

1. Select each vertex in turn as a starting point
2. Go to the nearest vertex which has not been visited yet
3. Repeat step 2 from the last vertex chosen until all vertices have been visited and then return to the start vertex using the shortest route
4. Once all vertices have been used as the starting vertex, select the tour with the smallest length as the upper bound

Question 11

What does the triangle inequality state?

Answer 11

The longest side of any triangle ≤ the sum of the two shorter sides

Question 12

In what case are the practical and classical travelling salesman problems equivalent?

Answer 12

• If the network is complete
• The direct path between any 2 vertices is also the shortest distance between any 2 vertices

Question 13

How do you set up a travelling salesman problem?

Answer 13

Create a matrix of least distances, this makes the classical and practial problem the same and allows you to find both upper and lower bounds