D2 June 2005 Q4

EdexcelOld spec14 marksDynamic Programming

(a) Explain what is meant by a maximin route in dynamic programming, and give an example of a situation that would require a maximin solution. (3)

A maximin route is to be found through the network shown in the diagram.

(b) Complete the table in the answer book, and hence find a maximin route. (9)

Scheme	Marks
The route from start to finish in which the arc of minimum length is as large as possible.	B2, 1, 0
e.g. must be practical, involve choice of route, have are ‘cuts’.	B1
	(3)

Mark scheme (b)

Scheme

Marks

Stage	State	Action	Value
1	H	HK	18(*)
	I	IK	19(*)
	J	JK	21(*)
2	F	FH	min (16, 18) = 16
		FI	min (23, 19) = 19(*)
		FJ	min (17, 21) = 17
	G	GH	min (20, 18) = 18
		GI	min (15, 19) = 15
		GJ	min (28, 21) = 21(*)
3	B	BG	min (18, 21) = 18(*)
	C	CF	min (25, 19) = 19(*)
		CG	min (16, 21) = 16
	D	DF	min (22, 19) = 19(*)
		DG	min (19, 21) = 19(*)
	E	EF	min (14, 19) = 14(*)
4	A	AB	min (24, 18) = 18
		AC	min (25, 19) = 19(*)
		AD	min (27, 19) = 19(*)
		AE	min (23, 14) = 14

Stage 1

M1 A1 (2)

Stage 2

M1 A1 A1 (3)

Stage 3

M1 A1ft

Stage 4

A1ft (3)

(8)

The scheme awards 8 marks to this part and 3 to part (c); the paper prints (9) and (2).