Динамическое программирование

Dynamic programming in control theory and the theory of computing systems is a way to solve complex problems by breaking them down into simpler subtasks. It is applicable to problems with an optimal substructure ( English ), which looks like a set of overlapping subtasks, the complexity of which is slightly less than the initial one. In this case, the computation time, compared with the “naive” methods, can be significantly reduced.

The key idea in dynamic programming is quite simple. As a rule, to solve the problem, it is required to solve separate parts of the problem (subtasks), and then combine the solutions of the subtasks into one common solution. Often, many of these subtasks are the same. The dynamic programming approach is to solve each subtask only once, thereby reducing the number of calculations. This is especially useful in cases where the number of recurring subtasks is exponentially large.

The method of dynamic programming from above is simply memorizing the results of solving those subtasks that can be re-encountered later. Dynamic programming from below involves the reformulation of a complex task as a recursive sequence of simpler subtasks.

Story

The phrase "dynamic programming" was first used in the 1940s by R. Bellman to describe the process of finding a solution to a problem, where the answer to one problem can be obtained only after solving the problem "preceding" it. In 1953, he clarified this definition to modern. Initially, this area was founded, as a system analysis and engineering, which was recognized by IEEE. Bellman's contribution to dynamic programming was perpetuated in the title of the Bellman equation, the central result of dynamic programming theory, which reformulates the optimization problem in a recursive form.

The word “programming” in the phrase “dynamic programming” in reality has almost nothing to do with “traditional” programming (code writing) and it makes sense as in the phrase “mathematical programming”, which is synonymous with the word “optimization”. Therefore, the word “program” in this context rather means the optimal sequence of actions for obtaining a solution to the problem. For example, a certain schedule of events at an exhibition is sometimes called a program. The program in this case is understood as a valid sequence of events.

The idea of ​​dynamic programming

Finding the shortest path in the graph from one vertex to another using the optimal substructure; a straight line indicates the shortest path between the vertices that it connects (intermediate path vertices are not shown); a wavy line indicates a long way; bold line is the final shortest path.

The subtask graph (the edge means that one problem depends on the solution of the other) for Fibonacci numbers (the graph is acyclic).

The optimal substructure in dynamic programming means that the optimal solution of smaller subtasks can be used to solve the original problem. For example, the shortest path in a graph from one vertex (denoted by s) to another (denoted by t) can be found as follows: first, consider the shortest path from all vertices adjacent to s to t, and then, taking into account the weights of the edges that s are connected to with adjacent vertices, choose the best path to t (through which vertex it is best to go). In general, we can solve the problem in which there is an optimal substructure, doing the following three steps.

1. Splitting a task into smaller subtasks.
2. Finding the optimal solution of subtasks recursively, doing the same three-step algorithm.
3. Using the obtained solution of subtasks for constructing solutions to the original problem.

Subtasks are solved by dividing them into even smaller subtasks, and so on, until they arrive at a trivial case of a problem that can be solved in constant time (the answer can be said right away). For example, if we need to find n!, Then the trivial task will be 1! = 1 (or 0! = 1).

Overlapping subtasks in dynamic programming mean subtasks that are used to solve a number of problems (not one) larger (that is, we do the same thing several times). A prime example is the calculation of the Fibonacci sequence, and - even in such a trivial case of calculating only two Fibonacci numbers, we have already calculated twice. If you continue further and count then will count two more times, so as to calculate will be needed again and . It turns out the following: a simple recursive approach will spend time on calculating solutions for problems that it has already solved.

To avoid such a course of events, we will save the decisions of the subtasks that we have already solved, and when we again need a solution of the subtasks, instead of calculating it again, we simply remove it from memory. This approach is called caching. Further optimizations can be done - for example, if we are sure that we no longer need a solution to a subtask, we can throw it out of memory, freeing it for other needs, or if the processor is idle and we know that a solution to some not yet counted subtasks, we will need in the future, we can solve them in advance.

Summarizing the above, we can say that dynamic programming uses the following properties of the problem:

• overlapping subtasks;
• optimal substructure;
• the ability to memorize the decisions of frequently occurring subtasks.

