Optimal Paths (Leaving Cert Applied Maths): Revision Notes
Bellman's Principle
What is Bellman's principle?
Bellman's Principle of Optimality is a fundamental concept in dynamic programming that helps us find optimal paths through networks. The principle states that if you have an optimal path from point A to point C that passes through point B, then the portion of that path from B to C must also be optimal.
In simpler terms, an optimal path is made up of optimal sub-paths. This means we can break down complex routing problems into smaller, manageable pieces and solve them systematically.
Understanding multi-stage networks
A multi-stage network is a special type of graph where nodes are organised into distinct stages or levels. These networks are particularly useful for solving sequential decision problems where you move from one stage to the next.
Key characteristics of multi-stage networks:
- Nodes represent different states or positions
- Edges connect nodes between adjacent stages with associated weights or costs
- Stages are numbered in reverse order (working backwards from the destination)
- Source node (S) is where we start our journey
- Sink node (T) is our final destination
The stages are numbered in reverse order because we use backward induction - we start our calculations from the destination and work backwards to the source. This approach ensures we always know the optimal value for future stages when making current decisions.
Dynamic programming table structure
To solve multi-stage network problems systematically, we use a structured table with four main columns:
Table Column Definitions:
- Stage: The stage number (numbered in reverse from destination to source)
- State: The node or position we're currently at
- Action: The possible moves or edges we can take from this state
- Value: The optimal value (cost, distance, or benefit) from this state to the destination
Step-by-step solution process
General Solution Approach: Always work backwards from the destination using the following systematic process for each stage.
Stage 1: Terminal stage calculations
Begin with the nodes that connect directly to the destination (sink). For these nodes, there's only one possible action - moving to the terminal node T. The value is simply the weight of the edge connecting to T.
Stage 2: Intermediate stage calculations
For each node in this stage, examine all possible actions (edges to the next stage). Calculate the value for each action by adding:
- The weight of the edge
- The optimal value from the destination node of that edge
Select the action that gives the best (maximum or minimum) value and mark it as optimal.
Stage 3: Source stage calculations
Apply the same process to the source node, considering all possible first moves. The optimal action here determines the first step of your optimal path.
Worked example solution
Worked Example: Finding the Longest Route from S to T
Let's examine how this works with a practical example finding the longest route from S to T:
Stage 1 Results:
- From E to T: Value = 14 (only route available)
- From F to T: Value = 15 (only route available)
- From G to T: Value = 12 (only route available)
Stage 2 Calculations:
- From A: Can go to E , F , or G . Best choice: AE with value 33
- From B: Can go to E or F . Both equally good with value 35
- From C: Can go to E , F , or G . Best choice: CE with value 34
Stage 3 Calculations:
- From S: Can go to A , B , or C . Best choice: SC with value 45
Optimal Path: The longest route is S→C→E→T with total length of 45.
Key examination tips
Essential Examination Strategies:
- Always number your stages in reverse order (from destination backwards)
- Show all calculations clearly in your table
- Mark optimal choices with asterisks (*)
- Trace back through optimal choices to find the complete optimal path
- Remember that "optimal" could mean longest, shortest, maximum profit, or minimum cost depending on the question
Remember!
Key Points to Remember:
- Bellman's Principle states that optimal paths contain optimal sub-paths
- Multi-stage networks are solved using backwards induction - start from the destination and work backwards
- Use a systematic table approach with columns for Stage, State, Action, and Value
- Calculate values by adding edge weights to optimal values from the next stage
- The optimal path is found by following the chain of optimal decisions from source to destination
- Always clearly mark your optimal choices and show your working for full marks