The travelling salesman: nearest neighbour Problem set B Answers

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

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

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

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

1. (a) 2520
2. (b) 25.2 days

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

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

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

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

1. (a) A: 64; B: 64; C: 72; D: 61; E: 64
2. (b) 61 km, tour D–C–E–B–A–D