Dynamic programming

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Not to be confused with Dynamic programming language or Dynamic problem. Dynamic programming_sentence_0

Dynamic programming is both a mathematical optimization method and a computer programming method. Dynamic programming_sentence_1

The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics. Dynamic programming_sentence_2

In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner. Dynamic programming_sentence_3

While some decision problems cannot be taken apart this way, decisions that span several points in time do often break apart recursively. Dynamic programming_sentence_4

Likewise, in computer science, if a problem can be solved optimally by breaking it into sub-problems and then recursively finding the optimal solutions to the sub-problems, then it is said to have optimal substructure. Dynamic programming_sentence_5

If sub-problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable, then there is a relation between the value of the larger problem and the values of the sub-problems. Dynamic programming_sentence_6

In the optimization literature this relationship is called the Bellman equation. Dynamic programming_sentence_7

Overview Dynamic programming_section_0

Mathematical optimization Dynamic programming_section_1

In terms of mathematical optimization, dynamic programming usually refers to simplifying a decision by breaking it down into a sequence of decision steps over time. Dynamic programming_sentence_8

This is done by defining a sequence of value functions V1, V2, ..., Vn taking y as an argument representing the state of the system at times i from 1 to n. The definition of Vn(y) is the value obtained in state y at the last time n. The values Vi at earlier times i = n −1, n − 2, ..., 2, 1 can be found by working backwards, using a recursive relationship called the Bellman equation. Dynamic programming_sentence_9

For i = 2, ..., n, Vi−1 at any state y is calculated from Vi by maximizing a simple function (usually the sum) of the gain from a decision at time i − 1 and the function Vi at the new state of the system if this decision is made. Dynamic programming_sentence_10

Since Vi has already been calculated for the needed states, the above operation yields Vi−1 for those states. Dynamic programming_sentence_11

Finally, V1 at the initial state of the system is the value of the optimal solution. Dynamic programming_sentence_12

The optimal values of the decision variables can be recovered, one by one, by tracking back the calculations already performed. Dynamic programming_sentence_13

Control theory Dynamic programming_section_2

Alternatively, the continuous process can be approximated by a discrete system, which leads to a following recurrence relation analog to the Hamilton–Jacobi–Bellman equation: Dynamic programming_sentence_14

Example from economics: Ramsey's problem of optimal saving Dynamic programming_section_3

See also: Ramsey–Cass–Koopmans model Dynamic programming_sentence_15

which can be simplified to Dynamic programming_sentence_16

We see that it is optimal to consume a larger fraction of current wealth as one gets older, finally consuming all remaining wealth in period T, the last period of life. Dynamic programming_sentence_17

Computer programming Dynamic programming_section_4

There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. Dynamic programming_sentence_18

If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called "divide and conquer" instead. Dynamic programming_sentence_19

This is why merge sort and quick sort are not classified as dynamic programming problems. Dynamic programming_sentence_20

Optimal substructure means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. Dynamic programming_sentence_21

Such optimal substructures are usually described by means of recursion. Dynamic programming_sentence_22

For example, given a graph G=(V,E), the shortest path p from a vertex u to a vertex v exhibits optimal substructure: take any intermediate vertex w on this shortest path p. If p is truly the shortest path, then it can be split into sub-paths p1 from u to w and p2 from w to v such that these, in turn, are indeed the shortest paths between the corresponding vertices (by the simple cut-and-paste argument described in Introduction to Algorithms). Dynamic programming_sentence_23

Hence, one can easily formulate the solution for finding shortest paths in a recursive manner, which is what the Bellman–Ford algorithm or the Floyd–Warshall algorithm does. Dynamic programming_sentence_24

Overlapping sub-problems means that the space of sub-problems must be small, that is, any recursive algorithm solving the problem should solve the same sub-problems over and over, rather than generating new sub-problems. Dynamic programming_sentence_25

For example, consider the recursive formulation for generating the Fibonacci series: Fi = Fi−1 + Fi−2, with base case F1 = F2 = 1. Dynamic programming_sentence_26

Then F43 = F42 + F41, and F42 = F41 + F40. Dynamic programming_sentence_27

Now F41 is being solved in the recursive sub-trees of both F43 as well as F42. Dynamic programming_sentence_28

Even though the total number of sub-problems is actually small (only 43 of them), we end up solving the same problems over and over if we adopt a naive recursive solution such as this. Dynamic programming_sentence_29

Dynamic programming takes account of this fact and solves each sub-problem only once. Dynamic programming_sentence_30

This can be achieved in either of two ways: Dynamic programming_sentence_31

