Рекурсивные методы решения задач динамического программирования

Recursion, caching, memoization, dynamic programming.

Динамическое программирование — способ решения сложных задач путём разбиения их на простые подзадачи. Применим данный метод к задачам с оптимальной подструктурой, которые выглядят, как набор перекрывающихся подзадач, с меньшей исходной сложностью. Ключевая идея в динамическом программировании относительно проста. Чтобы решить поставленную задачу, требуется решить отдельные части задачи, после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования заключается в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений [2]. Это особенно необходимо в случаях, когда число повторяющихся подзадач экспоненциально велико.

Решение задачи динамическим программированием должно содержать следующее:

• 1)    Зависимость элементов динамики друг от друга . Такая зависимость может быть прямо дана в условии (как правило возникает при решении задач на числовые последовательности). В противном случае можно попытаться узнать какой-то известный числовой ряд (например, чисел Фибоначчи), вычислив первые несколько значений вручную.

• 2)    Значение начальных состояний . В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно.

Перед тем, как перейти к непосредственному решению задач, рассмотрим понятие рекурсии. В математике рекурсия имеет отношение к методу определения функций и числовых рядов: рекурсивно заданная функция определяет своё значение через обращение к себе самой с другими аргументами. В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции [1].

В качестве примера рассмотрим задачу, решение которой будет рекурсивным.

Вычислить n-й член последовательности, заданной формулами: a2n an+an-1, a2n+1 an   an-1, ag = a1 = 1.

Здесь нам даны и начальные состояния (a 0 = a 1 = 1), и зависимости. Необходимо понимать, что 2n — условие чётности числа, а 2n+1 — нечётности. То есть, нет необходимости проверять, чётно ли число, и считать его в зависимости от этого по разным формулам. Решение данной задачи было написано на языке Java.

private static int f(int n){ if n==0 || n==l) return 1; // Проверка на начальное значение if(n%2==0){ //Проверка на чётность return f(n/2)+f(n/2-l); И Вычисляем по формуле для чётных индексов,

М ссылаясь на предыдущие значения }else{ return f((n-l)/2)-f((n-l)/2-l); H Вычисляем по формуле для нечётных //индексов, ссылаясь на предыдущие значения } }

Рисунок 1 – пример рекурсивного метода решения.

Данное решение хорошо работает, но есть особенности. Если необходимо вычислить f(12), то метод будет вычислять сумму f(6)+f(5). В то же время, f(6)=f(3)+f(2) и f(5)=f(2)-f(1), то есть значение f(2) будет вычисляться дважды. Решить данную проблему поможет — мемоизация или кеширование значений.

Идея мемоизации заключается в следующем. Единожды вычисляя значение, оно заносится в определенную структуру данных [3]. Перед каждым вычислением необходимо проверить, есть ли вычисляемое значение в этой структуре и, если оно существует, использовать его. В качестве структуры данных можно использовать массив, заполненный флаговыми значениями. Если значение элемента по индексу N равно значению флага, значит, его ещё не вычисляли. Это создаёт определённые трудности, так как значение флага не должно принадлежать множеству значений функции, которое не всегда очевидно [4]. Для этого отлично подойдёт использование хэш-таблицы — все действия в ней выполняются за O(1), что сильно поможет в решении задачи. Однако, при большом количестве значений два числа могут иметь одинаковый хэш, что, может порождать проблемы. В таком случае стоит использовать, например, красно-чёрное дерево поиска.

Для уже написанной функции f(int) кэширование значений будет выглядеть следующим образом:

private static HashMap();

}

Рисунок 2 – пример рекурсивного метода решения с кешированием значений.

Современное программирование всё больше помогает в решении сложных математических задач. Прогресс не стоит на месте, вычислительная мощность растёт и уже сегодня можно решать то, что несколько десятков лет назад казалось невозможным. Нестандартные алгоритмы и методы, позволяют находить новые подходы к решению задач. Именно такие рекурсивные методы динамического программирования позволяют решать сложные математические задачи с помощью современных языков высокого уровня, таких как Java.