О динамическом программировании на пальцах

Привет, хабр! Сегодня мы поговорим о динамическом программировании.

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

И часто в заданиях, олимпиадах, или даже просто в жизни, попадаются задания на динамическое программирование.

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

(С) Доктор Аргентум, 2022 год нашей эры

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

Динамическое программирование — это особый подход к решению задач. Не существует какого-то единого определения динамическому программированию, но все-таки попробуем её сформировать. Идея заключается в том, что оптимальное решение зачастую можно найти, рассмотрев все возможные пути решения задачи, и выбрать среди них лучшее.

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

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

В самых простых случаях эта таблица будет состоять только из одной строки — аналогично обычному массиву. Эти случаи будут называться одномерным динамическим программированием, и потреблять O(n) памяти. Например, алгоритм эффективного вычисления чисел Фибоначчи использует обычный массив для запоминания вычисленных промежуточных результатов. Классический рекурсивный алгоритм делает очень много бессмысленный работы — он по миллионному разу рассчитывает то, что уже было рассчитано в соседних ветках рекурсии.

В самых распространённых случаях эта таблица будет выглядеть привычно и состоять из строчек и столбиков. Обычная таблица, похожая на таблицы из Excel. Это называется двумерным динамическим программированием, которое при n строках и n столбцах таблицы потребляет O(n*n) = O(n^2) памяти. Например, квадратная таблица из 10 строк и 10 столбцов будет содержать 100 ячеек. Чуть ниже будет подробно разобрана именно такая задача.

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

Что нужно, чтобы решить задачу динамически, помимо ее исходных данных? Всего три вещи:

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

• Несколько простых правил по заполнению пустых ячеек таблицы, основанных на значениях в уже заполненных ячейках. Универсального рецепта тут нет и к каждой задаче требуется свой подход

• Правило выбора финального решения после заполнения таблицы

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

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

Представим хакера, который пытается взломать какой-то пароль перебором всех комбинаций символов. Если пароль допускает 10 цифр, 26 маленьких букв, 26 больших букв и 32 специальных символа (например, значок доллара), то для каждого символа в пароле есть 94 кандидата. Значит, чтобы взломать перебором пароль, состоящий из одного символа, потребуется 94 проверки. Если в пароле два символа — 94 кандидата на первую позицию, 94 кандидата на вторую позицию — то придется перебрать аж 94*94 = 8836 возможных пар. Для пароля из десяти символов потребуется уже перебор 94^10 комбинаций.

Если обобщить, то для взлома пароля с произвольной длиной N требуется O(94^N) операций. Такие затраты часто называют «экспоненциальными»: появление каждой новой позиции влечёт за собой увеличение количества операций в 94 раза. Взлом пароля может показаться чем-то экзотическим, но задачи, требующие полного перебора всех вариантов — совсем не экзотика, скорее угрюмая реальность.

Экспоненциальное время — это долго. Даже O(2^N) — это просто непозволительно долго. Настолько долго, что никому и в голову не придет запустить подобный алгоритм даже на простых данных — ведь на решение такой задачи с сотней элементов потребуются тысячи, миллионы или миллиарды лет вычислений. А в реальной жизни нужно решать задачи с намного большим количеством элементов. Как же быть?

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

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

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

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

1. Описать структуру оптимального решения.

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

3. Вычислить значение оптимального решения с помощью метода восходящего анализа.

4. Составить оптимальное решение на основе полученной информации.

Динамика на примере чисел Фибоначчи

Один из легких примеров для демонстрации силы динамического программирования - известные числа Фибоначчи.

Последовательность Фибоначчи - это список чисел, который начинается с двух единиц, а каждый следующий элемент, то есть число, равно сумме двух предыдущих. Например:

Формула для вычисления числа Фибоначчи представлена ниже:

Давайте создадим простейший алгоритм построения последовательности Фибоначчи на Python:

import timeit # замер времени


def fib(n):
    return 1 if n == 0 or n == 1 else fib(n - 1) + fib(n - 2)


# вывод времени работы 
print(timeit.timeit('fib(20)', number=100, globals=globals()))

>>> 2.2218473450011516

Отвратительно получилось. Алгоритм очень медленный. Так давайте улучшим его!

Фундаментальная проблема заключается в многократном выполнении одинаковых вычислений. Например, F3 рассчитывается дважды, а F2 – трижды, хотя результат каждый раз получается одинаковый. Даже если не углубляться в анализ времени выполнения, очевидно, что для этого алгоритма оно будет расти по экспоненте.

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

Не каждая задача пригодна для DP. Если подпроблемы не перекрываются, следует использовать алгоритм "разделяй и властвуй", как при сортировке массива слиянием.

Но как же улучшить наш алгоритм?

Ответ простой - мемоизация, запоминание, или же кеширование.

Один из способов избежать постоянного пересчитывания одних и тех же данных – кешировать результаты вычислений. Технически это реализуется так:

• Если кеш содержит результат для полученных входных данных, использовать значение из кеша.

• В противном случае, вычислить результат и сохранить его в кеше, поставив в соответствие с входными данными.

import timeit


