Scribd
Upload
345 views15 pages

Group 5 Dyn Prog

Dynamic programming is a technique that breaks down complex problems into simpler subproblems. It can be used to find optimal solutions through a recursive approach. The document provides an example of the stagecoach problem, which seeks to determine the route that minimizes total cost across four stages. Dynamic programming works backward from the final stage, using recursive relationships to determine the optimal policy for each previous stage based on the optimal policy for the next stage. Characteristics of problems suited to this approach include being divisible into stages with policy decisions and states that transform deterministically between stages.

Uploaded by

jmlaforteza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
345 views15 pages

Group 5 Dyn Prog

Dynamic programming is a technique that breaks down complex problems into simpler subproblems. It can be used to find optimal solutions through a recursive approach. The document provides an example of the stagecoach problem, which seeks to determine the route that minimizes total cost across four stages. Dynamic programming works backward from the final stage, using recursive relationships to determine the optimal policy for each previous stage based on the optimal policy for the next stage. Characteristics of problems suited to this approach include being divisible into stages with policy decisions and states that transform deterministically between stages.

Uploaded by

jmlaforteza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 15

OPTIMIZATION TECHNIQUES

DYNAMIC
PROGRAMMING
GROUP NO. 5

GALLEON, JAYCEE A.
LAFORTEZA, JAN MICHAEL
MAGPILY, ANDREI PAUL S.
MALLILLIN, GECILLE R.
REJANO, MARK EDWIL G.
WHAT IS DYNAMIC PROGRAMMING (DP)?

Mathematical technique for making a series of


interrelated decisions

Provides systematic procedure for determining


the optimal combination of decisions

Refers to simplifying a complicated problem by


breaking it down into simpler sub-problems in a
recursive manner
THE STAGECOACH PROBLEM
OBJECTIVE:

Determine the route that minimizes the


total cost of policy.

DECISION VARIABLES:
Xn ( n = 1, 2, 3, 4 )  immediate destination
on stage n
THUS, THE ROUTE IS:

where X4 = J
STAGES

1 2 3 4
SOLUTION PROCEDURE

When the fortune seeker has only one more stage


to go (n = 4)
When the fortune seeker has two more stages to go
(n = 3)
When n = 2
When n = 1
Summary:
Optimal routes

ACEHJ
ADEHJ
ADF IJ

All yield a total cost


of 11.
CHARACTERISTICS OF DP PROBLEMS

The problem can be divided into STAGES, with a


POLICY DECISION required at each stage.

Each stage has a number of STATES associated


with the beginning of that stage.

The effect of the policy decision at each stage is


to transform the current state to a state
associated with the beginning of the next stage.
CHARACTERISTICS OF DP PROBLEMS

The solution procedure is designed to find an


optimal policy for the overall problem.

Given the current state, an optimal policy for


the remaining stages is independent of the
policy decisions adopted in previous stages.

The solution procedure begins by finding the


optimal policy for the last stage.
CHARACTERISTICS OF DP PROBLEMS

A recursive relationship that identifies the


optimal policy for stage n, given the optimal
policy for stage n+1, is available.

The solution procedure starts at the end and


moves BACKWARD stage by stage.
DETERMINISTIC DYNAMIC PROGRAMMING

The state at the next stage is


completely determined by the state and
policy decision at the current stage

You might also like