Понимание динамического программирования для эффективного его использования

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

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

Термин «динамическое программирование» впервые был использован известным американским математиком, одним из ведущих специалистов в области компьютерных технологий Ричардом Беллманом еще в 1950-х годах. Динамическое программирование (ДП) — это метод решения сложных задач путем разбиения их на более мелкие подзадачи.

Тип проблем, которые может решить ДП, должен соответствовать двум критериям:

1. Оптимальная подструктура . Динамическое программирование означает, что решение более мелких подзадач можно использовать для решения первоначальной. Оптимальная субструктура является основной характеристикой парадигмы «Разделяй и властвуй».

Классическим примером реализации является алгоритм сортировки слиянием, в котором мы рекурсивно разбиваем задачу на простейшие подзадачи (массивы размера 1), после чего производим вычисления на основе каждой из них. Результаты используются для решения следующего уровня (более крупных подзадач) до тех пор, пока не будет достигнут начальный уровень.

2. Перекрывающиеся подзадачи . В информатике говорят, что проблема имеет перекрывающиеся подзадачи, если проблему можно разбить на подзадачи, которые используются повторно несколько раз. Другими словами, запуск одного и того же кода с теми же входными данными и теми же результатами. Классический пример этой задачи — вычисление N-го элемента последовательности Фибоначчи, который мы рассмотрим ниже.

Можно сказать, что ДП — это частный случай использования парадигмы «разделяй и властвуй» или ее более сложная версия. Паттерн хорошо подходит для решения задач комбинаторики, где рассчитывается большое количество различных комбинаций, но N-количество элементов зачастую монотонно и одинаково.

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

1. Мемоизация (нисходящий подход) реализуется посредством рекурсии. Задача разбивается на более мелкие подзадачи, их результаты сохраняются в памяти и объединяются для решения исходной задачи путем многократного использования.

• Минусы: этот подход использует стековую память посредством рекурсивных вызовов методов.
• Плюсы: Гибкость в решении задач DP.

2. Табуляция (подход «снизу вверх») реализуется итерационным методом. Подзадачи от самой маленькой до начальной вычисляются последовательно, итеративно.

• Минусы: ограниченный спектр применения. Этот подход требует первоначального понимания всей последовательности подзадач. Но в некоторых задачах это неосуществимо.
• Плюсы: эффективное использование памяти, поскольку все выполняется в рамках одной функции.

Теория может показаться скучной и непонятной — давайте рассмотрим несколько примеров.

Задача: последовательность Фибоначчи

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

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

Для этой задачи мы рассмотрим три случая:

1. Прямой подход: какие минусы?
2. Оптимизированное решение с использованием мемоизации
3. Оптимизированное решение с использованием табуляции

Прямой/грубый подход

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

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

На экране ниже вы можете увидеть стек вызовов функций для вычисления пятого элемента последовательности.

Обратите внимание, что функция fib(1) вызывается пять раз, а fib(2) три раза. Функции с одной сигнатурой, с одинаковыми параметрами запускаются неоднократно и делают одно и то же. При увеличении числа N дерево увеличивается не линейно, а экспоненциально, что приводит к колоссальному дублированию вычислений.

Математический анализ:

Временная сложность: O(2^n),

Пространственная сложность: O(n) -> пропорциональна максимальной глубине рекурсивного дерева, поскольку это максимальное количество элементов, которые могут присутствовать в стеке неявных вызовов функций.

Результат: Этот подход крайне неэффективен. Например, для вычисления 30-го элемента необходимо 1 073 741 824 операции.

Мемоизация (нисходящий подход)

В этом подходе реализация не сильно отличается от предыдущего решения «грубой силы», за исключением распределения памяти. Пусть это будет переменная memo, в которую мы собираем результаты вычислений любой завершенной функции fib() в нашем стеке.

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

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

Давайте снова сосредоточимся на стеке вызовов функций:

• Первой завершенной функцией, которая записывает результат в заметку, является выделенная функция fib(2) . Он возвращает управление выделенному fib(3) .
• Выделенный fib(3) находит свое значение после суммирования результатов вызовов fib(2) и fib(1) , вводит свое решение в заметку и возвращает управление fib(4) .
• Мы подошли к этапу повторного использования предыдущего опыта — когда управление возвращается в fib(4) , вызов fib(2) ожидает в нем своей очереди. fib(2) в свою очередь вместо вызова ( fib(1) + fib(0) ) использует всё готовое решение из заметки и сразу же возвращает его.
• fib(4) вычисляется и возвращает управление fib(5) , которому остается только запустить fib(3) . В последней аналогии fib(3) немедленно возвращает значение из заметки без вычислений.

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

Математический анализ:

Временная сложность: O(n)

Пространственная сложность: O(n)

Результат: существует явная разница в асимптотической сложности. Этот подход свел его к линейности во времени по сравнению с примитивным решением и не увеличил объем памяти.

Табуляция (подход «снизу вверх»)

Как упоминалось выше, этот подход предполагает итеративные вычисления от меньшей к большей подзадаче. В случае Фибоначчи наименьшими «подзадачами» являются первый и второй элементы последовательности, 0 и 1 соответственно.

Мы хорошо знаем, как элементы соотносятся друг с другом, что выражается формулой: fib(n) = fib(n-1) + fib(n-2) . Поскольку мы знаем предыдущие элементы, мы можем легко разработать следующий, следующий за ним и так далее.

Суммируя известные нам значения, мы можем найти следующий элемент. Эту операцию мы реализуем циклически, пока не найдем искомое значение.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

Математический анализ:

Временная сложность: O(n)

