D2 June 2006 Q1
1.
(a) State Bellman’s principle of optimality. (1)
(b) Explain what is meant by a minimax route. (1)
(c) Describe a practical problem that would require a minimax route as its solution. (2)
| Scheme | Marks |
|---|---|
| Any part of an optimal path is itself optimal | B1 |
| (1) |
Notes
B1 cao (“port”, “section”, OK; “arc”, “stage”, activity”, “event”, not)
| Scheme | Marks |
|---|---|
| The route chosen such that the maximum arc length is as small as possible | B1 |
| (1) |
Notes
B1 cao (not min of max rate, not minimize largest arc)
| Scheme | Marks |
|---|---|
| e.g. Maximising freight by minimising fuel needed when planning multiple stage light aircraft journey | B2, 1, 0 |
| (2) | |
| (4 marks) |
Notes
B2 cao
B1 cloze “Bod” gets B1