A2 October 2021 Q6

EdexcelCurrent spec12 marksDynamic Programming

Figure 3: staged directed network from S to T with arcs SA 52, SB 48, SC 50, AD 53, AE 52, AF 53, BE 51, BF 50, BG 46, CE 50, CG 47, DH 49, DI 50, EH 51, EJ 46, FH 51, FI 52, FJ 50, GI 53, GJ 51, HT 47, IT 48, JT 49 — Figure 3

The staged, directed network in Figure 3 represents a series of roads connecting 12 towns, \(S\), \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\), \(H\), \(I\), \(J\) and \(T\). The number on each arc shows the distance between these towns, in miles.

Bradley is planning a four-day cycle ride from \(S\) to \(T\).

He plans to leave his home at \(S\). On the first night he will stay at \(A\), \(B\) or \(C\), on the second night he will stay at \(D\), \(E\), \(F\) or \(G\), on the third night he will stay at \(H\), \(I\) or \(J\), and he will arrive at his friend’s house at \(T\) on the fourth day.

Bradley decides that the maximum distance he will cycle on any one day should be as small as possible.

(a) Write down the type of dynamic programming problem that Bradley needs to solve. (1)

(b) Use dynamic programming to complete the table below. (9)

Stage	State	Action	Destination	Value

Scheme	Marks	AO
Minimax	B1	1.2
	(1)

Mark scheme (b)

Scheme

Marks

Stage	State	Action	Destination	Value
1	H	HT	T	47*
	I	IT	T	48*
	J	JT	T	49*

3.1a

Stage	State	Action	Destination	Value
2	D	DH	H	Max(49, 47) = 49*
		DI	I	Max(50, 48) = 50
	E	EH	H	Max (51, 47) = 51
		EJ	J	Max (46, 49) = 49*
	F	FH	H	Max (51, 47) = 51
		FI	I	Max (52, 48) = 52
		FJ	J	Max (50, 49) = 50*
	G	GI	I	Max (53, 48) = 53
		GJ	J	Max (51, 49) = 51*

M1
A1
A1

3.1a
1.1b
1.1b

Stage	State	Action	Destination	Value
3	A	AD	D	Max(53, 49) = 53
		AE	E	Max(52, 49) = 52*
		AF	F	Max (53, 50) = 53
	B	BE	E	Max(51, 49) = 51
		BF	F	Max(50, 50) = 50*
		BG	G	Max(46, 51) = 51
	C	CE	E	Max(50, 49) = 50*
		CG	G	Max(47, 51) = 51

M1
A1ft
A1

1.1b
1.1b
1.1b

Stage	State	Action	Destination	Value
4	S	SA	A	Max(52, 52) = 52
		SB	B	Max(48, 50) = 50*
		SC	C	Max(50, 50) = 50*

M1
A1ft

1.1b
1.1b

(9)

Notes

Throughout (b):

Condone lack of destination column and/or reversed stage numbers throughout
Only penalise incorrect result in value – ie ignore working values
Penalise absence of state or action column with first two A marks earned only
Penalise empty/errors in stage column with first A mark earned only
If maximin, minimum, maximum, etc. then only the B mark and M marks can be awarded in (b) (so 4 out of 9 maximum) and one B mark can be awarded in (c) following through a correct route from their table

M marks in (b) - must bring earlier optimal results into calculations at least once

B1: Stage 1 correct

M1: Stage 2 completed with 4 states and at least 9 rows. Bod if something in each cell

A1: Any two states in Stage 2 correct

A1: cao all 4 states correct in Stage 2 (no extra rows)

M1: Stage 3 completed with 3 states and at least 8 rows. Bod if something in each cell

A1ft: cao any 2 states correct in Stage 3 on the follow through

A1: cao all 3 states in Stage 3 (no extra rows)

M1: Stage 4 completed with 1 state and at least 3 rows. Bod if something in each cell

A1ft: cao for Stage 4 following through their * values (no extra rows)

Mark scheme (c)

Scheme	Marks	AO
Route 1: S – B – F – J – T Route 2: S – C – E – J – T	B1ft B1	2.2a 2.2a
	(2)
	(12 marks)

Notes

B1ft: One correct route (dependent on first B mark and all M marks in (b)) following through their least values (oe) at each stage in (b)

B1: Both routes correct (dependent on first B mark and all M marks in (b))