Ленивая динамика

Материал из Algocode wiki
Перейти к: навигация, поиск

Одной частью решения задачи на ДП было установление порядка пересчета состояний - перед подсчетом нового состояния все те, от которого оно зависит, уже должны быть посчитаны.

Идея ленивого динамического программирования состоит в том, чтобы об этом не думать. Если мы уверены, что в графе состояний нет циклических зависимостей (то есть от текущего состояния по цепочке зависимостей мы не дойдем до него же самого), то можно отдать порядок пересчета на откуп рекурсии.

Реализуем подсчет состояния в виде рекурсивной функции. Вместо классического массива $dp[i][j]$, например, будет функция $calcDP(i, j)$. Она будет вызывать $calcDP(i - 1, j - 1)$ и $calcDP(i - 1, j)$. Чтобы наше решение не стало работать за экспоненту, будет запоминать результаты работы функций в отдельном массиве. Этот прием называется мемоизация (memoization). По-прежнему каждое состояние будет посчитано только один раз.

Во многих языках программирования мемоизация является встроенной оптимизацией.

В качестве примера рассмотрим вычисление фунцкии Аккермана (потому что считать числа Фибоначчи уже надоело).

 1 long long calc(int m, int n) {
 2     if (memoize[m][n] != 0) {
 3         return memoize[m][n];
 4     }
 5     if (m == 0) {
 6         return memoize[m][n] = n + 1;
 7     }
 8     if (n == 0) {
 9         return memoize[m][n] = calc(m - 1, n);
10     }
11     return memoize[m][n] = calc(m - 1, calc(m, n - 1));
12 }

В массиве $memoize$ сохраняются значения функции. Изначально мы предполагаем, что массив заполнен нулями, поэтому можно считать, что непосещенное состояние заполнено нулем, именно так мы понимаем, что в этом состоянии мы впервые. Здесь важно, что сама функция не принимает значения, равные нулю.

Несмотря на то что в ленивой динамике не надо думать о порядке пересчета, по эффективности этот метод в среднем уступает обычному подсчету, так как рекеурсивные вызовы требуют дополнительных затрат памяти, о которыз многие забывают. (Подробнее про рекурсию).

Если коротко, то при вызове подпрограммы необходимо запоминать информацию о том, откуда мы пришли в нее. Надо помнить, в какую точку надо будет пойти после выхода из подпрограммы, это дополнительные затраты памяти и времени.

Тем не менее, компиляторы умеют оптимизировать рекурсию в некоторых случаях. Например, существует хвостовая рекурсия - из программы происходит только один рекурсивный вызов. Такой тип рекурсии сразу разворачивается компилятором в цикл while.



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko