Dynamic programming (referred
to as DP ) is a very powerful technique to solve a particular
class of problems. It demands elegant formulation of the approach and simple
thinking. The idea is very simple, If you have solved a problem with the given
input, then save the result for future reference, so as to avoid solving the
same problem again. If the given problem can be broken up into smaller
sub-problems and these smaller sub-problems are in turn divided into smaller
ones, and in this process, if you observe some over-lapping sub-problems, then
its a big hint for DP. Also, the optimal solutions to the sub-problems
contribute to the optimal solution of the given problem.
There are two ways
of doing this.
1.) Top-Down : Start
solving the given problem by breaking it down. If you see that the problem has
been solved already, then just return the saved answer. If it has not been
solved, solve it and save the answer. This is usually easy to think of and very
intuitive. This is referred to as Memoization.
2.) Bottom-Up : Analyze
the problem and see the order in which the sub-problems are solved and start
solving from the trivial sub-problem, up towards the given problem. In this
process, it is guaranteed that the sub-problems are solved before solving the
problem. This is referred to as Dynamic Programming.
Obtaining
a solution to a dynamic programming problem
(1) Find
a recursive relation. If you are already have your recursive relation, go
to the implementation stage that starts from (4). Read the problem
carefully, and find out if you could divide the problem into sub-problems.
The most important thing for dynamic programming is that you should prove
that the solution of the higher-level problem expressed in optimal
solutions of the sub-problems is optimal. This part might be tough; if you
can’t figure out a recursive relation, try the "Backtrack Branch and
Bound" method. By doing that you might find a recursive relation
between sub-problems.
(2) What
is the answer of the problem? Now express your global optimal solution
in terms of the recursive relation that you found in the previous stage
(1).
(3) Try an
example to verify the recursive relation. Try a simple example by
walking through the recursion. You would get an insight whether
your relation is right or wrong.
(4) Express
the recursive relation top-down. First write down the trivial cases
(i.e. boundary cases), and then make the top-level function using the
previous function.
(5) Use
memoization to eliminate redundancy. After writing down the recursion, enter
the recursive function to calculate the solution for each stage.
(6) Express
the recursive relation bottom-up. The top-down approach divides the
problem top to bottom, and after hitting the trivial cases (i.e., boundary
cases) it climbs up the ladder. The bottom-up approach starts from the
trivial cases and goes up.
(7) Parallelize.
If your solution is not fast enough, you have two options. Either find a
more efficient recursive relation in terms of time complexity and start
again from step (1), or parallelize your program.
Invariant
1. Pre-condition.
The problem has a provable optimal substructure, which can be used to
get a globally
optimal solution
2. Invariant.
Locally optimal solutions are computed in the order defined by the structure
of the problem to
lead to a globally optimal solution
3. Post-condition.
The globally optimal solution is found.
Bellman's Optimality Principle
The principle that an optimal sequence of decisions in a multistage decision process problem has the property that whatever the initial state and decisions are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decisions.
Deterministic Dynamic
Programming
Deterministic problems are the ones where the state
at the next stage is completely determined by the state and policy decision at
the current stage. Deterministic dynamic programming problems are categorized
by the form of the objective function. For example, the objective
might be to minimize the sum of the contributions from the individual stages
(as for the stagecoach problem), or to maximize such a sum, or to minimize
a product of such terms, and so on. Another categorization is in terms of
the nature of the set of states for the respective stages.
Probabilistic
Dynamic Programming
Probabilistic dynamic programming differs from
deterministic dynamic programming in that the state at the next stage is not
completely determined by the state and policy decision at the current stage.
Rather, there is a probability distribution for what the next state will be.
However, this probability distribution still is completely determined by the
state and policy decision at the current stage.
Comments