Dynamic programming_unordered_list_0

  • Top-down approach: This is the direct fall-out of the recursive formulation of any problem. If the solution to any problem can be formulated recursively using the solution to its sub-problems, and if its sub-problems are overlapping, then one can easily memoize or store the solutions to the sub-problems in a table. Whenever we attempt to solve a new sub-problem, we first check the table to see if it is already solved. If a solution has been recorded, we can use it directly, otherwise we solve the sub-problem and add its solution to the table.Dynamic programming_item_0_0
  • Bottom-up approach: Once we formulate the solution to a problem recursively as in terms of its sub-problems, we can try reformulating the problem in a bottom-up fashion: try solving the sub-problems first and use their solutions to build-on and arrive at solutions to bigger sub-problems. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger sub-problems by using the solutions to small sub-problems. For example, if we already know the values of F41 and F40, we can directly calculate the value of F42.Dynamic programming_item_0_1

Some programming languages 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). Dynamic programming_sentence_32

Some languages make it possible portably (e.g. Scheme, Common Lisp, Perl or D). Dynamic programming_sentence_33

Some languages have automatic memoization built in, such as tabled Prolog and J, which supports memoization with the M. adverb. Dynamic programming_sentence_34

In any case, this is only possible for a referentially transparent function. Dynamic programming_sentence_35

Memoization is also encountered as an easily accessible design pattern within term-rewrite based languages such as Wolfram Language. Dynamic programming_sentence_36

Bioinformatics Dynamic programming_section_5

Dynamic programming is widely used in bioinformatics for the tasks such as sequence alignment, protein folding, RNA structure prediction and protein-DNA binding. Dynamic programming_sentence_37

The first dynamic programming algorithms for protein-DNA binding were developed in the 1970s independently by Charles DeLisi in USA and Georgii Gurskii and Alexander Zasedatelev in USSR. Dynamic programming_sentence_38

Recently these algorithms have become very popular in bioinformatics and computational biology, particularly in the studies of nucleosome positioning and transcription factor binding. Dynamic programming_sentence_39

Examples: Computer algorithms Dynamic programming_section_6

Dijkstra's algorithm for the shortest path problem Dynamic programming_section_7

From a dynamic programming point of view, Dijkstra's algorithm for the shortest path problem is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method. Dynamic programming_sentence_40

In fact, Dijkstra's explanation of the logic behind the algorithm, namely Dynamic programming_sentence_41

is a paraphrasing of Bellman's famous Principle of Optimality in the context of the shortest path problem. Dynamic programming_sentence_42

Fibonacci sequence Dynamic programming_section_8

Using dynamic programming in the calculation of the nth member of the Fibonacci sequence improves its performance greatly. Dynamic programming_sentence_43

Here is a naïve implementation, based directly on the mathematical definition: Dynamic programming_sentence_44

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times: Dynamic programming_sentence_45

Dynamic programming_ordered_list_1

  1. fib(5)Dynamic programming_item_1_2
  2. fib(4) + fib(3)Dynamic programming_item_1_3
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))Dynamic programming_item_1_4
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))Dynamic programming_item_1_5
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))Dynamic programming_item_1_6

In particular, fib(2) was calculated three times from scratch. Dynamic programming_sentence_46

In larger examples, many more values of fib, or subproblems, are recalculated, leading to an exponential time algorithm. Dynamic programming_sentence_47

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. Dynamic programming_sentence_48

The resulting function requires only O(n) time instead of exponential time (but requires O(n) space): Dynamic programming_sentence_49

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. Dynamic programming_sentence_50

In the bottom-up approach, we calculate the smaller values of fib first, then build larger values from them. Dynamic programming_sentence_51

This method also uses O(n) time since it contains a loop that repeats n − 1 times, but it only takes constant (O(1)) space, in contrast to the top-down approach which requires O(n) space to store the map. Dynamic programming_sentence_52

In both 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. Dynamic programming_sentence_53

A type of balanced 0–1 matrix Dynamic programming_section_9

Checkerboard Dynamic programming_section_10

Sequence alignment Dynamic programming_section_11

In genetics, sequence alignment is an important application where dynamic programming is essential. Dynamic programming_sentence_54

Typically, the problem consists of transforming one sequence into another using edit operations that replace, insert, or remove an element. Dynamic programming_sentence_55

Each operation has an associated cost, and the goal is to find the sequence of edits with the lowest total cost. Dynamic programming_sentence_56

The problem can be stated naturally as a recursion, a sequence A is optimally edited into a sequence B by either: Dynamic programming_sentence_57

Dynamic programming_ordered_list_2

  1. inserting the first character of B, and performing an optimal alignment of A and the tail of BDynamic programming_item_2_7
  2. deleting the first character of A, and performing the optimal alignment of the tail of A and BDynamic programming_item_2_8
  3. replacing the first character of A with the first character of B, and performing optimal alignments of the tails of A and B.Dynamic programming_item_2_9

The partial alignments can be tabulated in a matrix, where cell (i,j) contains the cost of the optimal alignment of A[1..i] to B[1..j]. Dynamic programming_sentence_58

The cost in cell (i,j) can be calculated by adding the cost of the relevant operations to the cost of its neighboring cells, and selecting the optimum. Dynamic programming_sentence_59

Different variants exist, see Smith–Waterman algorithm and Needleman–Wunsch algorithm. Dynamic programming_sentence_60

