Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-11/problems/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.11

The travelling salesman: nearest neighbour Problem set A Worked solutions

Skills

  1. The table shows the distances in km between five towns. Use the nearest neighbour algorithm from C. Write down the tour and its length.

    ABCDEA–717238B7–151416C1715–1120D231411–4E816204–
    • From C: D 11, B 15, A 17, E 20. Nearest: D (11)
    • From D: E 4, B 14, A 23. Nearest: E (4)
    • From E: A 8, B 16. Nearest: A (8)
    • Return B to C (15).
    • 11 + 4 + 8 + 7 + 15 = 45

  2. The graph shows the distances in km between five towns. Use the nearest neighbour algorithm from A. Write down the tour and its length.

    619131581418111624ABCDE
    • From A: B 6, D 13, E 15, C 19. Nearest: B (6)
    • From B: C 8, D 14, E 18. Nearest: C (8)
    • From C: D 11, E 16. Nearest: D (11)
    • Return E to A (15).
    • 6 + 8 + 11 + 24 + 15 = 64

  3. The graph shows the distances in km between five towns. A route is A–B–D–C–E–A.

    102417111516186148ABCDE

    1. (a) Show that the route is a Hamiltonian cycle and find its length.

      • Towns used: A, B, D, C, E, each once, then back to A.
      • 10 + 16 + 6 + 14 + 11 = 57

    2. (b) What does the length tell you about the shortest route that visits every town and returns?

      • 57 is an upper bound.
      • Shortest ≤ 57 km; it may be shorter.

  4. The table shows the distances in km between six towns. Use the nearest neighbour algorithm from B. Write down the tour and its length.

    ABCDEFA–121751123B12–1331019C1713–161824D5316–620E1110186–21F2319242021–
    • From B: D 3, E 10, A 12, C 13, F 19. Nearest: D (3)
    • From D: A 5, E 6, C 16, F 20. Nearest: A (5)
    • From A: E 11, C 17, F 23. Nearest: E (11)
    • From E: C 18, F 21. Nearest: C (18)
    • Return F to B (19). 3 + 5 + 11 + 18 + 24 + 19 = 80

  5. A courier must visit 7 towns, starting and finishing at the same town. Every pair of towns is joined by a road. A tour and its reverse count as one tour.

    1. (a) How many different tours are there?

      • (7 − 1)! ÷ 2 = 720 ÷ 2 = 360.

    2. (b) A computer checks 10 000 tours every second. How long would it take to check every tour for 14 towns? Give your answer in hours to 3 significant figures.

      • Tours: (14 − 1)! ÷ 2 = 3 113 510 400.
      • Seconds: 3 113 510 400 ÷ 10 000 = 311351.04.
      • Hours: 311351.04 ÷ 3600 = 86.5.

In context

  1. A bakery van leaves the depot A, delivers to five shops B to F and returns to A. The table shows the distances in km. Use the nearest neighbour algorithm from A. Write down the route and its length, and state what the length tells you about the shortest possible route.

    ABCDEFA–152161920B15–221158C2122–231418D61123–137E1951413–12F20818712–
    • From A: D 6, B 15, E 19, F 20, C 21. Nearest: D (6)
    • From D: F 7, B 11, E 13, C 23. Nearest: F (7)
    • From F: B 8, E 12, C 18. Nearest: B (8)
    • From B: E 5, C 22. Nearest: E (5)
    • Return C to A (21). 6 + 7 + 8 + 5 + 14 + 21 = 61
    • Upper bound: shortest ≤ 61 km.

  2. A tour guide visits six villages A to F and returns to her start. The table shows the distances in km.

    ABCDEFA–122011518B12–17161915C2017–9227D11169–1310E5192213–6F18157106–

    1. (a) Use the nearest neighbour algorithm from A. State the tour and its length.

      • A–E–F–C–D–B–A: 5 + 6 + 7 + 9 + 16 + 12 = 55

    2. (b) Use the nearest neighbour algorithm from E. State the tour and its length.

      • E–A–D–C–F–B–E: 5 + 11 + 9 + 7 + 15 + 19 = 66

    3. (c) State the best upper bound for the shortest route.

      • The smaller of 55 and 66 is 55.
      • Shortest route ≤ 55 km.

  3. A delivery driver finds a route of 55 km that visits every stop and returns to the depot, using the nearest neighbour algorithm. Later she finds a route of 51 km.

    1. (a) State the best upper bound for the shortest route.

      • Smaller of 55 and 51: 51.
      • Shortest ≤ 51 km.

    2. (b) Can the shortest route be 53 km? Explain.

      • 53 > 51, and a route of 51 km exists.
      • So the shortest route cannot be that long.

    3. (c) Can the shortest route be 45 km? Explain.

      • 45 < 51, so the upper bound does not rule it out.
      • An upper bound gives no information about how much shorter the shortest route is.

Stretch

  1. The graph shows the distances in km between five towns.

    9104382320242218ABCDE

    1. (a) Use the nearest neighbour algorithm from A. State the tour and its length.

      • A–E–D–B–C–A: 3 + 18 + 23 + 8 + 10 = 62

    2. (b) Find a Hamiltonian cycle shorter than your answer to part (a).

      • Try A–D–C–B–E–A: 4 + 24 + 8 + 20 + 3 = 59.
      • 59 < 62.

    3. (c) Does the nearest neighbour algorithm always give the shortest route? Use your answers to explain.

      • A shorter cycle exists, so the nearest neighbour length 62 is only an upper bound.

  2. The table shows the distances in km between five towns A to E. A salesman may start at any town.

    ABCDEA–2224143B22–171320C2417–129D141312–4E32094–

    1. (a) Use the nearest neighbour algorithm from each town in turn. Write down the length of each tour.

      • A: A–E–D–C–B–A = 58
      • B: B–D–E–A–C–B = 61
      • C: C–E–A–D–B–C = 56
      • D: D–E–A–B–C–D = 58
      • E: E–A–D–C–B–E = 66

    2. (b) State the best upper bound and the tour that gives it.

      • Smallest is 56, from C.
      • Shortest route ≤ 56 km.

jmaths.xyz · AI HL · AHL 1.11 The travelling salesman: nearest neighbour