Dynamic programming usually takes two approaches to solving problems:

• downstream dynamic programming: the task is divided into smaller subtasks, they are solved and then combined to solve the original problem. Memorization is used to solve common subtasks.
• ascending dynamic programming: all subtasks that will later be needed to solve the original problem are calculated in advance and then used to build a solution to the original problem. This method is better than downstream programming in terms of the size of the required stack and the number of function calls, but sometimes it is not easy to figure out in advance which solution we will need in the future.

Programming languages ​​can memorize the result of a function call with a specific set of arguments (memoization) in order to speed up the “calculation by name”. In some languages, this feature is built in (for example, Scheme, Common Lisp, Perl), and in some it requires additional extensions (C ++).

Serial dynamic programming, which is included in all textbooks on operations research, and non-serial dynamic programming (NSDP), which is currently poorly known, although it was discovered in the 1960s, are known.

Normal dynamic programming is a special case of non-serial dynamic programming, where the graph of the relationship of variables is just a way. The NSDP, being a natural and general method for accounting for the structure of an optimization problem, considers the set of constraints and / or the objective function as a recursively computable function. This allows you to find a solution in stages, at each of the stages using the information obtained at the previous stages, and the effectiveness of this algorithm directly depends on the structure of the graph of the relationship of variables. If this graph is sufficiently sparse, then the amount of computation at each stage can be kept within reasonable limits.

One of the main properties of problems solved by dynamic programming is additivity. Nonadditive problems are solved by other methods. For example, many of the tasks for optimizing a company's investment are non-additive and are solved by comparing the value of a company with and without investment.

Classic dynamic programming problems

• The task of the greatest common subsequence: two sequences are given, it is required to find the longest common subsequence.
• The task of finding the largest increasing subsequence: given the sequence, you want to find the longest increasing subsequence.
• The problem of editorial distance (Levenshtein distance): two lines are given, it is required to find the minimum number of erasures, replacements and additions of characters that convert one line to another.
• The problem of calculating Fibonacci numbers
• The problem of the order of matrix multiplication: given the matrix , ..., , it is required to minimize the number of scalar operations for their multiplication.
• The problem of choosing a trajectory
• The task of consistent decision making
• The task of using labor
• Inventory management task
• The knapsack problem: from an unlimited set of items with the properties “cost” and “weight” it is required to select a certain number of items in such a way as to obtain the maximum total cost with a limited total weight.
• Floyd-Worshell algorithm: find the shortest distances between all vertices of a weighted oriented graph.
• Bellman-Ford algorithm: find the shortest path in a weighted graph between two given vertices.
• Maximum independent set of vertices in a tree: given a tree, find the maximum set of vertices, no two of which are connected by an edge.

Literature

• Bellman R. Dynamic programming. - M .: Publishing house of foreign literature, 1960.
• Kormen, T., Leiserson, Ch., Rivest, R., Stein, K. Chapter 15. Dynamic Programming // Algorithms: Construction and Analysis = Introduction to Algorithms, Ed. I.V. Krasikova. - 2nd ed. - M .: Williams, 2005. - 1296 p. - ISBN 5-8459-0857-4
• Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani Algorithms = Algorithms. - 1st ed. - McGraw-Hill Science / Engineering / Math, 2006. - P. 336. - ISBN 0073523402
• Akulich I.L. Chapter 4. Problems of dynamic programming // Mathematical programming in examples and problems. - M .: Higher School, 1986. - 319 p. - ISBN 5-06-002663-9.
• Bertele U., Brioshi F. Nonserial dynamic programming. - NY: Academic Press, 1972. - 235 pp.
• Scherbina O. A. On the non-material modification of the local algorithm for the decomposition of discrete optimization problems. Dynamic Systems, 2005, no. nineteen.
• Scherbina O. A. Methodological aspects of dynamic programming // Dynamic systems, 2007, vol. 22. - pp.21-36.
• Gabasov R., Kirillova FM Fundamentals of dynamic programming. - Minsk: BSU Publishing House, 1975. - 262 p.