Tower of Hanoi puzzle Dynamic programming_section_12

The Tower of Hanoi or Towers of Hanoi is a mathematical game or puzzle. Dynamic programming_sentence_61

It consists of three rods, and a number of disks of different sizes which can slide onto any rod. Dynamic programming_sentence_62

The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape. Dynamic programming_sentence_63

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules: Dynamic programming_sentence_64

Dynamic programming_unordered_list_3

  • Only one disk may be moved at a time.Dynamic programming_item_3_10
  • Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.Dynamic programming_item_3_11
  • No disk may be placed on top of a smaller disk.Dynamic programming_item_3_12

The dynamic programming solution consists of solving the functional equation Dynamic programming_sentence_65

Dynamic programming_description_list_4

  • S(n,h,t) = S(n-1,h, not(h,t)) ; S(1,h,t) ; S(n-1,not(h,t),t)Dynamic programming_item_4_13

where n denotes the number of disks to be moved, h denotes the home rod, t denotes the target rod, not(h,t) denotes the third rod (neither h nor t), ";" denotes concatenation, and Dynamic programming_sentence_66

Dynamic programming_description_list_5

  • S(n, h, t) := solution to a problem consisting of n disks that are to be moved from rod h to rod t.Dynamic programming_item_5_14

For n=1 the problem is trivial, namely S(1,h,t) = "move a disk from rod h to rod t" (there is only one disk left). Dynamic programming_sentence_67

The number of moves required by this solution is 2 − 1. Dynamic programming_sentence_68

If the objective is to maximize the number of moves (without cycling) then the dynamic programming functional equation is slightly more complicated and 3 − 1 moves are required. Dynamic programming_sentence_69

Egg dropping puzzle Dynamic programming_section_13

The following is a description of the instance of this famous puzzle involving N=2 eggs and a building with H=36 floors: Dynamic programming_sentence_70

Dynamic programming_description_list_6

  • Suppose that we wish to know which stories in a 36-story building are safe to drop eggs from, and which will cause the eggs to break on landing (using U.S. English terminology, in which the first floor is at ground level). We make a few assumptions:Dynamic programming_item_6_15

Dynamic programming_description_list_7

  • Dynamic programming_item_7_16
    • An egg that survives a fall can be used again.Dynamic programming_item_7_17
    • A broken egg must be discarded.Dynamic programming_item_7_18
    • The effect of a fall is the same for all eggs.Dynamic programming_item_7_19
    • If an egg breaks when dropped, then it would break if dropped from a higher window.Dynamic programming_item_7_20
    • If an egg survives a fall, then it would survive a shorter fall.Dynamic programming_item_7_21
    • It is not ruled out that the first-floor windows break eggs, nor is it ruled out that eggs can survive the 36th-floor windows.Dynamic programming_item_7_22

Dynamic programming_description_list_8

  • If only one egg is available and we wish to be sure of obtaining the right result, the experiment can be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from the second-floor window. Continue upward until it breaks. In the worst case, this method may require 36 droppings. Suppose 2 eggs are available. What is the lowest number of egg-droppings that is guaranteed to work in all cases?Dynamic programming_item_8_23

To derive a dynamic programming functional equation for this puzzle, let the state of the dynamic programming model be a pair s = (n,k), where Dynamic programming_sentence_71

Dynamic programming_description_list_9

  • n = number of test eggs available, n = 0, 1, 2, 3, ..., N − 1.Dynamic programming_item_9_24
  • k = number of (consecutive) floors yet to be tested, k = 0, 1, 2, ..., H − 1.Dynamic programming_item_9_25

For instance, s = (2,6) indicates that two test eggs are available and 6 (consecutive) floors are yet to be tested. Dynamic programming_sentence_72

The initial state of the process is s = (N,H) where N denotes the number of test eggs available at the commencement of the experiment. Dynamic programming_sentence_73

The process terminates either when there are no more test eggs (n = 0) or when k = 0, whichever occurs first. Dynamic programming_sentence_74

If termination occurs at state s = (0,k) and k > 0, then the test failed. Dynamic programming_sentence_75

Now, let Dynamic programming_sentence_76

Dynamic programming_description_list_10

  • W(n,k) = minimum number of trials required to identify the value of the critical floor under the worst-case scenario given that the process is in state s = (n,k).Dynamic programming_item_10_26

Then it can be shown that Dynamic programming_sentence_77

Dynamic programming_description_list_11

  • W(n,k) = 1 + min{max(W(n − 1, x − 1), W(n,k − x)): x = 1, 2, ..., k }Dynamic programming_item_11_27

with W(n,0) = 0 for all n > 0 and W(1,k) = k for all k. It is easy to solve this equation iteratively by systematically increasing the values of n and k. Dynamic programming_sentence_78

Faster DP solution using a different parametrization Dynamic programming_section_14

Matrix chain multiplication Dynamic programming_section_15

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Dynamic programming.