Dynamic programming

Dynamic programming is an algorithmic method for solving optimization problems. The term was introduced in the 1940s by the American mathematician Richard Bellman, who applied this method in the field of control theory. In this context, it is also often spoken of Bellman's principle of dynamic programming.

Dynamic programming can then be used successfully if the optimization problem from many similar sub-problems is, and an optimal solution of the problem is composed of optimal solutions of the subproblems. This is called optimality principle of Bellman. In the first dynamic programming the optimal solutions of the smallest subproblems are directly computed and then composited to a suitable solution of a next largest part of the problem. This process continues it until the original problem has been solved. Once computed partial results are stored in a table. In subsequent calculations of similar sub-problems will make use of these temporary solutions, instead of calculating them each time. If the dynamic programming used consistently, it avoids costly recursion, because known partial results are reused.

In the control theory and related areas, one can use the principle of dynamic programming to derive such an equation (Hamilton -Jacobi - Bellman equation), whose solution gives the optimum value. The reasoning is as follows: If the problem is time-dependent, one can consider the optimal value of the cost functional at any given time. One then wonders what equation must satisfy the optimal solution, so that the objective function is maintained even at a later time, this leads to the Hamilton -Jacobi - Bellman equation. Thus, one can divide the problem into time steps, instead of having to solve it at once.

In physics, this principle had long been known, but not under this name. The transition from a global (all time points simultaneously ) corresponds to a time-dependent ( dynamic ) approach where the transformation of the Lagrange functionals in the Hamiltonian functional by means of the Legendre transformation.

Examples

  • CYK algorithm
  • Earley algorithm
  • Needleman - Wunsch algorithm
  • Smith -Waterman algorithm
  • Viterbi algorithm
  • Algorithm of Floyd and Warshall
  • Pseudopolynomieller algorithm for the knapsack problem
Richard E. Bellman Table (information) Functional (mathematics) Legendre-Transformation Earley parser Needleman–Wunsch algorithm Smith–Waterman algorithm Floyd–Warshall algorithm Pseudo-polynomial time Memoization Charles E. Leiserson Ron Rivest Kurt Mehlhorn Digital Object Identifier Integrated Authority File
250421
de