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.Ordinary 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 (8), A→C (13), B→D (9), C→D (15). 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 (8), A→C (13), B→D (9) and C→D (15). 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. Only along the listed arrows: each one is one way.
  • What is fixed? Four one-way legs: A→B 8, A→C 13, B→D 9, C→D 15. Costs, so lower is better. No units are given.
  • What do they want? The least cost from A to D. And the method is named: backward values, working from D back to A.
Céim

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

Bellman's Principle & Dynamic Programming

Bellman's principle finds the best route by combining each next-edge cost with the best remaining cost from its destination.

Why it matters

Working backwards stores useful results at each state and avoids judging a whole journey by its first edge alone.

The worked example

Travel from A to the terminal D is allowed only along A→B (8), A→C (13), B→D (9) and C→D (15). 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. Only along the listed arrows: each one is one way.
    • What is fixed? Four one-way legs: A→B 8, A→C 13, B→D 9, C→D 15. Costs, so lower is better. No units are given.
    • What do they want? The least cost from A to D. And the method is named: backward values, working from D back to A.
  2. Understand

    • How do I picture it?
    • A on the left, D on the right, B above, C below. Draw each leg as an arrow with its cost.
    • Two ways to go: through B, or through C. At A you must choose.
  3. Reduce

    • Where do I start?
    • At the end, D. Then B and C, which lead straight to D. Then A, last.
    • At A, compare two totals: 8 + J(B) and 13 + J(C). Keep the smaller.
  4. Solve

    • Work back from D.
    • J(D) = 0
    • J(B) = 9 + J(D) = 9 + 0 = 9
  5. Check

    • Is it right, and did I answer it?
    • Go forward instead: A→B→D costs 8 + 9 = 17. A→C→D costs 13 + 15 = 28. 17 is less. ✓
    • Here the cheaper first leg did win. That was luck: with B→D at 30, it would lose. Backward values never rely on luck.