D2 June 2007 Q7

EdexcelOld spec14 marksDynamic Programming

Network of underwater tunnels from X to Y through air pockets A to L with times in seconds

Agent Goodie has successfully recovered the stolen plans from Evil Doctor Fiendish and needs to take them from Evil Doctor Fiendish’s secret headquarters at X to safety at Y. To do this he must swim through a network of underwater tunnels. Agent Goodie has no breathing apparatus, but knows that there are twelve points, \(A\), \(B\), \(C\), \(D\), \(E\), \(F\), \(G\), \(H\), \(I\), \(J\), \(K\) and \(L\), at which there are air pockets where he can take a breath.

The network is modelled above, and the number on each arc gives the time, in seconds, it takes Agent Goodie to swim from one air pocket to the next.

Agent Goodie needs to find a route through this network that minimises the longest time between successive air pockets.

(a) Use dynamic programming to complete a table of stage, state, action, destination and value, and hence find a suitable route for Agent Goodie. (12)

Unfortunately, just as Agent Goodie is about to start his journey, tunnel XA becomes blocked.

(b) Find an optimal route for Agent Goodie avoiding tunnel XA. (2)

Mark scheme (a)

Scheme

Marks

Stage	State	Action	Destination	Value
1	J	JY	Y	98*
	K	KY	Y	94*
	L	LY	Y	86*
2	G	GJ	J	max(79, 98) = 98*
		GK	K	max(98, 94) = 98*
	H	HK	K	max(95, 94) = 95
		HL	L	max(72, 86) = 86*
	I	IL	L	max(56, 86) = 86*
3	C	CG	G	max(50, 98) = 98*
	D	DG	G	max(92, 98) = 98
		DH	H	max(81, 86) = 86*
	E	EH	H	max(89, 86) = 89*
	F	FH	H	max(84, 86) = 86*
		FI	I	max(72, 86) = 86*
4	A	AC	C	max(95, 98) = 98
		AD	D	max(86, 86) = 86*
		AE	E	max(63, 89) = 89
	B	BE	E	max(88, 89) = 89
		BF	F	max(87, 86) = 87*
5	X	XA	A	max(55, 86) = 86*
		XB	B	max(85, 87) = 87

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

X A D H L Y (minimax = 86)

M1 A1ft

(12)

Notes

The question paper prints no table; the scheme’s table is shown.