# Decision - Travelling salesman problem Flashcards

What is a heuristic algorithm?

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

What is a tour?

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

What is the difference between a tour and a cycle?

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

What is a tour that visits every vertex exactly once?

A hamiltonian cycle

What is the practical travelling salesman problem?

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

What is the classical travelling salesman problem?

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

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

- Turn the network into a complete network/matrix of least distances
- Find the minimum spanning tree for the network (either by using Prim’s or Kruskal’s algorithm). This ensures each vertex is included.
- 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
- 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)

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

- Remove each vertex in turn, together with its arcs
- 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) - Add to the RMST the “cost” of reconnecting the deleted vertex
**by the 2 shortest, distinct, arcs**and note the totals **The greatest of these totals is used for the lower bound**- Make the lower bound as high as possible to reduce the interval in which the optimal solution is contained
- 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

What is a residual spanning tree?

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

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

- Select each vertex in turn as a starting point
- Go to the nearest vertex
**which has not been visited yet** - 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** - Once all vertices have been used as the starting vertex, select the tour with the smallest length as the upper bound

What does the triangle inequality state?

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

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

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

How do you set up a travelling salesman problem?

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