Dynamic programming: Difference between revisions

Revision as of 19:06, 24 November 2015

Revision as of 19:39, 24 November 2015

Line 1:

{{Disputed|Memoization vs. Dynamic programming}}

{{Distinguish|Dynamic programming language|Dynamic algorithm|Dynamic problem}}

In [[mathematics]], [[management science]], [[economics]], [[computer science]], and [[bioinformatics]], '''dynamic programming''' is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions - ideally, using a memory-based data structure. The next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time at the expense of a (hopefully) modest expenditure in storage space. (Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup.) The act of storing solutions to subproblems is called "[[memoization]]". In contrast, a more naive method would not recognize that a particular subproblem has already been solved previously, and would repeatedly solve the same subproblem many times.

This approach is especially useful when the number of repeating subproblems [[exponential growth|grows exponentially]] as a function of the size of the input.

Dynamic programming is applicable to problems exhibiting the properties of [[overlapping subproblem]]s<ref>S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, ''''Algorithms'''', p 173, available at http://www.cs.berkeley.edu/~vazirani/algorithms.html</ref> and [[optimal substructure]] (described below). When applicable, the method takes far less time than other methods that don't take advantage of the subproblem overlap (like [[depth-first search]]).

Dynamic programming algorithms are used for optimization (for example, finding the shortest path between two points, or the fastest way to multiply many matrices). A dynamic programming algorithm will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem. The alternatives are many, such as using a [[greedy algorithm]], which picks the locally optimal choice at each branch in the road. The locally optimal choice may be a poor choice for the overall solution. While a greedy algorithm does not guarantee an optimal solution, it is often faster to calculate. Fortunately, some greedy algorithms (such as [[minimum spanning tree]]s) are proven to lead to the optimal solution.

Line 12 ⟶ 8:

For example, let's say that you have to get from point A to point B as fast as possible, in a given city, during rush hour. A dynamic programming algorithm will look at finding the shortest paths to points close to A, and use those solutions to eventually find the shortest path to B. On the other hand, a greedy algorithm will start you driving immediately and will pick the road that looks the fastest at every intersection. As you can imagine, this strategy might not lead to the fastest arrival time, since you might take some "easy" streets and then find yourself hopelessly stuck in a traffic jam.

<!-- Note to copyeditors: the term used here is "memoization", NOT "memorization". -->

Sometimes, applying memoization to a naive basic recursive solution already results in a dynamic programming solution with asymptotically optimal time complexity; however, the optimal solution to some problems requires more sophisticated dynamic programming algorithms. Some of these may be recursive as well but parametrized differently from the naive solution. Others can be more complicated and cannot be implemented as a recursive function with memoization. Examples of these are the two solutions to the Egg Dropping puzzle below.

Line 31 ⟶ 26:

There are two key attributes that a problem must have in order for dynamic programming to be applicable: [[optimal substructure]] and [[overlapping subproblem|overlapping sub-problem]]s. If a problem can be solved by combining optimal solutions to ''non-overlapping'' sub-problems, the strategy is called "[[Divide and conquer algorithm|divide and conquer]]" instead. This is why [[mergesort|merge sort]] and [[quicksort|quick sort]] are not classified as dynamic programming problems.

''Optimal substructure'' means that the solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems. Consequently, the first step towards devising a dynamic programming solution is to check whether the problem exhibits such optimal substructure. Such optimal substructures are usually described by means of [[recursion]]. 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 ''p₁'' from ''u'' to ''w'' and ''p₂'' 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]]''). 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.

''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. For example, consider the recursive formulation for generating the Fibonacci series: ''F''_''i'' = ''F''_{''i''&minus;1} + ''F''_{''i''&minus;2}, with base case ''F''₁&nbsp;=&nbsp;''F''₂&nbsp;=&nbsp;1. Then ''F''₄₃ =&nbsp;''F''₄₂&nbsp;+&nbsp;''F''₄₁, and ''F''₄₂ =&nbsp;''F''₄₁&nbsp;+&nbsp;''F''₄₀. Now ''F''₄₁ is being solved in the recursive sub-trees of both ''F''₄₃ as well as ''F''₄₂. 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 takes account of this fact and solves each sub-problem only once.