Bounds for the travelling salesman problemEdexcel International A Level Maths: Flashcards

What these 12 flashcards ask

What is an upper bound for the TSP?
What is a lower bound for the TSP?
What does it mean if the upper and lower bounds are equal?
How do you make an incomplete network complete?
State the nearest neighbour algorithm.
Does the nearest neighbour algorithm give the shortest tour?
How do you get the best nearest neighbour upper bound?
How does an MST give an upper bound?
What is a shortcut?
State the steps for a lower bound.
Why is the deleted-vertex method a lower bound?
Which deleted vertex gives the best lower bound?

Exam questions on Bounds for the travelling salesman problem

A complete network has five vertices $P$ , $Q$ , $R$ , $S$ and $T$ , with lengths $PQ=14$ , $PR=10$ , $PS=17$ , $PT=9$ , $QR=11$ , $QS=8$ , $QT=15$ , $RS=12$ , $RT=13$ and $ST=16$ .
Apply the nearest neighbour algorithm starting at $P$ . Write down the tour and its length, and state what this tells you about the shortest tour.2 marks
A complete network has five depots $V$ , $W$ , $X$ , $Y$ and $Z$ , with lengths $VW=11$ , $VX=7$ , $VY=9$ , $VZ=14$ , $WX=6$ , $WY=13$ , $WZ=10$ , $XY=8$ , $XZ=12$ and $YZ=15$ . A lower bound for the travelling salesman problem is found by deleting vertex $V$ .
Find the lower bound for the length of the shortest tour from deleting $V$ , and explain why it is a lower bound.2 marks
A delivery firm has five depots $A$ to $E$ . The only direct roads and their lengths in km are $AB=7$ , $BC=5$ , $CD=6$ , $DE=4$ and $BE=9$ . A driver must visit every depot and return to the start, and may pass through a depot more than once.
Find the shortest distances between $A$ and $D$ , between $B$ and $D$ , and between $C$ and $E$ .3 marks

Written by the Exaim team, led by Shaun Daswani (Head of Upper Secondary, Improve ME Institute; MSc Financial Mathematics, Imperial College London; BSc, UCL) and Jason Daswani (operational lead, Improve ME Institute; LSE).