Standard +0.3 This is a standard textbook dynamic programming problem with clear structure (staged network, maximin optimization). While it requires systematic application of DP algorithms and careful bookkeeping through multiple stages, it follows a well-defined procedure taught in D2 with no novel problem-solving required. The extension in part (e) adds minimal complexity as it's a straightforward sensitivity analysis on the optimal solution already found.
\end{figure}
The staged, directed network in Figure 2 represents a series of roads connecting 11 towns, \(\mathrm { S } , \mathrm { A }\), B, C, D, E, F, G, H, J and T. The number on each arc shows the weight limit, in tonnes, for the corresponding road. Janet needs to drive a truck from S to T, passing through exactly three other towns. She needs to find the maximum weight of the truck that she can use.
Write down the type of dynamic programming problem that Janet needs to solve.
Use dynamic programming to complete the table in the answer book.
Hence find the maximum weight of the truck Janet can use.
Write down the route that Janet should take.
Janet intends to ask for the weight limit to be increased on one of the three roads leading directly into T. Janet wishes to maximise the weight of her truck.
Determine which of the three roads she should choose and its new minimum weight limit.
Write down the maximum weight of the truck she would be able to use and the new route she would take.
Stage 3: \(G \to GT \to T = 8^*\); \(H \to HT \to T = 5^*\); \(J \to JT \to T = 6^*\)
M1 A1
b1M1: First stage completed, 3 rows, something in each cell. b1A1: CAO (condone missing \(*\))
Stage 2: \(D \to DH \to H = \min(10,5)=5^*\); \(E \to EG \to G = \min(9,8)=8^*\); \(E \to EH \to H = \min(8,5)=5\); \(E \to EJ \to J = \min(7,6)=6\); \(F \to FH \to H = \min(8,5)=5^*\); \(F \to FJ \to J = \min(5,6)=5^*\)
M1 A1 A1
b2M1: Second stage completed with 3 states, at least 6 rows. b2A1: Second stage any 2 states correct. b3A1: CAO all 3 states correct
Stage 1: \(A \to AD \to D = \min(8,5)=5\); \(A \to AE \to E = \min(6,8)=6^*\); \(B \to BE \to E = \min(17,8)=8^*\); \(B \to BF \to F = \min(9,5)=5\); \(C \to CD \to D = \min(10,5)=5^*\); \(C \to CF \to F = \min(10,5)=5^*\)
M1 A1ft A1
b3M1: Third stage completed with 3 states, at least 6 rows. b4A1ft: Any two states correct following through \(*\) values. b5A1: CAO all 3 states correct
Stage 0: \(S \to SA \to A = \min(11,6)=6\); \(S \to SB \to B = \min(8,8)=8^*\); \(S \to SC \to C = \min(12,5)=5\)
M1 A1
(10) b4M1: Fourth stage completed, 1 state, at least 3 rows. b6A1: CAO final state correct
Part (c)
Answer
Marks
Guidance
Answer
Marks
Guidance
Maximum weight \(= 8\) (tonnes)
B1
(1) c1B1: CAO (dependent on scoring all M marks in (b))
Part (d)
Answer
Marks
Guidance
Answer
Marks
Guidance
Route: \(S - B - E - G - T\)
B1
(1) d1B1: CAO (dependent on scoring all M marks in (b))
Part (e)(i)
Answer
Marks
Guidance
Answer
Marks
Guidance
Increase HT (by 5) to 10
B1
e1B1: Indication of either increasing HT by 5 or increasing HT to 10
Part (e)(ii)
Answer
Marks
Guidance
Answer
Marks
Guidance
Maximum weight \(= 10\) (tonnes)
B1
e2B1: CAO
New route: \(S - C - D - H - T\)
B1
(3) e3B1: CAO
Total: 16 marks
Dynamic Programming Mark Scheme
SC3 Minimum:
Answer
Marks
Guidance
Stage
State
Action
3
G
GT
H
HT
T
J
JT
T
2
D
DH
E
EG
G
EH
H
\(8+5=13^*\)
EJ
J
\(7+6=13^*\)
F
FH
H
FJ
J
\(5+6=11^*\)
1
A
AD
AE
E
\(6+13=19^*\)
B
BE
E
BF
F
\(9+11=20^*\)
C
CD
D
CF
F
\(10+11=21^*\)
0
S
SA
SB
B
\(8+20=28^*\)
SC
C
\(12+21=33\)
Route: \(S - B - F - J - T\)
SC4 Maximax:
Answer
Marks
Guidance
Stage
State
Action
3
G
GT
H
HT
T
J
JT
T
2
D
DH
E
EG
G
EH
H
\(\max(8,5)=8\)
EJ
J
\(\max(7,6)=7\)
F
FH
H
FJ
J
\(\max(5,6)=6\)
1
A
AD
AE
E
\(\max(6,9)=9\)
B
BE
E
BF
F
\(\max(9,8)=9\)
C
CD
D
CF
F
\(\max(10,8)=10^*\)
0
S
SA
SB
B
\(\max(8,17)=17^*\)
SC
C
\(\max(12,10)=12\)
SC5 Minimin:
Answer
Marks
Guidance
Stage
State
Action
3
G
GT
H
HT
T
J
JT
T
2
D
DH
E
EG
G
EH
H
\(\min(8,5)=5^*\)
EJ
J
\(\min(7,6)=6\)
F
FH
H
FJ
J
\(\min(5,6)=5^*\)
1
A
AD
AE
E
\(\min(6,5)=5^*\)
B
BE
E
BF
F
\(\min(9,5)=5^*\)
C
CD
D
CF
F
\(\min(10,5)=5^*\)
0
S
SA
SB
B
\(\min(8,5)=5^*\)
SC
C
\(\min(12,5)=5^*\)
SC6 Working Forwards S to T:
Answer
Marks
Guidance
Stage
State
Action
3
A
AS
B
BS
S
C
CS
S
2
D
DA
DC
C
\(\min(10,12)=10^*\)
E
EA
A
EB
B
\(\min(17,8)=8^*\)
F
FB
B
FC
C
\(\min(10,12)=10^*\)
1
G
GE
H
HD
D
HE
E
\(\min(8,8)=8\)
HF
F
\(\min(8,10)=8\)
J
JE
E
JF
F
\(\min(5,10)=5\)
0
T
TG
TH
H
\(\min(5,10)=5\)
TJ
J
\(\min(6,7)=6\)
SC7 Reversed States:
Answer
Marks
Guidance
Stage
State
Action
3
T
TG
TH
H
\(5^*\)
TJ
J
\(6^*\)
2
G
GE
H
HD
D
HE
E
\(\min(8,5)=5\)
HF
F
\(\min(8,5)=5^*\)
J
JE
E
JF
F
\(\min(5,6)=5^*\)
1
D
DA
DC
C
\(\min(10,5)=5^*\)
E
EA
A
EB
B
\(\min(17,8)=8^*\)
F
FB
B
FC
C
\(\min(10,5)=5^*\)
0
A
AS
B
BS
S
C
CS
S
Weight: \(8\) Route: \(S - B - E - G - T\)
# Question 6:
## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximin | B1 | **(1)** a1B1: CAO |
## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Stage 3: $G \to GT \to T = 8^*$; $H \to HT \to T = 5^*$; $J \to JT \to T = 6^*$ | M1 A1 | b1M1: First stage completed, 3 rows, something in each cell. b1A1: CAO (condone missing $*$) |
| Stage 2: $D \to DH \to H = \min(10,5)=5^*$; $E \to EG \to G = \min(9,8)=8^*$; $E \to EH \to H = \min(8,5)=5$; $E \to EJ \to J = \min(7,6)=6$; $F \to FH \to H = \min(8,5)=5^*$; $F \to FJ \to J = \min(5,6)=5^*$ | M1 A1 A1 | b2M1: Second stage completed with 3 states, at least 6 rows. b2A1: Second stage any 2 states correct. b3A1: CAO all 3 states correct |
| Stage 1: $A \to AD \to D = \min(8,5)=5$; $A \to AE \to E = \min(6,8)=6^*$; $B \to BE \to E = \min(17,8)=8^*$; $B \to BF \to F = \min(9,5)=5$; $C \to CD \to D = \min(10,5)=5^*$; $C \to CF \to F = \min(10,5)=5^*$ | M1 A1ft A1 | b3M1: Third stage completed with 3 states, at least 6 rows. b4A1ft: Any two states correct following through $*$ values. b5A1: CAO all 3 states correct |
| Stage 0: $S \to SA \to A = \min(11,6)=6$; $S \to SB \to B = \min(8,8)=8^*$; $S \to SC \to C = \min(12,5)=5$ | M1 A1 | **(10)** b4M1: Fourth stage completed, 1 state, at least 3 rows. b6A1: CAO final state correct |
## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum weight $= 8$ (tonnes) | B1 | **(1)** c1B1: CAO (dependent on scoring **all** M marks in (b)) |
## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Route: $S - B - E - G - T$ | B1 | **(1)** d1B1: CAO (dependent on scoring **all** M marks in (b)) |
## Part (e)(i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Increase HT (by 5) to 10 | B1 | e1B1: Indication of either increasing HT by 5 or increasing HT to 10 |
## Part (e)(ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Maximum weight $= 10$ (tonnes) | B1 | e2B1: CAO |
| New route: $S - C - D - H - T$ | B1 | **(3)** e3B1: CAO |
**Total: 16 marks**
# Dynamic Programming Mark Scheme
## SC3 Minimum:
| Stage | State | Action | Destination | Value |
|-------|-------|--------|-------------|-------|
| 3 | G | GT | T | $8^*$ |
| | H | HT | T | $5^*$ |
| | J | JT | T | $6^*$ |
| 2 | D | DH | H | $10+5=15^*$ |
| | E | EG | G | $9+8=17$ |
| | | EH | H | $8+5=13^*$ |
| | | EJ | J | $7+6=13^*$ |
| | F | FH | H | $8+5=13$ |
| | | FJ | J | $5+6=11^*$ |
| 1 | A | AD | D | $8+15=23$ |
| | | AE | E | $6+13=19^*$ |
| | B | BE | E | $17+13=30$ |
| | | BF | F | $9+11=20^*$ |
| | C | CD | D | $10+15=25$ |
| | | CF | F | $10+11=21^*$ |
| 0 | S | SA | A | $11+19=30$ |
| | | SB | B | $8+20=28^*$ |
| | | SC | C | $12+21=33$ |
Route: $S - B - F - J - T$
---
## SC4 Maximax:
| Stage | State | Action | Destination | Value |
|-------|-------|--------|-------------|-------|
| 3 | G | GT | T | $8^*$ |
| | H | HT | T | $5^*$ |
| | J | JT | T | $6^*$ |
| 2 | D | DH | H | $\max(10,5)=10^*$ |
| | E | EG | G | $\max(9,8)=9^*$ |
| | | EH | H | $\max(8,5)=8$ |
| | | EJ | J | $\max(7,6)=7$ |
| | F | FH | H | $\max(8,5)=8^*$ |
| | | FJ | J | $\max(5,6)=6$ |
| 1 | A | AD | D | $\max(8,10)=10^*$ |
| | | AE | E | $\max(6,9)=9$ |
| | B | BE | E | $\max(17,9)=17^*$ |
| | | BF | F | $\max(9,8)=9$ |
| | C | CD | D | $\max(10,10)=10^*$ |
| | | CF | F | $\max(10,8)=10^*$ |
| 0 | S | SA | A | $\max(11,10)=11$ |
| | | SB | B | $\max(8,17)=17^*$ |
| | | SC | C | $\max(12,10)=12$ |
---
## SC5 Minimin:
| Stage | State | Action | Destination | Value |
|-------|-------|--------|-------------|-------|
| 3 | G | GT | T | $8^*$ |
| | H | HT | T | $5^*$ |
| | J | JT | T | $6^*$ |
| 2 | D | DH | H | $\min(10,5)=5^*$ |
| | E | EG | G | $\min(9,8)=8$ |
| | | EH | H | $\min(8,5)=5^*$ |
| | | EJ | J | $\min(7,6)=6$ |
| | F | FH | H | $\min(8,5)=5^*$ |
| | | FJ | J | $\min(5,6)=5^*$ |
| 1 | A | AD | D | $\min(8,5)=5^*$ |
| | | AE | E | $\min(6,5)=5^*$ |
| | B | BE | E | $\min(17,5)=5^*$ |
| | | BF | F | $\min(9,5)=5^*$ |
| | C | CD | D | $\min(10,5)=5^*$ |
| | | CF | F | $\min(10,5)=5^*$ |
| 0 | S | SA | A | $\min(11,5)=5^*$ |
| | | SB | B | $\min(8,5)=5^*$ |
| | | SC | C | $\min(12,5)=5^*$ |
---
## SC6 Working Forwards S to T:
| Stage | State | Action | Destination | Value |
|-------|-------|--------|-------------|-------|
| 3 | A | AS | S | $11^*$ |
| | B | BS | S | $8^*$ |
| | C | CS | S | $12^*$ |
| 2 | D | DA | A | $\min(8,11)=8$ |
| | | DC | C | $\min(10,12)=10^*$ |
| | E | EA | A | $\min(6,11)=6$ |
| | | EB | B | $\min(17,8)=8^*$ |
| | F | FB | B | $\min(9,8)=8$ |
| | | FC | C | $\min(10,12)=10^*$ |
| 1 | G | GE | E | $\min(9,8)=8^*$ |
| | H | HD | D | $\min(10,12)=10^*$ |
| | | HE | E | $\min(8,8)=8$ |
| | | HF | F | $\min(8,10)=8$ |
| | J | JE | E | $\min(7,8)=7^*$ |
| | | JF | F | $\min(5,10)=5$ |
| 0 | T | TG | G | $\min(8,8)=8^*$ |
| | | TH | H | $\min(5,10)=5$ |
| | | TJ | J | $\min(6,7)=6$ |
---
## SC7 Reversed States:
| Stage | State | Action | Destination | Value |
|-------|-------|--------|-------------|-------|
| 3 | T | TG | G | $8^*$ |
| | | TH | H | $5^*$ |
| | | TJ | J | $6^*$ |
| 2 | G | GE | E | $\min(9,8)=8^*$ |
| | H | HD | D | $\min(10,5)=5^*$ |
| | | HE | E | $\min(8,5)=5$ |
| | | HF | F | $\min(8,5)=5^*$ |
| | J | JE | E | $\min(7,6)=6$ |
| | | JF | F | $\min(5,6)=5^*$ |
| 1 | D | DA | A | $\min(8,5)=5$ |
| | | DC | C | $\min(10,5)=5^*$ |
| | E | EA | A | $\min(6,8)=6^*$ |
| | | EB | B | $\min(17,8)=8^*$ |
| | F | FB | B | $\min(9,5)=5$ |
| | | FC | C | $\min(10,5)=5^*$ |
| 0 | A | AS | S | $\min(11,6)=6$ |
| | B | BS | S | $\min(8,8)=8^*$ |
| | C | CS | S | $\min(12,5)=5$ |
Weight: $8$ Route: $S - B - E - G - T$
6.
\begin{figure}[h]
\begin{center}
\includegraphics[alt={},max width=\textwidth]{57c75bde-811a-421c-899a-3689bdba6724-7_614_1264_239_402}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}
The staged, directed network in Figure 2 represents a series of roads connecting 11 towns, $\mathrm { S } , \mathrm { A }$, B, C, D, E, F, G, H, J and T. The number on each arc shows the weight limit, in tonnes, for the corresponding road. Janet needs to drive a truck from S to T, passing through exactly three other towns. She needs to find the maximum weight of the truck that she can use.
\begin{enumerate}[label=(\alph*)]
\item Write down the type of dynamic programming problem that Janet needs to solve.
\item Use dynamic programming to complete the table in the answer book.
\item Hence find the maximum weight of the truck Janet can use.
\item Write down the route that Janet should take.
Janet intends to ask for the weight limit to be increased on one of the three roads leading directly into T. Janet wishes to maximise the weight of her truck.
\item \begin{enumerate}[label=(\roman*)]
\item Determine which of the three roads she should choose and its new minimum weight limit.
\item Write down the maximum weight of the truck she would be able to use and the new route she would take.
\end{enumerate}\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2015 Q6 [16]}}