D2 June 2008 Q4

EdexcelOld spec12 marksDynamic Programming

(a) Explain the difference between a maximin route and a minimax route in dynamic programming. (2)

A maximin route from L to R is to be found through the staged network shown above.

(b) Use dynamic programming to complete a table and hence find a maximin route. (10)

Scheme	Marks
Maximin : we seek a route where the shortest arc used is as great as possible. Minimax : we seek a route where the longest arc used is as small as possible.	B2, 1, 0
	(2)

Mark scheme (b)

Scheme

Marks

Stage	State	Action	Dest.	Value
1	G	GR	R	132*
	H	HR	R	175*
	I	IR	R	139*
2	D	DG	G	min (175, 132) = 132
		DH	H	min (160, 175) = 160*
	E	EG	G	min (162, 132) = 132
		EH	H	min (144, 175) = 144*
		EI	I	min (102, 139) = 102
	F	FH	H	min (145, 175) = 145*
		FI	I	min (210, 139) = 139
3	A	AD	D	min (185, 160) = 160*
		AE	E	min (279, 144) = 144
	B	BD	D	min (119, 160) = 119
		BE	E	min (250, 144) = 144*
		BF	F	min (123, 145) = 123
	C	CE	E	min (240, 144) = 144
		CF	F	min (170, 145) = 145*
4	L	LA	A	min (155, 160) = 155*
		LB	B	min (190, 144) = 144
		LC	C	min (148, 145) = 145

Stage 1: M1 A1
Stage 2: M1 A1 A1
Stage 3: M1 A1ft A1ft
Stage 4: A1ft

Maximin route: LADHR

A1ft

(10)

(12 marks)

The printed scheme shows column totals 5 against the table and 5 against the route; the codes listed add up to 10.