Dynamic programming, basic principles

To select the optimal solution for programming tasks, it is sometimes necessary to go through a large number of data combinations, which loads the memory of the personal computer. Such methods include, for example, the "divide and conquer" programming method. In this case, the algorithm provides for the separation of the task into individual small subtasks. This method is used only in cases where small subtasks are independent of each other. In order to avoid doing unnecessary work in the event that the subtasks are interdependent, the dynamic programming method proposed by the American R. Bellman in the 1950s is used.

The essence of the method

Dynamic programming consists in determining the optimal solution of the n-dimensional problem, dividing its n separate steps. Each of them is a subtask with respect to one variable.

The main advantage of this approach can be considered that developers are engaged in one-dimensional optimization tasks of subtasks instead of the n-dimensional problem, and the solution of the main task is going "from the bottom up".

It is advisable to apply dynamic programming in those cases where the subtasks are interrelated, i.e. Have common modules. The algorithm provides a solution to each of the subtasks once, and the replies are saved in a special table. This makes it possible not to calculate the answer anew when meeting a similar subtask.

The task of dynamic programming solves the problem of optimization. The author of this method R. Bellman formulated the principle of optimality: whatever the initial state at each step and the solution determined at this step, all the following are chosen to be optimal with respect to the state that the system takes at the end of the step.

The method improves the performance of tasks that are solved by searching variants or recursions.

Construction of the algorithm of the problem

Dynamic programming assumes the construction of such an algorithm of tasks, in which the task is divided into two or more sub-tasks so that its solution is formed from the optimal solution of all the subtasks included in it. Further, there arises the need for writing a recurrence relation and calculating the optimal parameter value for the problem as a whole.

Sometimes, at the third step, you need to remember additionally some auxiliary information about the progress of each subtask. This is called the reverse.

Application of the method

Dynamic programming is used when there are two characteristic features:

• Optimality for subtasks;
• Presence of overlapping subtasks in the problem.

Solving the optimization problem by the method of dynamic programming, it is first necessary to describe the structure of the solution. The problem is optimal if the solution of the problem consists of the optimal solutions of its subtasks. In this case, it is advisable to use dynamic programming.

The second property of the problem, which is essential for this method, is a small number of subtasks. The recursive solution of the problem uses the same overlapping subtasks, the number of which depends on the size of the initial information. The answer is stored in a special table, the program saves time, using this data.

Particularly effective is the use of dynamic programming when, in essence, tasks need to be taken step-by-step. For example, consider a simple example of the task of replacing and repairing equipment. Suppose, on the casting machine of a tire manufacturing plant, tires are made simultaneously in two different forms. In the event that one of the forms fails, you have to disassemble the machine. It is clear that sometimes it is more advantageous to replace the second form in order not to disassemble the machine in case, and this form will be inefficient at the next stage. Moreover, it is easier to replace both operating forms before they start to fail. The method of dynamic programming determines the best strategy in the question of replacing such forms, taking into account all factors: the benefit of continuing the operation of forms, the loss from idle machines, the cost of rejected tires, and more.