| Dynamic Programming |
Article Index for Dynamic |
Articles about Dynamic Programming |
Website Links For Dynamic |
Information AboutDynamic Programming |
| CATEGORIES ABOUT DYNAMIC PROGRAMMING | |
| control theory | |
| optimization algorithms | |
| systems engineeringcontrol theory | |
| optimization algorithms | |
| systems engineering | |
| programming paradigms | |
|
Mathematician Richard Bellman invented dynamic programming in 1953 . The field was founded as a systems analysis and engineering topic which is recognized by the IEEE . OVERVIEW ''Optimal substructure'' means that optimal solutions of subproblems can be used to find the optimal solutions of the overall problem. For example, the Shortest Path to a goal from a vertex in a Graph can be found by first computing the shortest path to the goal from all adjacent vertices, and then using this to pick the best overall path, as shown in Figure 1. In general, we can solve a problem with optimal substructure using a three-step process: # Break the problem into smaller subproblems. # Solve these problems optimally using this three-step process recursively. # Use these optimal solutions to construct an optimal solution for the original problem. The subproblems are, themselves, solved by dividing them into sub-subproblems, and so on, until we reach some simple case that is easy to solve. but a DAG indicates overlapping subproblems.]] To say that a problem has ''overlapping subproblems'' is to say that the same subproblems are used to solve many different larger problems. For example, in the Fibonacci Sequence , F3 = F1 + F2 and F4 = F2 + F3 — computing each number involves computing F2. Because both F3 and F4 are needed to compute F5, a naïve approach to computing F5 may end up computing F2 twice or more. This applies whenever overlapping subproblems are present: a naïve approach may waste time recomputing optimal solutions to subproblems it has already solved. In order to avoid this, we instead save the solutions to problems we have already solved. Then, if we need to solve the same problem later, we can retrieve and reuse our already-computed solution. This approach is called '' Memoization '' (not ''memorization'', although this term also fits). If we are sure we won't need a particular solution anymore, we can throw it away to save space. In some cases, we can even compute the solutions to subproblems we know that we'll need in advance. In summary, dynamic programming makes use of: Dynamic programming usually takes one of two approaches:
Originally, the term ''dynamic programming'' only applied to solving certain kinds of operational problems outside the area of Computer Science , just as '' Linear Programming '' did. In this context, it has no particular connection to Programming at all; the name is a coincidence. The term was also used in the 1940s by Richard Bellman , an American mathematician, to describe the process of solving problems where one needs to find the best decisions one after another. Some Functional Programming Language s, most notably Haskell , can automatically memoize the result of a function call with a particular set of arguments, in order to speed up Call-by-name evaluation (this mechanism is referred to as '' Call-by-need ''). This is only possible for a function which has no Side-effect s, which is always true in Haskell but seldom true in imperative languages. EXAMPLES Fibonacci sequence A naïve implementation of a function finding the ''n''th member of the Fibonacci Sequence , based directly on the mathematical definition, performs much redundant work: function fib(n) if n = 0 '''or''' n = 1 return n else return fib(n − 1) + fib(n − 2) Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:# fib(5)# fib(4) + fib(3)# (fib(3) + fib(2)) + (fib(2) + fib(1))# ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))# (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))In particular, fib(2) was calculated twice from scratch. In larger examples, many more values of fib, or ''subproblems'', are recalculated, leading to an exponential time algorithm.Now, suppose we have a simple Map object, ''m'', which maps each value of fib that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O (''n'') time instead of exponential time:var m := '''map'''(0 → 1, 1 → 1) function fib(n) if n '''not in''' '''keys'''(m) m {Link without Title} := fib(n − 1) + fib(n − 2) return m {Link without Title} This technique of saving values that have already been calculated is called '' Memoization ''; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values. In this case, we can also reduce the function from using linear (O(''n'')) space to using constant space by changing our function to use a bottom-up approach which calculates smaller values of fib first, then build larger values from them:function fib(n) var previousFib := 1, currentFib := 1 repeat n − 1 '''times''' var newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib return currentFib This bottom-up version is close to the simple imperative loop that might be used to compute the Fibonacci function in an introductory computer science course. In both these examples, we only calculate fib(2) one time, and then use it to calculate both fib(4) and fib(3), instead of computing it every time either of them is evaluated.Checkerboard Consider a checkerboard with ''n'' × ''n'' squares and a cost-function ''c''(''i'', ''j'') which returns a cost associated with square ''i'',''j'' (''i'' being the row, ''j'' being the column). For instance (on a 5 × 5 checkerboard), +---+---+---+---+---+ |
|
|