The travelling salesman: nearest neighbour Problem set A Answers

C–D–E–A–B–C; 45 km

A–B–C–D–E–A; 64 km

1. (a) Each town once, returns to A; length 57 km
2. (b) The shortest route is at most 57 km.

B–D–A–E–C–F–B; 80 km

1. (a) 360
2. (b) 86.5 hours

A–D–F–B–E–C–A; 61 km; the shortest route is at most 61 km

1. (a) A–E–F–C–D–B–A; 55 km
2. (b) E–A–D–C–F–B–E; 66 km
3. (c) 55 km

1. (a) 51 km
2. (b) No: a route of 51 km exists, so the shortest is at most 51.
3. (c) We cannot tell. The upper bound allows it, but it may or may not be possible.

1. (a) A–E–D–B–C–A; 62 km
2. (b) A–D–C–B–E–A; 59 km (or the same cycle reversed)
3. (c) No. The nearest neighbour tour is 62 km but a route of 59 km exists.

1. (a) A: 58; B: 61; C: 56; D: 58; E: 66
2. (b) 56 km, tour C–E–A–D–B–C