Введение в динамическое программирование и мемоизацию

Привет 🖐️

Меня зовут Милад и добро пожаловать в мой блог. В этом посте мы в двух словах изучим динамическое программирование и мемоизацию; Так что оставайтесь со мной в этом удивительном и веселом путешествии.

Что такое динамическое программирование и мемоизация

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

Мемоизация. Это особый метод кэширования промежуточных результатов для ускорения вычислений. Оно происходит от слова «memo», означающего запоминание или запоминание значений, и работает путем поддержания сопоставления входных данных с рассчитанными выходными данными, так что, когда значение снова потребуется, оно ищется, а не пересчитывается. Это полезно для рекурсивных функций, которые повторяют вычисления для одних и тех же входных данных.

Почему они имеют значение

Динамическое программирование и мемоизация — важные методы в информатике и оптимизации, поскольку они могут значительно повысить производительность алгоритмов. Есть несколько основных причин, почему они важны:

Повышает эффективность. Благодаря сохранению промежуточных результатов вместо их повторного вычисления динамическое программирование позволяет избежать ненужных повторных вычислений. Это может улучшить скорость алгоритма с экспоненциального до линейного времени.
Решает более серьезные проблемы. Многие сложные проблемы имеют оптимальную подструктуру, подходящую для подхода динамического программирования. Это позволяет решать более масштабные задачи.
Элегантное решение проблем. Динамическое программирование разбивает проблемы на перекрывающиеся подзадачи. Этот модульный подход зачастую чище и проще для понимания.
Возможности оптимизации. Динамическое программирование хорошо подходит для поиска оптимальных решений проблем путем рассмотрения всех возможностей и сохранения оптимальных подрешений.
Эффективное использование пространства. Благодаря кэшированию результатов динамическое программирование сокращает количество избыточных вычислений и не тратит пространство на поиск неоптимальных решений.

Когда мы сможем их использовать

Динамическое программирование и запоминание можно применять к задачам, которые демонстрируют две ключевые особенности:

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

Ключевым критерием является то, что проблему можно разделить на более мелкие перекрывающиеся подзадачи, и объединение их оптимальных решений приводит к оптимальному решению всей проблемы. Проблемы с этой структурой можно эффективно решить с помощью динамического программирования.

Понимание концепции на простом примере

Допустим, у нас есть функция, выполнение которой занимает много времени, а именно:

function addTo100(n) {
    console.log("Long time");
    return 100 + n;
}

Теперь давайте запустим его:

console.log(addTo100(5));
/*
Output:

Long time
105
*/

Как видите, функция возвращает результат после длительного выполнения. А что, если мы запустим его 5 раз подряд с одним и тем же входным значением:

console.log(addTo100(5));
console.log(addTo100(5));
console.log(addTo100(5));
console.log(addTo100(5));
console.log(addTo100(5));
/*
Output:

Long time
105
Long time
105
Long time
105
Long time
105
Long time
105
*/

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

// Map variable to store input and corresponding outputs
const cache = {};

function memoizedAddTo100(n) {
    // If n is in cache variable, just pick it up and return it
    if (n in cache) return cache[n];
    // Otherwise take a long time to calculate it for the first time
    console.log("Long time");
    // Then put it in the cache variable
    cache[n] = 100 + n;
    // And finally return the output value
    return cache[n];
}

На этот раз давайте запустим запомненную функцию 5 раз подряд с одним и тем же входным значением:

console.log(memoizedAddTo100(5));
console.log(memoizedAddTo100(5));
console.log(memoizedAddTo100(5));
console.log(memoizedAddTo100(5));
console.log(memoizedAddTo100(5));

/*
Output:

Long time
105
105
105
105
105
*/

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

Известный пример для обсуждения

Последовательность Фибоначчи — это ряд чисел, где каждое число представляет собой сумму двух предыдущих. Последовательность начинается с 0 и 1 и выглядит следующим образом:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987…

Последовательность следует рекурсивным отношениям:

F(n) = F(n-1) + F(n-2)

Где F(n) — n-е число Фибоначчи. Первые несколько чисел Фибоначчи:

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0) = 1

F(3) = F(2) + F(1) = 2

F(4) = F(3) + F(2) = 3

F(5) = F(4) + F(3) = 5

и так далее…

Мы собираемся реализовать функцию, которая вычисляет значение n-го числа Фибоначчи, используя рекурсию:

// This variable records the number of operations that the function
// have been done in order to calculate nth fibonacci number
let numCalculationsRegularFib = 0;

function fibonacci(n) {
    // Time complexity: O(2^n)
    if (n < 2) return n;    // For all n less than 2, return n itself
    numCalculationsRegularFib++;// Increase by one
    // recursive call of two previous ones
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Допустим, мы собираемся узнать 30-е число Фибоначчи, используя приведенную выше функцию:

const fib30 = fibonacci(30);
console.log(`Fib(30): ${fib30}`);
console.log(`${numCalculationsRegularFib} operations have been done for calculating fib(30)`);

/*
Output:

Fib(30): 832040
1346268 operations have been done for calculating fib(30)
*/

Подожди!, Что?! 1346268 операций; Да, именно поэтому его временная сложность равна O(2^n).

Как видно из приведенной выше диаграммы, O(2^n) — это вторая худшая временная сложность, и нам необходимо оптимизировать предыдущий алгоритм, используя методы динамического программирования и запоминания.

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

Давайте реализуем новый алгоритм Фибоначчи, мемоизированный:

// Cache variable to store the result of calculations
const fibCache = {};
// This variable records the number of operations that the function
// have been done in order to calculate nth fibonacci number
let numCalculationsMemoizedFib = 0

function memoizedFibonacci(n) {
    // Time complexity: O(n)
    // If we calculated fib(n) before, pick up its value from cache
    if (n in fibCache) return fibCache[n];
    else {    // Otherwise
        // For all n less than 2, return n itself
        if (n < 2) return n;
        numCalculationsMemoizedFib++;    // increase by one
        // Make a recursive call and store it in the cache variable
        fibCache[n] =  memoizedFibonacci(n - 1) + memoizedFibonacci(n - 2);
        return fibCache[n];
    }
}

Теперь предположим, что мы собираемся еще раз узнать 30-е число Фибоначчи, используя новую функцию выше:

const memoizedFib30 = memoizedFibonacci(30);
console.log(`Fib(30): ${memoizedFib30}`);
console.log(`${numCalculationsMemoizedFib} operations have been done for calculating fib(30)`);

/*
Output:

Fib(30): 832040
29 operations have been done for calculating fib(30)
*/

Поздравляем, мы сделали это; мы только что оптимизировали нашу функцию, используя возможности техники запоминания, и вычислили Fib(30), используя 29 операций вместо 1346268, Да 🦾. Более того, еще одна оптимизация, которую мы сделали, заключалась в том, что мы оптимизировали O(2^n) до O(n), что является приемлемой временной сложностью.

Заключение

Динамическое программирование и запоминание — это мощные и универсальные методы, которые могут помочь оптимизировать производительность алгоритмов. Сохраняя промежуточные результаты и повторно используя предыдущие вычисления, динамическое программирование позволяет решать сложные проблемы, которые в противном случае были бы невозможны.

Надеюсь, вам понравилось, увидимся в следующий раз 👋

Введение в динамическое программирование и мемоизацию