D2 June 2019 Q1
1.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | – | 53 | 47 | 39 | 35 | 40 |
| B | 53 | – | 32 | 46 | 41 | 43 |
| C | 47 | 32 | – | 51 | 47 | 37 |
| D | 39 | 46 | 51 | – | 36 | 49 |
| E | 35 | 41 | 47 | 36 | – | 42 |
| F | 40 | 43 | 37 | 49 | 42 | – |
The table above shows the least distances, in km, between six towns, A, B, C, D, E and F. Jas needs to visit each town, starting and finishing at D, and wishes to minimise the total distance she travels.
(a) Starting at D, use the nearest neighbour algorithm to obtain an upper bound for the length of the route. You must state your route and its length. (2)
(b) Starting by deleting D, and all of its arcs, find a lower bound for the route length. (3)
| Scheme | Marks |
|---|---|
| NNA: D – E – A – F – C – B – D | M1 |
| 36 + 35 + 40 + 37 + 32 + 46 = 226 (km) | A1 |
| (2) |
Notes
a1M1: Nearest neighbour starting at D – must get to at least D – E – A – F – C – Or correct length stated
a1A1: Both route and length correctly stated (route must return to D) If double 226 A0. Do not isw.
| Scheme | Marks |
|---|---|
| RMST weight = 144 (km) | B1 |
| 144 + 39 + 36 = 219 (km) | M1 A1 |
| (3) | |
| 5 marks |
Notes
b1B1: CAO for RMST weight (either 144 or 35 + 40 + 37 + 32) – maybe implied by later working
b1M1: Adding 39 and 36 (the two least weighted arcs) to their RMST length – this mark maybe implied by the correct value for the lower bound
b1A1: CAO – if 219 seen without working then award all 3 marks in (b)