Chapter 5 The Travelling Salesman Problem Flashcards
State the algorithm that allows us to find an upper bound for the practical salesmen problem?
Why won’t this work with the CSP?
It won’t work with the CSP because by definition vertices will be visited more than once
State the algorithm which can be used to find a lower bound to the classical salesman’s problem?
How do you make it work for the practical salesman’s problem?
This algorithm only works for the classical problem. To make it work for the practical problem you need to apply the algorithm to a table of least distances
State the nearest neighbour algorithm
How can you find the optimum problem in a travelling salesman problem?
If you have lower bound of 23 and then you find a solution which a value of 23 then that must be a optimal solution
What is a tour?
A tour is a walk which visits every vertex which returns to its starting vertex
A tour could visit every vertex more than once but if every vertex is visited only once then it is a hamiltonian cycle
Hat is a walk?
A walk in a network is a finite sequence of edges such that the end vertex of 1 edge is the start vertex of the next
What is the classical problem?
In the classical problem, each vertex must be visited exactly once before returning to the start
What is the practical problem?
In the practical problem, each vertex must be visited at least once before returning to the start
What is the able of least distances?
A table which shows the shortest path between every vertex
What is the problem with the finding a lower bound algorithm and how can it be overcome?
It only works for the classical problem
To make it work for the practical problem you need to apply the algorithm to a table of least distances
What is a Residual Spanning Tree?
The residual spanning tree is the MST for the resulting network after removing a vertex
Explain the exam technique tip in 5.3?
When finding shortcuts you can draw the spanning tree as a straight line
Which bound do you use if you are asked to write down your upper and lower bounds?
If asked to write an inequality the lower bound will be < if it doesn’t represent a hamiltonian cycle (as that can’t be a solution)
The upper bound will always be ≤
What is the point of the nearest neighbour algorithm?
Finding shortcuts takes a long time so use this instead
What will the nearest neighbour alg generally give you as a solution?
A tour
And not a optimal solution
State the triangle inequality
