Девять фундаментальных алгоритмов, чтобы научиться пользоваться динамическим программированием
Динамическое программирование - важная техника соревновательного программирования. Он заключается в обмене памяти на время, чтобы избежать повторения вычислений. Это может привести к значительному повышению производительности, иногда превращая алгоритм с экспоненциальным временем в линейный.
Это первая часть серии статей. Первая иллюстрирует основы динамического программирования с помощью трех основных проблем, вторая исследует еще три продвинутых алгоритма, а в трех отдельных статьях рассматриваются более сложные проблемы. Вот список всех алгоритмов, которые мы рассмотрим:
- Вычисление n -го числа трибоначчи (часть 1)
- Калькулятор эффективных биномиальных коэффициентов (часть 1)
- Подсчет путей в сетке (часть 1)
- Проблема резки стержня (часть 2)
- Нахождение самой длинной возрастающей подпоследовательности (часть 2)
- Расчет сдачи (часть 2)
- Задача о рюкзаке (часть 3)
- Нахождение самой длинной общей подпоследовательности (часть 4)
- Проблема выравнивания последовательностей (часть 5)
Я попытался сделать его максимально независимым от языка, и все алгоритмы, которые мы будем изучать, проиллюстрированы реализацией в псевдокоде.
Давайте начнем!
Что такое динамическое программирование?
В отличие от жадных алгоритмов, которые производят глобальное решение, принимая локально оптимальные решения по подзадачам (что не обязательно дает оптимальный результат), динамическое программирование находит оптимальное решение, рассматривая все возможные возможности, пытаясь минимизировать количество вычислений. Это достигается с помощью кеша, в котором хранятся результаты прошлых вычислений.
Все проблемы оптимизации нельзя решить с помощью динамического программирования: они должны иметь оптимальную подструктуру. Это означает, что решение проблемы можно вывести из решения подзадач. Примером задачи, не имеющей оптимальной подструктуры, является определение длины самого длинного простого пути на графе, то есть самого длинного пути, который не посещает одну и ту же вершину несколько раз.
Следовательно, динамическое программирование применяется к задачам, которые имеют оптимальную подструктуру и где начальные проблемы разбиты на перекрывающиеся подзадачи (в противном случае достаточно простого подхода «разделяй и властвуй», поскольку не было бы необходимо сохранить прошлые вычисления). Алгоритмы динамического программирования всегда находят оптимальное решение.
В динамическом программировании используются два основных метода, которые мы рассмотрим в этой статье: табуляция и мемоизация.
Табулирование и запоминание: введение и примеры
Табулирование или восходящий подход
Как следует из названия, алгоритм, использующий восходящий подход, начинает с выполнения базовых вычислений, а затем наращивает кэш до целевого значения. Например, предположим, что мы хотим вычислить n -й член последовательности трибоначчи для некоторого натурального числа n. Последовательность трибоначчи определяется:
Trib (0) = 0; Trib (1) = 1; Trib (2) = 1
Trib (n + 3) = Trib (n) + Trib (n + 1) + Trib (n + 2) для любого натурального числа n.
Вот наивное решение, которое напрямую реализует определение без оптимизаций:
Следующее дерево повторения иллюстрирует выполнение вызова tribonacci 6.
Мы видим, что большинство значений вычисляются несколько раз, что делает наш код довольно медленным по сравнению с количеством полезных вычислений. Фактически, функция tribonacci имеет экспоненциальную сложность: сложность выполнения определяется как T (N) = 3T (N - 1) + Θ (1), поэтому общая терм T (N) = Θ (3 ^ N).
Здесь на помощь приходит табуляция. Вот новая версия нашего калькулятора Трибоначчи, который использует табуляцию:
Вместо рекурсивного вычисления Trib (N -1), Trib (N -2) и Trib (N -3) для вычисления T ( N), мы просто извлекаем их за постоянное время, используя массив кеша. Следовательно, достаточно одного рекурсивного вызова. Поскольку нерекурсивные накладные расходы занимают постоянное время, tabulationTribonacci выполняется за Θ (N) времени и занимает Θ (N) пространства.
Воспоминание, или подход сверху вниз
Запоминание и табуляция очень похожи, поскольку они оба используют одну и ту же идею запоминания вычислений, чтобы избежать их повторного выполнения. Разница заключается в порядке вычисления значений. Алгоритм, использующий мемоизацию для вычисления N-го члена последовательности S, начинается с заполнения кэша от S (N) до S (1).
Примером, где этот подход полезен, является вычисление биномиального коэффициента. Определим его индуктивно формулой Bin (N, K) = Bin (N - 1, K - 1) + Bin (N - 1, K). Существует два базовых случая: для всех натуральных чисел u, Bin (u, 0) = 1 и Bin (u, u ) = 1.
Вот немедленная транскрипция приведенного выше определения:
Цикл выполняется T (n, k) = 2Bin (n, k) - 1 раз. Как и раньше, многие вычисления выполняются несколько раз, и их сохранение существенно повысит эффективность функции.
Мы могли бы использовать восходящую технику и создать двумерный массив (n * k) для хранения биномиальных коэффициентов всех пар чисел. Обратной стороной этого подхода является то, что он потребует решения большего количества подзадач, чем необходимо: мы будем вычислять Bin (a, b) для a ≤ n и b ≤ k. Решение - начать вычисление Bin (n , k) и вернуться к базовому случаю. Этот подход реализован ниже.
Дать точную оценку сложности этого алгоритма было бы довольно сложно, но несомненно то, что количество вычислений не может асимптотически превышать min (Bin (n, k) , (n + 1, k + 1)), поскольку он не может быть хуже, чем наивный подход, а количество вычисляемых значений ограничено размером кеша . Например, для вычисления Bin (12, 5) требуется 71 шаг при использовании подхода динамического программирования, в отличие от 1583 шага при использовании наивного подхода.
Мы узнаем о другой задаче, в которой нисходящий подход предпочтительнее восходящего в третьей части, при решении задачи о ранце.
Теперь, когда мы увидели основные методы, используемые для создания алгоритма динамического программирования, мы перейдем к некоторым конкретным задачам, которые мы можем решить с помощью динамического программирования.
Подсчет путей в сетке
Начнем с простой, но интересной задачи.
Постановка задачи
Пусть N будет положительным целым числом. Мы рассматриваем сетку размером N × N. Каждый квадрат сетки представлен кортежем (u, v), соответствующим его координатам, где u - горизонтальный компонент, а v - вертикальный компонент. Верхний левый угол находится в координатах (0, 0), а нижний правый угол - в (N - 1, N - 1). Мы можем перемещаться по сетке, по одному квадрату за раз, вниз или вправо: если x (1),…, x (n) - путь, то для каждого индекса k ≤ n - 1, если x (k) = (u, v), то x (k + 1) равно (u + 1, v) или (u, v + 1).
Наша цель - вычислить количество различных путей от верхнего левого угла до нижнего правого угла.
Почему мы должны подойти к этой проблеме, используя динамическое программирование?
Прежде всего, эту проблему можно решить рекурсивно. Мы знаем, что есть только один способ добраться до верхнего левого угла (0, 0), поскольку это наша отправная точка: мы нашли базовый вариант. Затем есть два способа добраться до квадрата (u, v) ≠ (0, 0): либо из (u - 1, v) или из (u, v - 1) (затем нам нужно будет рассмотреть патологические случаи, когда u = 0 или v = 0). Следовательно, количество путей к (u, v) является суммой количества путей к (u - 1, v) и количество путей к (u, v - 1).
Наивным решением будет подход сверху вниз, при котором мы начнем с вычисления количества способов добраться до (N - 1, N - 1) путем вычисления количества способы добраться до (N - 1, N - 2) и количество способов добраться до (N - 2, N - 1). Но оба (N - 1, N - 2) и (N - 2, N - 1) являются доступны через (N - 2, N - 2), что, следовательно, будет вычислено дважды: подзадачи перекрываются. Следовательно, этот наивный подход потребует неполиномиального времени, даже если у нас есть только N × N различных значений для вычисления.
Написание решения
Мы воспользуемся рекуррентным соотношением, которое мы нашли ранее, и мы сможем реализовать решение этой проблемы с помощью динамического программирования. В приведенном ниже примере используется двумерный массив для хранения количества различных путей к каждому квадрату сетки.
Этот алгоритм работает за квадратичное время ((N ²) относительно длины сторон сетки). Он идет сверху вниз и слева направо, поэтому не пытается вычислить количество путей к квадрату (u, v ) перед вычислением количества путей к (u - 1, v) и к (u, v - 1) по возможности. Это важный момент, на который следует обратить внимание: при реализации табуляции вам необходимо убедиться, что значения вычисляются в правильном порядке, то есть вы не пытаетесь основывать вычисления на результате, который вы еще не вычислили.
Патологические случаи обрабатываются подпрограммой в строках 13 и 16. Когда один из двух компонентов (скажем, u) координат равен нулю, мы устанавливаем количество путей, исходящих из (u - 1, v) до 0, поскольку нет никаких способов приземлиться в квадрат за пределами сетки.
Строки 23 и 24 управляют рекурсивными вызовами: если текущий квадрат является последним в своем столбце, то есть в последней строке (lastRow истинно), мы переходим к следующему столбцу, начиная со строки 0. В противном случае мы остаемся в том же столбце. и увеличиваем индекс строки на единицу.
При n = 7 получаем следующий кеш:
Это показывает, что существует 924 различных пути от (0, 0) до (7, 7).
Сделай сам
Я рекомендую вам реализовать алгоритм, который мы дали, на реальном языке программирования. Чтобы помочь вам проверить правильность вашей реализации, я создал репозиторий, который содержит тестовые примеры для некоторых проблем. Ссылка здесь:
Файл paths-in-a-grid.txt имеет следующий формат:
n f n <blank line>
Где n - размер сетки (сетка n * n), а f n - количество путей к нижнему правому углу.
Файлы maximum-path-in-a-grid-positive.txt и maximum-path-in-a-grid-pos-neg.txt содержат тесты для первого упражнения ниже. Они имеют следующий формат:
n l11 l12 ... l1n . . . ln1 ln2 ... lnn f n <blank line>
n - размер сетки, n следующие строки соответствуют каждой строке сетки (с n целыми числами, разделенными пробелами), а f n - решение. Целые числа находятся в диапазоне от 1 до 45 включительно в первом файле и от -45 до 45 во втором файле.
Упражнения
Вот варианты и возможные улучшения рассмотренных нами алгоритмов:
- Рассмотрим квадратную сетку, заполненную положительными числами. Мы определяем стоимость пути x (1)… x (k) как сумму чисел, хранящихся в каждом квадрате пути . Используйте подход, аналогичный тому, который мы использовали для подсчета путей в сетке, чтобы вычислить максимальную стоимость пути, идущего от верхнего левого угла к нижнему правому углу. Улучшите свое решение, чтобы оно работало с произвольными числами (положительными, отрицательными или нулевыми).
- Можете ли вы улучшить решение указанной выше проблемы, чтобы явно вычислить путь с максимальной стоимостью? Это не должно ухудшать асимптотические границы для сложности времени выполнения и сложности пространства.
Совет: поддерживайте дополнительный массив, который отслеживает, достиг ли максимальный путь к каждому квадрату сетки квадрата сверху или слева. Это позволит вам вернуться от последнего квадрата к первому и построить оптимальный путь. - Мы определяем манхэттенское расстояние между (u, v) и (w, x) как | u - w | + | v - x |. Предположим, вы не можете перейти к квадрату (u, v), если его манхэттенское расстояние до нижнего левого угла (в координатах (0, N )) меньше или равно N - 2 (где сетка имеет размер N × N). Сколько путей от левого верхнего угла к правому нижнему? Сколько элементов массива кэша нам нужно вычислить, чтобы ответить на вопрос?
Вы можете прочитать вторую часть здесь:
Я сгенерировал изображения псевдокода, используя библиотеку с открытым исходным кодом, которую я написал на Python. Здесь вы можете найти код: https://github.com/zak-al/Psi
