D2 4.1 - Bellman's principle and tabulation | Edexcel A-Level Further Mathematics

One network has just four routes, yet four sensible questions give four different winners. The shortest total, longest total, smallest worst arc and largest weakest arc need not choose the same route. How can one organised method handle all four?

You already know

For a fixed list of numbers, $\min$ selects the smallest and $\max$ selects the largest. A total adds contributions; a largest or smallest individual contribution is a different quantity.

A network consists of nodes joined by arcs carrying numerical weights. Arrows specify permitted directions. A directed path follows these arrows without repeating a node. A staged network groups nodes into successive decision positions, with every arc moving to a later position, so no directed cycle is possible. A crossing without a marked node is not a junction.

Dynamic programming solves a large decision problem through smaller remaining problems. The essential information must be recorded in the state.

The tabulation columns

Column	Meaning
Stage	Which decision position or time period is being considered
State	Information that identifies the remaining problem, such as the current node or stock held
Action	A feasible choice at that state
Destination	The state reached after taking that action
Value	That action's contribution combined with the already optimised continuation

The stage variable identifies the position or period. The state variable identifies the relevant situation within it. Record every feasible action, and mark each state’s optimum with a star.

The same node can be a sufficient state for a route whose future costs depend only on that node. A production problem may instead need the amount of stock held. If an earlier decision changes future possibilities, include that information in the state; do not merge different remaining problems.

Bellman's principle of optimality

For a shortest or longest additive path in the staged setting, any part of an optimal path is itself optimal between its endpoints.

Not in the formula booklet: learn it.

For a shortest path, suppose a chosen continuation could be replaced by a cheaper one from the same state. Keeping the earlier decisions and making that replacement would improve the whole route, contradicting optimality. The longest-path argument replaces “cheaper” by “larger”. This lets us optimise the final decisions first and reuse their values at earlier stages.

Work backwards to calculate values, then trace the selected actions forwards to recover a route or schedule. Here stage $1$ will be the final decision before the destination, stage $2$ the preceding decision, and so on.

Key idea

A value belongs to a defined remaining problem. Combine each possible action with the correct destination's optimal value; choosing the best-looking immediate action alone is not dynamic programming.

Check the logic that makes a stored continuation reusable.

Tabulate minimum and maximum total weight

Use this staged network throughout the route examples. Its weights are abstract numbers; the question determines whether they represent costs, rewards, leg lengths or another quantity.

[DIAGRAM: asset_name: One staged network with four different optimal routes; asset_slug: 9fm0-d2-188-staged-network; caption: Work backwards from T, then trace selected actions forwards from S.; description: Directed staged network S to A7 and B5, A to C1 and D12, B to C15 and D8, C to T13 and D to T9; the crossing of AD and BC is not a node, and backward decision stages are labelled1 at C,D,2 at A,B,3 at S.]

For an additive objective, the candidate value is always immediate arc weight plus the best remaining total at its destination.

Additive Bellman recurrences

Let $w_{vu}$ be the weight on $v\to u$ . With terminal value $V(T)=0$ ,

V_{\min}(v)=\min_{v\to u}\{w_{vu}+V_{\min}(u)\}

V_{\max}(v)=\max_{v\to u}\{w_{vu}+V_{\max}(u)\}

Use the same objective at every stage. These recurrences apply to the staged network, so the continuation values are known when a state is processed.

Not in the formula booklet: learn it.

List all candidate actions before choosing the state optimum. A star marks a selected minimum or maximum within that state, rather than the smallest or largest entry in the entire table.

Worked example 1: optimise the same network in two ways

Question. Find a minimum-total and a maximum-total S-to-T route by tabulation.

Plan. Solve states C and D, then A and B, then S. Use a separate table for each objective and trace its stars forwards.

For a minimum total:

Stage	State	Action	Destination	Value
$1$	C	CT	T	$13+0=13^\ast$
$1$	D	DT	T	$9+0=9^\ast$
$2$	A	AC	C	$1+13=14^\ast$
$2$	A	AD	D	$12+9=21$
$2$	B	BC	C	$15+13=28$
$2$	B	BD	D	$8+9=17^\ast$
$3$	S	SA	A	$7+14=21^\ast$
$3$	S	SB	B	$5+17=22$

For a maximum total:

