To select the optimal solution when performing programming tasks, it is sometimes necessary to sort through a large number of data combinations, which loads the memory of a personal computer. Such methods include, for example, the divide and conquer programming method. In this case, the algorithm provides for the division of the task into separate small subtasks. This method is used only in cases where small subtasks are independent of each other. In order to avoid doing unnecessary work if the subtasks are interdependent, we use the dynamic programming method proposed by the American R. Bellman in the 50s.
The essence of the method
Dynamic programming consists in determining the optimal solution to an n-dimensional problem, dividing it into n separate stages. Each of them is a subtask in relation to one variable.
The main advantage of this approach can be considered as the fact that developers are engaged in one-dimensional optimization problems of subtasks instead of an n-dimensional problem, and the solution to the main problem is collected “from bottom to top”.
It is advisable to use dynamic programming in cases where the subtasks are interconnected, i.e. have common modules. The algorithm provides for the solution of each of the subtasks once, and the answers are saved in a special table. This makes it possible not to re-calculate the answer when meeting with a similar subtask.
The dynamic programming problem solves the optimization problem. The author of this method, R. Bellman, formulated the principle of optimality: no matter what the initial state at each step is and the solution defined at this step, all of the following are chosen optimal with respect to the state that the system takes at the end of the step.
The method improves the execution of tasks solved by enumerating options or recursions.
Building a task algorithm
Dynamic programming involves the construction of such a task algorithm in which the task is so divided into two or more subtasks so that its solution consists of the optimal solution of all the subtasks included in it. Next, it becomes necessary to write a recurrence relation and calculate the optimal parameter value for the problem as a whole.
Sometimes at the 3rd step, you need to additionally remember some supporting information about the progress of each subtask. This is called a reverse stroke.
Method application
Dynamic programming is used when there are two characteristic features:
- optimality for subtasks;
- the presence of overlapping subtasks in the task.
Solving the optimization problem by the dynamic programming method, it is first necessary to describe the structure of the solution. A task is optimal if the solution to the problem consists of optimal solutions to its subtasks. In this case, it is advisable to use dynamic programming.
The second property of the problem, essential for this method, is a small number of subtasks. A recursive solution to the problem uses the same overlapping subtasks, the amount of which depends on the size of the source information. The answer is stored in a special table, the program saves time using this data.
The use of dynamic programming is especially effective when, in essence, tasks need to be made in stages. For example, consider a simple example of the task of replacing and repairing equipment. Let’s say, on a foundry of a tire factory, 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 profitable to replace the second form in order not to disassemble the car in case this form also turns out to be inoperative at the next stage. Moreover, it is easier to replace both working forms before they begin to fail. The dynamic programming method determines the best strategy for replacing such forms, taking into account all factors: the benefits of continued operation of the forms, loss from machine downtime, the cost of rejected tires, and more.