Step 6 of 8 · Worked example · TEACH

← Algorithms, Optimisation & Project Scheduling

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Higher Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 6

Follow the worked example and explain why each modelling and calculation step is valid.

Travel from A to terminal D is permitted only along A→B (4), A→C (9), B→D (5), C→D (11). All weights are costs. Find the minimum cost from A using backward values.

Travel from A to the terminal D is allowed only along A→B (4), A→C (9), B→D (5) and C→D (11). All weights are costs.

Find the minimum cost from A using backward values.

Read it once, slowly. Then copy it onto your page.
  • What is going on? A trip from A that ends at the terminal D. It can go only along four one-way edges: A→B 4, A→C 9, B→D 5, C→D 11.
  • What are the numbers? Costs: each edge used adds its cost. The arrows matter: no edge may be used against its arrow. No units are given.
  • What do they want? The least total cost from A to D, found by backward values: start at D and work back to A.
Céim

Higher Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 6 of 8

Bellman's Principle & Dynamic Programming

Bellman’s principle finds an optimal policy by combining each immediate cost with the best remaining cost from the next state.

Why it matters

In exam network problems, backward dynamic programming gives a justified minimum rather than an unsupported cheapest-edge guess.

The worked example

Travel from A to the terminal D is allowed only along A→B (4), A→C (9), B→D (5) and C→D (11). All weights are costs. Find the minimum cost from A using backward values.

How the worked example goes

  1. Read

    • What is going on? A trip from A that ends at the terminal D. It can go only along four one-way edges: A→B 4, A→C 9, B→D 5, C→D 11.
    • What are the numbers? Costs: each edge used adds its cost. The arrows matter: no edge may be used against its arrow. No units are given.
    • What do they want? The least total cost from A to D, found by backward values: start at D and work back to A.
  2. Understand

    • How do I picture it?
    • Draw A on the left, D on the right, B above the middle, C below. Draw the four arrows with their costs.
    • A → B (4), B → D (5)
  3. Reduce

    • Where do I start?
    • At the terminal: no travel is left, so J(D) = 0.
    • B and C each have one edge out, to D. A has two, so J(A) is the smaller of two totals.
  4. Solve

    • Work back to B and C.
    • Why backwards works: once J is known at every node ahead, each choice weighs the whole rest of the trip, not just the next edge.
    • J(D) = 0
  5. Check

    • Is it right?
    • Add each route forwards
    • A→B→D: 4 + 5 = 9