A2 June 2024 Q6

EdexcelCurrent spec10 marksDynamic Programming

Figure 2: staged directed network from S to T with arcs SA 3, SB 2, AC 4, AE 5, BC 4, BD 7, BE 4, CF 3, CG 4, DF 3, DG 1, EG 2, FH 5, FI 4, FJ 6, GH 5, GI 3, HT 2, IT 3, JT 4 — Figure 2

The staged, directed network in Figure 2 represents the roads that connect 12 towns, S, A, B, C, D, E, F, G, H, I, J and T. The number on each arc shows the time, in hours, it takes to drive between these towns.

Elena plans to drive from S to T. She must arrive at T by 9 pm.

(a) By completing the table in the answer book, use dynamic programming to find the latest time that Elena can start her journey from S to arrive at T by 9 pm. (9)

[The table in the answer book has columns headed Stage, State, Action, Destination and Value.]

(b) Hence write down the route that Elena should take. (1)

Mark scheme (a)

Scheme

Marks

Stage	State	Action	Dest	Value
1	H	HT	T	2*
	I	IT	T	3*
	J	JT	T	4*

3.1a

Stage	State	Action	Dest	Value
2	F	FH	H	5 + 2 = 7*
		FI	I	4 + 3 = 7*
		FJ	J	6 + 4 = 10
	G	GH	H	5 + 2 = 7
		GI	I	3 + 3 = 6*

M1
A1

3.1a
1.1b

Stage	State	Action	Dest	Value
3	C	CF	F	3 + 7 = 10*
		CG	G	4 + 6 = 10*
	D	DF	F	3 + 7 = 10
		DG	G	1 + 6 = 7*
	E	EG	G	2 + 6 = 8*

M1
A1

1.1b
1.1b

Stage	State	Action	Dest	Value
4	A	AC	C	4 + 10 = 14
		AE	E	5 + 8 = 13*
	B	BC	C	4 + 10 = 14
		BD	D	7 + 7 = 14
		BE	E	4 + 8 = 12*
5	S	SA	A	3 + 13 = 16
		SB	B	2 + 12 = 14*

M1
A1ft
A1

1.1b
1.1b
1.1b

Latest time that Elena can start her journey is 7 am

3.2a

(9)

Notes

All M marks – must bring earlier optimal results into calculations. Ignore extra rows. Penalise lack of * only once per question.

B1: CAO for first stage

M1: Second stage completed. At least 4 rows, something in each cell.

A1: CAO for second stage exactly 5 rows

M1: Third stage completed. At least 4 rows, something in each cell.

A1: CAO for third stage exactly 5 rows

M1: Fourth stage completed. 5 rows, something in each cell.

A1ft: correct ft their optimal values from third stage

A1: CAO for fifth stage

A1: Correct latest start time in context (e.g. 7 am, 07:00, etc.)

Special Case – Maximin or Minimax

Stage	State	Action	Dest	Value	Value
1	H	HT	T	2*	2*
	I	IT	T	3*	3*
	J	JT	T	4*	4*
2	F	FH	H	Min (5, 2) = 2	Max (5, 2) = 5
		FI	I	Min (4, 3) = 3	Max (4, 3) = 4*
		FJ	J	Min (6, 4) = 4*	Max (6, 4) = 6
	G	GH	H	Min (5, 2) = 2	Max (5, 2) = 5*
		GI	I	Min (3, 3) = 3*	Max (3, 3) = 3
3	C	CF	F	Min (3, 4) = 3*	Max (3, 4) = 4*
		CG	G	Min (4, 3) = 3*	Max (4, 5) = 5
	D	DF	F	Min (3, 4) = 3*	Max (3, 4) = 4*
		DG	G	Min (1, 3) = 1	Max (1, 5) = 5
	E	EG	G	Min (2, 3) = 2*	Max (2, 5) = 5*
4	A	AC	C	Min (4, 3) = 3*	Max (4, 4) = 4*
		AE	E	Min (5, 2) = 2	Max (5, 5) = 5
	B	BC	C	Min (4, 3) = 3*	Max (4, 4) = 4*
		BD	D	Min (7, 3) = 3*	Max (7, 4) = 7
		BE	E	Min (4, 2) = 2	Max (4, 5) = 5
5	S	SA	A	Min (3, 3) = 3*	Max (3, 4) = 4*
		SB	B	Min (2, 3) = 2	Max (2, 4) = 4*

B1 M1 A0 M1 A0 M1 A0 A0 A0 B0 - Max 4/10

Scheme	Marks	AO
Route: SBEGIT	B1	2.2a
	(1)
	(10 marks)