D2 June 2015 Q6

EdexcelOld spec16 marksDynamic Programming

Figure 2: staged directed network of roads from S to T through A, B, C, D, E, F, G, H and J with weight limits — Figure 2

The staged, directed network in Figure 2 represents a series of roads connecting 11 towns, S, 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.

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

(b) Use dynamic programming to complete the table in the answer book. (10)

(d) Write down the route that Janet should take. (1)

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.

(e) (3)

(i) Determine which of the three roads she should choose and its new minimum weight limit.

(ii) Write down the maximum weight of the truck she would be able to use and the new route she would take.

Scheme	Marks
Maximin	B1
	(1)

Mark scheme (b)

Stage	State	Action	Destination	Value	Marks
3	G	GT	T	8*
	H	HT	T	5*	M1 A1
	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	M1 A1 A1
		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, 8) = 6*	M1 A1ft A1
	B	BE	E	min (17, 8) = 8*
		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, 6) = 6
		SB	B	min (8, 8) = 8*	M1 A1
		SC	C	min (12, 5) = 5
					(10)

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

2^nd, 3^rd and 4^th M marks - must bring earlier optimal results into calculations at least oncePenalise lack of * only once

b1M1: First stage completed. 3 rows, something in each cell

b1A1: CAO condone missing * here

b2M1: Second stage completed with 3 states and at least 6 rows. Bod if something in each cell

b2A1: Second stage any 2 states correct

b3A1: CAO all 3 states correct (no missing/extra rows)

b3M1: Third stage completed with 3 states and at least 6 rows. Bod if something in each cell

b4A1ft: Third stage any two states correct. Follow through their * values or the correct * values

b5A1: CAO all 3 states correct (no missing/extra rows)

b4M1: Fourth stage completed with 1 state and at least 3 rows. Bod if something in each cell

b6A1: CAO final state correct (no missing/extra rows)

Special cases

Special Cases for (b), (c) and (d)

SC1 Minimax: M1 A1 M1 A0 A0 M1 A1 A0 M1 A0 B1 B1 (Max 8/12)SC2 Maximum: M1 A1 M1 A0 A0 M1 A0 A0 M1 A0 B0 B1 (Max 6/12)SC3 Minimum: As above (SC2)SC4 Maximax: M1 A1 M1 A0 A0 M1 A0 A0 M1 A0 B0 B0 (Max 5/12)SC5 Minimin: As above (SC4)SC6 Working forwards: M1 A0 M1 A0 A0 M1 A0 A0 M1 A0 B0 B0 (Max 4/12)SC7 Reversed states: M1 A0 M1 A0 A0 M1 A0 A0 M1 A1 B1 B1 (Max 7/12)

SC1 Minimax:

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, 7) = 7*
	B	BE	E	max (17, 7) = 17
		BF	F	max (9, 6) = 9*
	C	CD	D	max (10, 10)=10*
		CF	F	max (10, 6) = 10*
0	S	SA	A	max (11, 7) = 11
		SB	B	max (8, 9) = 9*
		SC	C	max (12, 10) = 12

Weight: 9 Route: S – B – F – J – T

SC2 Maximum:

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 + 17 = 23*
	B	BE	E	17 + 17 = 34*
		BF	F	9 + 13 = 22
	C	CD	D	10 + 15 = 25*
		CF	F	10 + 13 = 23
0	S	SA	A	11 + 23 = 34
		SB	B	8 + 34 = 42*
		SC	C	12 + 25 = 37

Route: S – B – E – G – T

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

Scheme	Marks
Maximum weight = 8 (tonnes)	B1
	(1)

Scheme	Marks
Route: S – B – E – G – T	B1
	(1)

Mark scheme (e)

Scheme	Marks
(i) Increase HT (by 5) to 10	B1
(ii) Maximum weight = 10 (tonnes)	B1
New route: S – C – D – H – T	B1
	(3)
	16 marks

Notes

e1B1: Indication of either increasing HT by 5 or increasing HT to 10

e2B1: CAO (10)

e3B1: CAO (S – C – D – H – T)