Шпортько, О. В. та Малаш, К. М. та Shportko, A. V. та Malash, K. M. (2020) ЗАСТОСУВАННЯ МЕМОІЗАЦІЇ В ЗАДАЧАХ МІНІМІЗАЦІЇ КІЛЬКОСТІ ЗНАКІВ АРИФМЕТИЧНИХ ОПЕРАЦІЙ. Вісник Національного університету водного господарства та природокористування (2(90)). с. 127-143.

Text Vt9013.zax.pdf Download(327kB)

Анотація

В статті порівнюються способи розв’язання задачі мінімізації кількості додавань із застосуванням мемоізації на основі методів рекурсії та динамічного програмування. Наведено рекурентні формули прямого і зворотного ходу методу динамічного програмування для розв’язування цієї задачі. Визначено і обґрунтовано обмеження на проміжні результати її розв’язків. Наведено фрагменти програм мовою C# для реалізації запропонованих способів мінімізації кількості додавань. Показано, що використання мемоізації для відсікання неефективних варіантів перебору дає змогу прискорити виконання відповідних алгоритмів в десятки разів.

Title in English

MEMOIZATION USING IN THE PROBLEMS OF MINIMIZATION OF SIGNS OF THE ARITHMETIC OPERATIONS NUMBER

English abstract

The article compares two ways of solving the arithmetic operations of placement of signs based on the use of memoization: method is based on recursion and dynamic programming. Limitations of the intermediate results of the problem solution are identified and justified. It is shown that the use of memoization in order to cut off ineffective search options makes it possible to accelerate the corresponding of algorithms execution for tens times. Analyzing the results of the study, the following conclusions were obtained: 1. Memoization should be used not only to speed up the execution of recursive calls, but also to implement the dynamic programming method and, in general, to reduce the number of nested cycles, which will significantly accelerate the execution of programs. At the same time, only the results of the calculations should be stored, which can be used in the future repeatedly. 2. In order to accelerate the solution of sequential decisionmaking problems, it is reasonable to use a dynamic programming method in the algorithmization process rather than recursive calls of subroutines. Although the implementations of this method require a large amount of memory to backfire, they do not store in the stack the values of all local variables for each recursive call every time. 3. To save RAM, the values of the state variables and the target function should be stored only for the current and previous steps of the dynamic programming method, and for all steps and states of the system, only a minimum of data should be stored to provide a solution during the reverse process of this method. 4. In the process of implementing the dynamic programming method, it is reasonable to consider not only the target function, but also the variable of each state. It takes a lot of machine time using the memorization method of solving the problem and not only saves memory while not storing the invalid values, but also speeds up calculations for the future states significantly.

Перегляд елементу

Завантажень