Decision Maths: 5. The Travelling Salesman Problem Flashcards
Walk Defintion
A finite sequence of edges such that the end vertex or one edge is the start vertex of the next, basically can repeat vertices and edges.
Tour Definition
A walk that visits every vertex, returning to its start vertex, is called a tour
(A tour could visit some vertices more than once)
How many times can a Tour visit some vertices
A tour could visit some vertices more than once
Hamiltonian Cycle Defintion
A Hamiltonian Cycle is a tour that visits every vertex exactly once
What is the difference between the two variations of the travelling salesmen problem (Classic Travelling Salesman and Practical Travelling Salesman)
- In the classical problem, each vertex must be visited exactly once before returning to the start.
- In the practical problem, each vertex must be visited at least once before returning to the start.
How can you make the classical and practical travelling salesman problems equivalent
If you convert the network into a complete network of least distances, the classical and practical travelling salesman problems are equivalent.
To create a complete network of least distances you ensure that the triangle inequality holds for all triangles in the network.
(The triangle inequality states:
The longest side of any triangle ≤ the sum of the two shorter sides)
What can you do if you have a network where the triangle inequality does not hold in one or more triangles?
If you have a network where the triangle inequality does not hold in one or more triangles, you simply replace the longest arc in those triangles by the sum of the two smaller ones, thereby creating a network which shows the shortest distances.
What is a Table of Least Distances
The distance matrix for a complete network of least distances is called a table of least distances. It shows the shortest path between any two points in the network.
How do you use a Minimum Spanning Tree (MST) to find an Upper Bound
- Find a MST for a network using Prims or Kruskal’s
- Double this (in effect you are retracing your steps along each edge)
- Seek ‘shortcuts’ this makes use of some of the omitted arcs to enable you to bypass some of the repeats and improve your upper bound.
How to use a Minimum Spanning Tree (MST) to find a Lower Bound (LB)
You can use this method to find a LB for the classical problem.
- Remove each vertex in turn (or whichever you are directed to remove)
- Find the residual minimum spanning tree (RMST)
- Add to the RMST the ‘cost’ of reconnecting the deleted vertex by the two shortest, distinct arcs
- 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 known to be
- If the LB is a Hamiltonian Cycle, or if the LB is the same as the UP you have found an optimal solution.
What is an alternative approach to finding the Upper Bound (UB) for large networks
The method of finding a minimum spanning tree and selecting shortcuts is inefficient and difficult for large networks, an alternative approach is to use the nearest neighbour algorithm.
How do you carry out the Nearest Neighbour Algorithm to find the Upper Bound (UB)
- Select each vertex in turn as a starting point
- Go to the nearest vertex which has not yet been visited.
- Repeat step 2 until all vertices have been visited and then return to the start vertex using the shortest route.
- Once all the vertices have been used as the starting vertex, select the tour with the smallest length as the upper bound.
What are the differences between the nearest neighbour algorithm and Primm’s algorithm
- Nearest neighbour finds a Hamiltonian cycle, Primm’s finds a minimum spanning tree
- Nearest neighbour finds the closest vertex to the vertex last chosen, Primm’s finds the closest vertex to any of the vertices already selected.