def fib(n, cache=None):
    if n == 0 or n == 1: return 1

    if cache is None: cache = {}
    if n in cache: return cache[n]

    result = fib(n - 1, cache) + fib(n - 2, cache)
    cache[n] = result
    
    return result


print(timeit.timeit('fib(20)', number=100, globals=globals()))

>>> 0.00414187600108562

Невероятно! Скорость выполнения повысилась в 2 раза!

Давайте улучшим и сделаем полный ее рефакторинг, но сам смысл оставим тот же - мемоизация, но применим также декораторы Python:

import timeit
from inspect import signature
 

class memoize(dict):
    def __init__(self, func):
        self.func = func
        self.signature = signature(func)
 
    def __missing__(self, key):
        (arg, kwarg) = key
        self[key] = val = self.func(*arg,  
                          **dict(kwarg))
        return val
 
    def __call__(self, *arg, **kwarg):
        key = self.signature.bind(*arg, 
                                  **kwarg)
        return self[key.args, 
                    frozenset(key.kwargs.items())]
 
 
@memoize
def Fibonacci(n): 
 
    if n<0: 
        print("Неверный ввод") 
 
    elif n == 0: 
        return 0
    elif n == 1: 
        return 1
 
    else: 
        return Fibonacci(n-1)+Fibonacci(n-2)
 
if __name__ == "__main__":
    print(Fibonacci(20)) 
    print(timeit.timeit('Fibonacci(20)', number=100, globals=globals()))

Зависимость от n практически линейна!

Но что насчет пространственной сложности? Для вычисления F_n нужно вычислить F_n-1 и F_n-2, и так далее до F₀. Следовательно, придется кэшировать O(n) результатов. Значит, потребуется O(n) памяти.

Можно ли сделать лучше? В этом случае можно!

Динамическое программирование снизу вверх

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

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

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

• есть узлы (задачи) и ребра (зависимости между ними);

• ребра имеют направление, одна подзадача зависит от другой;

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

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

Для ряда Фибоначчи этот порядок соответствует увеличению входных данных. То есть сначала мы должны вычислить F₀, затем F₁, F₂ и так далее до F_n.

Есть еще одна важная вещь, которую мы можем вывести из DAG. Каждая подзадача зависит только от двух других. Если вы вычисляете F_m, то вам нужны только результаты F_m-1 и F_m-2, и совершенно не нужно F_m-10. То есть вы можете спокойно выбрасывать значения, которые не участвуют в текущем вычислении.

Формализация алгоритма

1. Заведем две локальные переменные, которые будут представлять последние два числа Фибоначчи, с которыми мы работаем.

2. Поместим в них F₀(=1) и F₁(=1)

3. Изменяя i от 2 до n вычислим F_i. Каждая операция зависит только от F_i-1 и F_i-2, которые хранятся в локальных переменных. Получая результат, мы выбрасываем F_i-2, заменяем его на F_i-1, а в оставшуюся переменную записываем F_i.

В Python это выглядит так:

import timeit


def fib(n):
    a = 1  # f(i - 2)
    b = 1  # f(i - 1)
    for i in range(2, n + 1): 
        a, b = b, a + b
    return b
    

print(timeit.timeit('fib(20)', number=100, globals=globals()))

>>> 0.0005998830019962043

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

Этот подход называется "снизу-вверх" (bottom-up approach), так как основывается на решении небольших подзадач с целью построения более крупных.

Задача о рюкзаке

Другой популярный пример применения динамического программирования - задача о рюкзаке (knapsack problem). В этой задаче у нас есть набор предметов с определенной стоимостью и весом, а также рюкзак с ограниченной вместимостью. Нужно выбрать такой набор предметов, чтобы их суммарная стоимость была максимальной, а их суммарный вес не превышал вместимость рюкзака.

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

1. Создаем матрицу dp размером (n + 1) x (W + 1), где n - количество предметов, W - вместимость рюкзака.

2. Инициализируем первую строку и первый столбец матрицы dp нулями.

3. Проходимся по каждому предмету i от 1 до n.

4. Проходимся по каждой вместимости w от 1 до W.

5. Если вес предмета i меньше или равен w, то dp[i][w] равно максимуму из значения dp[i-1][w] и стоимости предмета i плюс значения dp[i-1][w-вес предмета i].

6. Иначе, dp[i][w] равно значению dp[i-1][w].

7. Возвращаем значение в правом нижнем углу матрицы dp как результат.

import timeit


def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]


weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(timeit.timeit('knapsack(weights, values, capacity)', number=100, globals=globals()))

>>> 0.007788784998410847

Пример использования:

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
result = knapsack(weights, values, capacity)
print(result) # Вывод: 9

В данном примере мы выбираем предметы с весами 3, 4 и 5 и получаем максимальную суммарную стоимость равную 9.

Интересные примеры задач

Внешние ссылки на примеры задач, которые могут заинтересовать вас

• Задача о расстановке знаков в выражении

• Задача о порядке перемножения матриц

• Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами

• Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза

• Задача о наибольшей общей подпоследовательности

• Задача о редакционном расстоянии, алгоритм Вагнера-Фишера

• Задача о расстоянии Дамерау-Левенштейна

Вот такая небольшая статья у нас получилось. Надеюсь вам понравилось, ставьте плюсы, и комментируйте! С вами был доктор Аргентум!