D1, C5 - The Travelling Salesman Problem Flashcards
What is the Travelling Salesman problem
Visiting every vertex / node in a network, starting and finishing at the same vertex
How is the Travelling Salesman problem different to route inspection / the Chinese Postman problem
Travelling Salesman - visit every vertex and finish at start
Chinese Postman - traverse every arc
What is the Classical Travelling Salesman problem
Each vertex is visited only once
What is the Practical Travelling Salesman problem
Each vertex is visited at least once
What is a walk
Begins at a vertex, traverses arcs and ends at a vertex
What is a tour
Visits every vertex (could be more than once) and returns to the starting vertex
What type of tour visits every vertex once
Hamiltonian Cycle
Why do we use upper / lower bounds for travelling salesman problems
There is no efficient algorithm to solve the problems so you want to know how ‘good’ our solution is
What does it mean if you solution to a travelling salesman problem equals the lower bound
It is an optimal solution
What is a table of least distances
A table of the shortest distances between vertices
How do you know the values for a table of least distances
Inspection
How would you find the minimum spanning tree when given a network
Prim’s algorithm
OR
Kruskal’s algorithm
How would you find the minimum spanning tree when given a (least) distance table
Prim’s algorithm
How do you find the upper bound for the travelling salesman problem
Weight of upper bound x 2
How do you find better solutions than the upper bound of the travelling salesman problem
Look for shortcuts
What are the steps to find the lower bound using a minimum spanning tree
1) Remove a vertex
2) Find the residual minimum spanning tree
3) Add back the removed vertex by using the two shortest arcs
4) OPTIONAL, you can: Repeat steps 1-3, removing different vertices and pick the solution with the highest weight. If the solution is a Hamiltonian Cycle (or UB = LB), then have found an optimal solution
What is a residual minimum spanning tree
A spanning tree of the remaining vertices when one is removed
You have found two lower bounds, 678m and 712m, which is the better lower bound and why
712m is the better lower bound since we want the optimal solution interval (LB to UB) to be as small as possible
(712 is the biggest)
The lower bound is 712m and does not form a Hamiltonian Cycle while the upper bound is 1093m, what is the smallest interval that must contain the optimal route
712 < optimal solution <= 1093
The optimal solution can ONLY equal the lower bound if the LB is a Hamiltonian Cycle
When can the optimal solution = the LB
When the LB forms a Hamiltonian Cycle
What does the nearest neighbour algorithm do
Finds an upper bound
What are the steps for the nearest neighbour algorithm
1) Start with any vertex
2) Select the nearest vertex that has not yet been visited
3) Repeat until all vertices have been visited and make sure you return to starting vertex
4) Choose a different starting vertex and repeat steps 2-3
5) When all vertices have been selected as starting vertices, choose the tour with the lowest weight as an upper bound
Why do we use the nearest neighbour algorithm instead of the minimum spanning tree method
For very large networks, the MST would take ages
When performing the nearest neighbour algorithm (similar to Prim’s), why don’t you cross out the row for the starting vertex
Because you need to get back to the start
