5. The Travelling Salesman Problem Flashcards
Define the term tour
A walk which visits every vertex and then returns to start vertex
What are the two variations of the travelling salesman problem?
- Classical
2. Practical
What is the difference between the classical and practical problem?
The classical problem requires the vertices to be visited exactly once, but the practical problems requires each vertex to be visited at least once
What does the triangle inequality state?
longest side ≤ sum of two shorter sides
How do you find the upper bound for the practical problem?
Using Prim’s or Kruskal’s algorithm to find the MST
How is the initial upper bound found?
Finding weight of MST and doubling it
How do you improve the initial upper bound?
Look for shortcuts
Which is the better upper bound solution: the lowest or the highest value?
Lowest - reduces interval in which optimal solution is contained
What is a RMST (Residual Minimum Spanning Tree)?
The MST for resulting network after removing a vertex
How do you find the lower bound for the classical problem?
Using the RMST method
What are the steps to the RMST method?
- Remove each vertex in turn, together with its arcs
- Find the RMST and its length
- Add the cost of deleting the vertex to the RMST by the two shortest, distinct arcs and note the totals
- The greatest of the totals is used for the lower bound
What is are the two scenarios for when the optimal solution is found?
- A Hamiltonian cycle for the lower bound
2. The lower bound is the same as the upper bound
What is the nearest neighbour algorithm used for?
Finding the upper bound
What are the steps to the nearest neighbour algorithm?
- Select each vertex in turn as the starting point
- Go to the nearest vertex that 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 vertices have been used as the starting vertex, select the tour with the smallest length as the upper bound
