Вы когда-нибудь задумывались, как некоторые алгоритмы могут эффективно решать сложные задачи, в то время как другие кажутся бесконечно медленными? Большое количество оптимизационных задач, которые невозможно решить очевидным методом (перебором, сравнением всех возможных решений между собой) за вменяемое время, обычно решаются способом, известным как динамическое программирование. Суть подхода заключается в разбивании задачи на более мелкие подзадачи и, используя решения этих подзадач, построения решения большей задачи. Другими словами, техника основывается на принципе математической индукции.
Динамическое программирование – это увлекательная область компьютерной науки, которая внесла значительный вклад в оптимизацию вычислений. Динамическое программирование имеет широкий спектр применений: от прогнозирования цен на акции до оптимизации сложных логистических сетей.
Задача про лягушку
Лягушка Пепе изначально сидит на кувшинке под номером 1. Всего имеется N кувшинок в ряд. Пепе хочется оказаться на кувшинке под номером N. На некоторых кувшинках уже сидят другие лягушки – Пепе не хочет лишних проблем, поэтому на эти кувшинки он не будет прыгать. Нужно найти количество различных маршрутов, которыми Пепе может добраться до последней кувшинки.
Bruteforce решение – перебор
Самое очевидное решение для этой задачи – просто перебрать все возможные маршруты, выбрать среди них возможные (то есть где Пепе не наступает на других лягушек) и посчитать количество.
Перебирать все возможные пути в таких задачах можно разными способами, например: рекурсивно (разветвляясь на каждом шагу) или перебирая битовые маски (определить для каждой кувшинки, собираемся мы на нее наступать или нет заранее и дальше выяснять возможен ли такой путь). Рассмотрим рекурсивный способ – в данном случае он кажется проще в реализации:
def count_ways(current_step, last_step, is_free):
if current_step == 1:
return 1
if current_step < 1:
return 0
if not is_free[current_step]:
return 0
ways_if_jump_1 = count_ways(current_step - 1, last_step, is_free)
ways_if_jump_2 = count_ways(current_step - 2, last_step, is_free)
return ways_if_jump_1 + ways_if_jump_2
Для получения ответа нужно вызвать count_ways(N, N, is_free). В аргумент is_free передать массив/словарь, где для каждой кувшинки от 1 до N записано True, если кувшинка свободна и False, если занята.
Насколько вычислительно дорого это решение?
На каждом шагу (для каждого current_step) мы ветвимся в 2 новых рекурсивных вызова, которые в худшем случае так и ветвятся до конца на 2 ветки. В худшем случае (когда нет запретных кувшинок) функция count_ways вызовется 2n раз. Это довольно дорого, так как даже при N = 30 функция вызовется больше миллиарда раз. Самое главное, что асимптотически решение плохое – при увеличении N вычислительная сложность возрастает экспоненциально. То есть, при N = 40 уже потребуется триллион вызовов функции.
Динамическое программирование: bottom up
Классическое «оптимальное» решение описанной задачи – это подход bottom up. Это уже метод динамического программирования. А точнее, все методы в динамическом программировании можно условно разделить на 2 семейства: снизу вверх (bottom up) и сверху вниз (top down). Чаще всего используют bottom up, потому что его реализация обычно оказывается вычислительно более выигрышной.
Решение динамическим программированием снизу вверх – это почти копия того, как применяют принцип математической индукции в школах. Философия следующая: если мы знаем решение задачи для K кувшинок, то мы можем переиспользовать это знание, чтобы быстро решить задачу для K + 1 кувшинки.
Простейший случай в нашей задаче – это когда Пепе стоит на кувшинке под номером 1. До кувшинки 1 Пепе может добраться одним способом – это база индукции. Дальше используем правило: на кувшинку K можно прийти из кувшинки K – 1 или K – 2 – это правило перехода индукции. Или такое же симметричное: из кувшинки K можно прыгнуть на K + 1 или K + 2.
def count_ways(N, is_free):
answer = [None] * (N + 1)
answer[0] = 0 # создаем для удобства техническую нулевую кувшинку чтобы не проверять каждый раз в цикле дальше что кувшинка существует
answer[1] = 1
for i in range(2, N + 1):
if not is_free[i]:
answer[i] = 0
else:
answer[i] = answer[i - 1] + answer[i - 2]
return answer[N]
Или симметрично, считая вперед (с таким подходом стоит быть осторожным, в некоторых задачах он может приводить к неинтуитивным ошибкам, хотя и на первый взгляд кажется проще):
def count_ways(N, is_free):
answer = [None] * (N + 1)
answer[1] = 1
for i in range(1, N + 1):
if i + 1 <= N and is_free[i + 1]:
answer[i + 1] += answer[I]
if i + 2 <= N and is_free[i + 2]:
answer[i + 2] += answer[i]
return answer[N]
Мемоизация – top down
Мемоизация – это другое название для подхода «сверху вниз». То есть, вместо построения решения сначала для K, а потом для K + 1, делаем наоборот. Мы начинаем в N (последняя кувшинка) и пытаемся понять, откуда мы могли сюда прийти – из N – 1 и N – 2. Мы уже видели такое решение в брутфорс-решении, но с мемоизацией будет одна разница – мы будем запоминать решения промежуточных задач. Отсюда и название метода.
Посмотрим на брутфорс решение с мемоизацией.
count_ways_cache = dict(1=1)
def count_ways(current_step, last_step, is_free):
if current_step in count_ways_cache:
return count_ways_cache[current_step]
if current_step < 1:
return 0
if not is_free[current_step]:
return 0
ways_if_jump_1 = count_ways(current_step - 1, last_step, is_free)
ways_if_jump_2 = count_ways(current_step - 2, last_step, is_free)
return ways_if_jump_1 + ways_if_jump_2
Здесь в качестве кеша используем словарь. Это приятный момент метода мемоизации – можно легко кешировать результаты функции, например при строковых аргументах если функция работает над типом str. В обычной bottom-down динамике обычно создают какой-нибудь массив или матрицу заранее и от начала до конца ее заполняют, а тут можно создать словарь и запоминать в каком-угодно порядке без разбора.
Не очень много отличий от самого брутфорса, правда?
Если вы понимаете, как написать брутфорс top-down решение, то проще вставить туда 3 строчки, обеспечивающие мемоизацию, чем писать bottom-up решение. В python даже 3 строчки писать необязательно – есть готовый декоратор functools.lru_cache.
Изменилась ли вычислительная сложность такого решения? Да, значительно. Благодаря запоминанию и переиспользованию результата для каждой кувшинки,мы считаем ответ только один раз. А на все дальнейшие запросы для этой кувшинки очень быстро отвечаем готовым результатом без запуска дальшейшей рекурсии. Это, по сути, делает наше решение линейным по ассимптотике. То есть, с таким решение можно посчитать результат для N = миллиард за секунду.
И почему это лучше?
Одна из проблем bottom-up подхода заключается в том, что сложно понять где bottom, а где up. Иными словами, этот подход предполагает, что:
- Знаем, какие предыдущие состояния нужно решить.
- Предыдущие состояния решены.
Обычно пункт 1 несложно закрыть – для этого в большинстве случаев достаточно правильно понять условие задачи. А вот пункт 2 иногда бывает довольно трудно реализовать. Например, в задаче про шахматного коня:
Есть шахматная доска N x N. Некоторые из клеток заняты другими фигурами – на них вставать конь не может. Нужно определить возможен ли на такой доске для коня путь от клетки [1,1] до клетки [N,N]. Конь ходит по правилам шахмат. Фигуры, занимающие клетки, не двигаются.
В такой задаче довольно легко выяснить формулу перехода: конь в клетку [K,L] может попасть из клеток [K-1,L-2], [K-1, L+2], [K+1,L-2], [K+1,L+2] или [K-2,L-1], [K+2,L-1], [K-2,L+1], [K+2,L+1] – из максимум 8 клеток. То есть, написать брутфорс решение несложно – нужно только учесть граничные случаи типа выхода за границы доски. А если можно написать брутфорс – значит можно легко преобразовать его в мемоизированную динамику!
Чтобы решить честным bottom-up, тут придется придумывать, как сделать обход поля: если идти сверху вниз по строчкам, то правило «предыдущие состояния решены» не выполнено – конь мог прийти снизу в эту клетку, а вниз еще не вычислен.
Короче говоря, мемоизация или top-down динамика убирает необходимость думать про правило 2. Приятным бонусом является то, что top-down подход вычисляет не все возможные состояния, а только нужные для конечного вопроса. При bottom-up же мы обычно не знаем, какие решения предыдущих состояний могут понадобиться, поэтому считаем все возможные.
Однако, у мемоизации есть и отрицательные стороны. Например, bottom-up решения обычно чуть быстрее работают, если правильно реализованы – потому что процессоры умеют их оптимизировать лучше. Также часто мемоизация накладывается сверх рекурсивного решения – а рекурсия всегда дороже цикла. Тут можно сказать, что при желании рекурсию всегда можно убрать и заменить явным стеком.
В целом, метод мемоизации мне нравится больше классического bottom-up и он часто позволяет прикладывать меньше умственных усилий и достигать результата проще. Та же концепция используется и за пределами динамического программирования и вообще решения алгоритмических задач – например, ленивая инициализация.
Как часто вы применяете мемоизацию при решении задач?