Menu
Sign up Sign in

AI HL · AHL 1

Graph Theory

0 of 43 skills done

0
AHL 1.11

The travelling salesman: nearest neighbour

AHL 1.11

The travelling salesman: nearest neighbour

Target: I can say what a Hamiltonian cycle is, check that a route is one and find its length. (+3 more)

By the end of this section

Key points

The travelling salesman problem

  • The travelling salesman problem asks for the shortest route that visits every vertex and returns to the start.
  • A Hamiltonian cycle visits every vertex exactly once and returns to the start. A cycle on n vertices has n edges.
  • On a complete graph (every pair of vertices joined) every order of the vertices is a Hamiltonian cycle. The number of cycles grows very fast, so we use a quick method to get a good route.
  • On a complete graph with n vertices there are (n − 1)! ÷ 2 different Hamiltonian cycles. Fix the start, order the other n − 1 vertices, then halve because a tour and its reverse are the same.

Nearest neighbour algorithm

  • Start at the vertex the question names.
  • Go to the nearest vertex that you have not visited yet. Repeat.
  • When every vertex is visited, return to the start by the direct edge, even if that edge is long.
  • Write the tour and add the weights. In a table, cross out each column once you have visited that vertex.

Upper bounds

  • The length of any Hamiltonian cycle is an upper bound: the shortest route is at most this long.
  • Say "at most". The nearest neighbour length is not the shortest route, which may be shorter.
  • Different start vertices can give different tours. Try more than one start and take the smallest length as the best upper bound.

Explore: the travelling salesman problem

Nearest neighbour gives an upper bound for the shortest tour. The deleted vertex method gives a lower bound. Run both and see the shortest tour squeezed between them.

Start at

Upper bounds found
Lower bounds found

  1. Run nearest neighbour from each vertex in turn. Do you always get the same length? Which length would you quote as the upper bound?
  2. Delete a different vertex each time. Which gives the best lower bound: the largest or the smallest? Why?
  3. Why does a tour have to use two edges at the deleted vertex? Why must the rest of the tour be at least as long as the minimum spanning tree?
  4. On Graph 4 find a lower bound and an upper bound that are equal. What does that tell you about the tour?

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.
Nearest neighbour from B

A salesman must visit the five towns A to E and return to his start. The graph shows the distances in km. Use the nearest neighbour algorithm from B. Write down the tour and its length.

137154561412311ABCDE
Working
  1. Move 1

    B → C (5)

    From B, the unvisited vertices are C (5), D (6), A (13), E (14). The nearest is C.

  2. Move 2

    C → E (3)

    From C, the unvisited vertices are E (3), A (7), D (12). The nearest is E.

  3. Move 3

    E → A (4)

    From E, the unvisited vertices are A (4), D (11). The nearest is A.

  4. Move 4

    A → D (15)

    From A, the unvisited vertices are D (15). The nearest is D.

  5. Return

    D → B (6)

    Every vertex is visited. Go back to the start along the direct edge, even if it is long.

  6. 137154561412311ABCDE
    Length

    B–C–E–A–D–B: 5 + 3 + 4 + 15 + 6 = 33

    The tour has length 33. This is an upper bound for the shortest route.

Video walkthrough coming
Two starting vertices

The table shows the distances in km between six towns A to F. A van driver visits every town and returns to the start. Use the nearest neighbour algorithm from A, then from D. State the best upper bound for the length of the shortest route.

ABCDEFA–5971210B5–1831419C918–4811D734–1716E1214817–20F1019111620–
Working
  1. From A

    A–B–D–C–E–F–A: 5 + 3 + 4 + 8 + 20 + 10 = 50

    Each time go to the nearest unvisited town, then return: A to B (5); B to D (3); D to C (4); C to E (8); E to F (20); back to A (10).

  2. From D

    D–B–A–C–E–F–D: 3 + 5 + 9 + 8 + 20 + 16 = 61

    The same method from D: D to B (3); B to A (5); A to C (9); C to E (8); E to F (20); back to D (16).

  3. Best bound

    min(50, 61) = 50

    The shortest route is at most 50. The start vertex changes the tour, so try more than one and take the smaller bound.

Video walkthrough coming
A Hamiltonian cycle as an upper bound

The graph shows the distances in km between five towns. A courier takes the route A–C–E–B–D–A. Show that this route visits every town once and returns to A, and find its length. What does this tell you about the shortest route that visits every town?

597122482141914ABCDE
Working
  1. Check

    A–C–E–B–D–A

    Each of A, B, C, D, E appears once and the route returns to A. It is a Hamiltonian cycle.

  2. Edges

    AC = 9; CE = 19; EB = 21; BD = 8; DA = 7

    Read each weight from the graph.

  3. 597122482141914ABCDE
    Length

    9 + 19 + 21 + 8 + 7 = 64

    Every Hamiltonian cycle gives an upper bound.

  4. Meaning

    Shortest route ≤ 64

    The shortest route is at most 64. It could be shorter.

Video walkthrough coming
What an upper bound tells you

A courier uses the nearest neighbour algorithm from the depot and finds a route of length 53 km that visits every stop and returns. By trying another route she finds one of length 49 km. A colleague says the shortest possible route is 52 km. State the best upper bound for the shortest route and say whether the colleague can be right.

Working
  1. Bounds

    Shortest ≤ 53 and shortest ≤ 49

    Each route found is an upper bound. The smaller is better: 49 km.

  2. The claim

    52 > 49

    A route of 49 km exists, so the shortest route cannot be 52 km. The colleague is wrong.

  3. What is left

    Shortest route ≤ 49

    An upper bound does not say how close the shortest route is. It could be much shorter.

Video walkthrough coming
How many tours?

A courier must visit six towns, starting and finishing at the depot, which is one of the six towns. Every pair of towns is joined by a road, so the graph is complete. A tour and the same tour in the reverse direction count as one tour. How many different tours are there?

Working
  1. Fix the start

    5! = 120

    The depot is the start. The other 5 towns can be put in any order.

  2. Remove the reverses

    120 ÷ 2 = 60

    A–B–C–D–E–F–A and A–F–E–D–C–B–A are the same tour. Each tour was counted twice.

  3. The rule

    (n − 1)! ÷ 2 = (6 − 1)! ÷ 2 = 60

    For n towns there are (n − 1)! ÷ 2 different tours.

  4. Why it matters

    15 towns: 14! ÷ 2 = 43 589 145 600

    Checking every tour is not practical for more than a few towns. That is why we find an upper and a lower bound instead.

Video walkthrough coming