Stage	State	Action	Destination	Value
$1$	C	CT	T	$13^\ast$
$1$	D	DT	T	$9^\ast$
$2$	A	AC	C	$1+13=14$
$2$	A	AD	D	$12+9=21^\ast$
$2$	B	BC	C	$15+13=28^\ast$
$2$	B	BD	D	$8+9=17$
$3$	S	SA	A	$7+21=28$
$3$	S	SB	B	$5+28=33^\ast$

Why is the SA candidate different in the two tables? A's best remaining total is $14$ for minimisation but $21$ for maximisation. Using the wrong continuation would mix two different problems.

Answer. Minimum: $S,A,C,T$ , total $21$ . Maximum: $S,B,C,T$ , total $33$ .

Check. Their direct sums are $7+1+13=21$ and $5+15+13=33$ . The initially cheaper SB arc does not begin the minimum-total route.

Worked example 2 changes only CT's weight, from $13$ to $11$ . The graph and the two objectives remain fixed.

Worked example 2: propagate one changed continuation

Question. Recalculate both optimal totals and routes after the CT change.

Plan. Update C, then every earlier state whose candidates use C. Do not change D's value.

For a minimum total:

Stage	State	Action	Destination	Value
$1$	C	CT	T	$11^\ast$
$1$	D	DT	T	$9^\ast$
$2$	A	AC	C	$1+11=12^\ast$
$2$	A	AD	D	$12+9=21$
$2$	B	BC	C	$15+11=26$
$2$	B	BD	D	$8+9=17^\ast$
$3$	S	SA	A	$7+12=19^\ast$
$3$	S	SB	B	$5+17=22$

For a maximum total:

Stage	State	Action	Destination	Value
$1$	C	CT	T	$11^\ast$
$1$	D	DT	T	$9^\ast$
$2$	A	AC	C	$1+11=12$
$2$	A	AD	D	$12+9=21^\ast$
$2$	B	BC	C	$15+11=26^\ast$
$2$	B	BD	D	$8+9=17$
$3$	S	SA	A	$7+21=28$
$3$	S	SB	B	$5+26=31^\ast$

Why does B's minimum remain $17$ although its BC candidate changes? Its selected minimum action is still BD. Update every affected candidate, then choose again.

Answer. Minimum: $S,A,C,T$ , total $19$ . Maximum: $S,B,C,T$ , total $31$ .

Check. Direct route sums are $7+1+11=19$ and $5+15+11=31$ ; each selected route uses CT once, so each total falls by $2$ .

If weights are travel durations and an arrival deadline is given, first obtain the minimum total duration, then subtract it from the deadline. Keep the value column as a duration unless the question explicitly defines a different state value.

Watch out

Wrong: choose the smallest immediate arc for a minimum route, omit the destination's value, or switch from minimum to maximum partway through. Right: combine immediate weight with the correct optimised continuation at every state.

Change only CT once more.

Optimise the worst arc rather than a total

A minimax route makes its largest arc as small as possible: for example, avoid any very long individual driving leg. A maximin route makes its smallest arc as large as possible: for example, choose a route with the widest possible narrowest passage.

These are single-route objectives. They do not add arc weights, and a maximin path is not a calculation of total flow through a whole network.

Bottleneck Bellman recurrences

At the last decision stage, each route has one arc, so initialise its value from that arc's weight. At earlier stages,

B(v)=\min_{v\to u}\max\{w_{vu},B(u)\} \qquad\text{for minimax}

W(v)=\max_{v\to u}\min\{w_{vu},W(u)\} \qquad\text{for maximin}

The inner operation measures a candidate route's worst arc; the outer operation chooses the best candidate.

Not in the formula booklet: learn it.

Optimising the continuation is still safe: replacing a suffix by one with a smaller largest arc cannot worsen a minimax candidate; replacing it by one with a larger smallest arc cannot worsen a maximin candidate. Follow selected actions to obtain an optimal route, keeping tied choices where they occur.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure Mathematics

Further Pure Mathematics 1

Further Pure Mathematics 2

Further Statistics 1

Further Statistics 2

Further Mechanics 1

Further Mechanics 2

Decision Mathematics 1

Decision Mathematics 2

D2 4.1 - Bellman's principle and tabulation

Solve the remaining problem before the earlier decision

Tabulate minimum and maximum total weight

Optimise the worst arc rather than a total

Continue this lesson.

Learn faster with Nova