Космическая сложность: O(1)

Результат: Этот подход так же эффективен, как и мемоизация, с точки зрения скорости, но он использует постоянный объем памяти.

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

Давайте рассмотрим более сложную задачу : нам нужно найти количество всех структурно уникальных бинарных деревьев, которые можно создать из N узлов.

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет не более двух потомков. Как правило, первый узел называется родительским и имеет двух дочерних узлов — левый дочерний и правый дочерний.

Предположим, что нам нужно найти решение для N = 3. Для трех узлов имеется 5 структурно уникальных деревьев. Мы можем посчитать их в уме, но если N увеличить, вариации значительно возрастут, и визуализировать их в голове будет невозможно.

Эту задачу можно отнести к комбинаторике. Давайте разберемся, какие комбинации могут образовываться и как найти закономерность их образования.

1. Каждое дерево начинается с верхнего узла (вершины дерева). Затем дерево расширяется в глубину.
2. Каждый узел является началом нового дочернего дерева (поддерева), как показано на экране. Левое поддерево окрашено в зеленый цвет, а правое — в красный. У каждого своя вершина.

Давайте рассмотрим пример задачи, где N = 6 на концептуальном уровне. Мы назовем нашу функцию расчета numOfUniqueTrees(n: Int) .

В нашем примере задано 6 узлов, один из которых по упомянутому ранее принципу образует вершину дерева, а другие 5 — остаток.

С этого момента мы взаимодействуем с остальными узлами. Это можно сделать разными способами. Например, используя все пять узлов для формирования левого поддерева или отправив все пять в правое поддерево. Или разделив узлы на две — 2 слева и 3 справа (см. скрин ниже), получим ограниченное количество таких вариантов.

Чтобы добиться результата numOfUniqueTrees(6) нам необходимо рассмотреть все варианты распределения наших узлов. Они показаны в таблице:

В таблице показано 6 различных распределений узлов. Если мы найдем, сколько уникальных деревьев можно создать для каждого распределения, и просуммируем их, мы достигнем конечного результата.

Как узнать количество уникальных деревьев для раздачи?

У нас есть два параметра: Left Nodes и Right Nodes (левый и правый столбец таблицы).

Результат будет равен: numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) .

Почему? Слева у нас будет X уникальных деревьев, и для каждого мы сможем разместить Y уникальных вариаций деревьев справа. Мы умножаем их, чтобы получить результат.

Итак, давайте выясним варианты для первого распределения (5 слева, 0 справа)

numOfUniqueTrees(5) * numOfUniqueTrees(0) , так как справа у нас нет узлов. Результатом будет numOfUniqueTrees(5) — количество уникальных поддеревьев слева при постоянном правом.

Вычисление numOfUniqueTrees(5) .

Теперь у нас есть наименьшая подзадача. Мы будем действовать с ним так же, как и с более крупным. На этом этапе характеристика задач ДП ясна — оптимальная подструктура, рекурсивное поведение.

Один узел (зеленый узел) отправляется в вершину. Остальные (четыре) узла распределяем аналогично предыдущему опыту (4:0), (3:1), (2:2), (1:3), (0:4).

Рассчитаем первое распределение (4:0). По предыдущей аналогии он равен numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) .

Вычисление numOfUniqueTrees(4) . Если мы выделим узел для вершины, у нас останется 3.

Распределения (3:0), (2:1), (1:2), (0:3).

Для 2 узлов существует только два уникальных бинарных дерева, для 1 — одно. Ранее мы уже упоминали, что существует 5 вариантов уникальных бинарных деревьев для трех узлов.

В результате — распределения (3:0), (0:3) равны 5, (2:1), (1:2) — 2. Если просуммировать 5 + 2 + 2 + 5, получим 14. numOfUniqueTrees(4) = 14.

Занесем результат расчета в переменную memo по опыту мемоизации. Всякий раз, когда нам понадобится найти варианты для четырех узлов, мы не будем их рассчитывать заново, а повторно воспользуемся предыдущим опытом.

Вернемся к расчету (5:0), который равен сумме распределений (4:0), (3:1), (2:2), (1:3), (0:4). Мы знаем, что (4:0) = 14. Обратимся к памятке, (3:1) = 5, (2:2) = 4 (2 варианта слева * 2 справа), (1:3) = 5, (0:4) = 14. Если суммировать, получим 42, numOfUniqueTrees(5) = 42.

Вернемся к вычислению numOfUniqueTrees(6) , которое равно сумме распределений.

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 слева * 2 справа), (2:3) = 10, (1:4) = 14, (0: 5) = 42. Если суммировать, получим 132, numOfUniqueTrees(5) = 132 .

Задача решена!

Результат: обратите внимание на перекрывающиеся подзадачи в решении, где N = 6. В простом решении numOfUniqueTrees(3) будет вызываться 18 раз (экран ниже). С увеличением N повторение одних и тех же вычислений будет намного больше.

Подчеркиваю, что количество уникальных деревьев для (5 слева, 0 справа) и (0 слева, 5 справа) будет одинаковым. Только в одном случае они будут слева, а в другом справа. Это также работает для (4 слева, 1 справа) и (1 слева, 4 справа).

Мемоизация как подход динамического программирования позволила нам оптимизировать решение такой сложной задачи.

Выполнение

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

Заключение

В ряде случаев решение задач средствами динамического программирования позволяет сэкономить огромное количество времени и заставить алгоритм работать с максимальной эффективностью.

Спасибо, что дочитали эту статью до конца. Буду рад ответить на ваши вопросы.

Автор : Аят Рахишев