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

Динамическому программированию посвящено много статей и разборов в математическом программировании, потому что объяснить его непосвященным – крайне непросто. Основная проблема объяснения подхода динамического программирования – не в самое его сложности, а в том, что непонятно, зачем методы динамического программирования нужны. А непонятно – потому что все привыкли к линейному программированию, не видят разницы между ДП/рекурсивным алгоритмом/«разделяй и властвуй», слабо представляют себе вычисление сложности и основы математической оптимизации. Ниже мы постараемся дать простые и понятные объяснения всем этим терминам, покажем разницу сложности у разных математических методов и на примерах разберем динамическое планирование/программирование.

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

История

В истории динамического программирования нет ничего интересного – его создали математики, чтобы решить проблему сложности рекурсивных алгоритмов (обо всем этом – ниже). Единственный момент – поскольку динамическое программирование придумали математики, оно в большей мере является математическим методом, и пусть слово «программирование» не вводит вас в заблуждение.

Формулировка и ликбез

Официальная формулировка: теория динамического программирования предполагает решение сложной задачи разбитием ее на более простые задачи. Эта формулировка объясняет все и ничего одновременно – если вы знакомы с олимпиадным программированием, вы можете задать логичный вопрос: а чем динамическое программирование в таком случае отличается от рекурсии, которая тоже разбивает задачу на подзадачи?

Чтобы отметить на этот вопрос, нам сначала нужно разобрать, что в программировании означают нотации сложности. Сложность – это сколько ресурсов уйдет на решение задачи выбранным алгоритмом. Вообще, сложность можно высчитывать по количеству операций и по выделяемому месту, но обычно считают именно количество операций. Сложность записывается как O(n). Под n обычно подразумевается количество входных данных. Например, если сложность алгоритма сортировки – O(n), то массив из 100 элементов будет отсортирован за 100 действий. Если же сложность сортировки – O(n^2), то массив из 100 элементов будет отсортирован за 10 000 действий. Особая нотация O(1) означает, что требуется ровно одно действие. 

Еще одна особенность сложности – считаются только степени сложности. Сложность может считаться как n, как степень n, как логарифм по основанию 2 от n, как факториал n и в других больших множителях/делителях. Например, нужно отсортировать массив на 1 000 переменных:

• O(логарифм от n по основанию 2): примерно 10 действий.
• O(n): 1 000 действий.
• O(n^2): 1 000 000 действий.
• O(n!): полностью приводить не будем, но число имеет 2 568 цифр, последние 249 – нули.

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

Итак, алгоритмы имеют разную сложность. Хороший показатель – линейная сложность (O(n)), желательно по возможности доводить сложность до логарифма по основанию 2, O(n^2) – плохо, O(n^3) – ужасно медленно, O(n!) – ждите результат лет через 200. Если мы начнем рассматривать в этом контексте алгоритмы, разбивающие задачу на подзадачи, то самым эффективным будет «разделяй и властвуй» – алгоритм, который делит некоторое количество данных на 2 части, затем каждую часть снова делит на 2 части – и так, пока не дойдет до атомарного (неделимого) куска данных. В процессе разделения алгоритм делает еще что-то – сортирует, отбрасывает ненужное и так далее. В среднем «разделяй и властвуй» работает за логарифм по основанию 2, но имеет очень узкую сферу применения – нужно, чтобы каждая подзадача (половина, оставшаяся после разделения) решалась ровно так же, как и изначальная задача.

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

Числа Фибоначчи – это числовой ряд, и для того, чтобы вычислить 6-е число, мы вызываем функцию вычисления 4 и 5 числа, чтобы вычислить 4-е число, мы вызываем функцию вычисления 2 и 3 числа, и так далее – пока не упремся в 0 или 1, здесь мы уже ничего не вызываем, а просто возвращаем ноль или единицу. Таким образом, подзадача нахождения числа разбивается на нахождение двух чисел младше, и это продолжается, пока не будет достигнута точка остановки для каждой ветки дерева рекурсии.

Но на картинке выше вы можете заметить одну проблему: рекурсивный метод жрет очень много ресурсов, потому что f0 и f1 вычисляются очень много раз (как и f2, f3 и f4 – только f5 выполняется единожды). Сложность рекурсивного метода вычисления числа Фибоначчи – 2 в степени n, то есть для сотого числа понадобится 1 267 650 600 228 229 401 496 703 205 376 вызовов функции. Так себе, честно говоря. 

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

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

Если мы будем решать задачу на числа Фибоначчи по принципу динамического программирования, код на Python будет выглядеть так:

def fibonacci(n): f = [0, 1] for i in range(2, n+1): f.append(f[i-1] + f[i-2]) return f[n]

Мы заводим массив, в котором хранятся уже вычисленные числа. Сначала в нем лежат 0 и 1 – эти значения числового ряда известны изначально. Потом мы просто запускаем цикл от 2 до n включительно, который в f[2] кладет f[1] + f[0], в f[3] кладет f[2] + f[1] и так далее. Когда цикл закончился – просто возвращаем число под номером n из списка. Алгоритм можно оптимизировать еще лучше:

for i in range(2,n+1): c = a + b a = b b = c

Вместо того, чтобы хранить числа в списке, мы просто запоминаем 2 последних вычисленных, так как они нужны нам для вычисления следующего, а все остальные отбрасываем. Это не единственное оптимальное планирование, по принципу динамического программирования можно придумать еще 3-4 решения, но суть у них у всех одинаковая – сложность составляет O(n), что означает оптимальную сложность = оптимальное решение.

Использование динамического программирования

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

Решение задач и разбор решений

Здесь мы разберем решение 2 задач с помощью динамического программирования. Каждый подраздел будет разбит на 4 части: формулировка задачи; поиск оптимальной последовательности (для применения динамического или рекурсивного подхода нам нужно найти последовательность, которая разбивает задачу на ряд просты подзадач); код решения на Python, разбор решения.

Уродливые числа

Задача: уродливыми числами являются те, которые делятся на 2, 3 или 5. 1 тоже включена в ряд уродливых чисел. Нужно найти n-ное уродливое число.

Последовательность: поскольку уродливые числа делятся на 2, 3 или 5, нам не обязательно перебирать по порядку все числа – можем сразу умножать число на 2/3/5 и добавлять его в список уродливых.

Код:

def getNthUglyNo(n): ugly = [0] * n ugly[0] = 1 i2 = i3 = i5 = 0 next_multiple_of_2 = 2 next_multiple_of_3 = 3 next_multiple_of_5 = 5 for l in range(1, n): ugly[l] = min(next_multiple_of_2, next_multiple_of_3, next_multiple_of_5) if ugly[l] == next_multiple_of_2: i2 += 1 next_multiple_of_2 = ugly[i2] * 2 if ugly[l] == next_multiple_of_3: i3 += 1 next_multiple_of_3 = ugly[i3] * 3 if ugly[l] == next_multiple_of_5: i5 += 1 next_multiple_of_5 = ugly[i5] * 5 return ugly[-1]

Разбор: сначала мы заводим список уродливых чисел и кладем туда 1, заводим 3 переменные для индексов (пока они равны 0), заводим 3 переменные для хранения результата умножения на 2/3/5. Далее запускаем цикл от 1 до n (последовательное добавление уродливых чисел), в цикле сначала ищем минимальное число, делящееся на 2/3/5 (для начала цикла это 2), заносим это число в список. Далее делаем проверку того, какое число оказалось минимальным: если в список попало next_multiple_of_2, то увеличиваем индекс i2 на 1, записываем в next_multiple_of_2 умноженное уродливое число на 2; такие же проверки делаем для 3 и 5. Индексы нужны для того, чтобы всегда выбирать следующее минимальное число. В конце возвращаем последнее уродливое число.

Золотая шахта

Задача: есть золотая шахта – матрица размером m*n. В каждой ячейке матрицы находится 0 или положительное число – количество золота для этой клетки. Шахтер стартует в нулевой колонке, в любом ряду. Двигаться шахтер может только вправо или по диагонали – вправо+вверх, вправо+вниз. Найдите путь, который обеспечит самое большое количество золота.

Последовательность: поскольку шахтер двигается только вправо, мы можем высчитать, сколько золота будет получено на каждом следующем шаге, начиная с конца. Для последнего ряда в любой строке это будет 0; для любой ячейки в предпоследнем ряду это будет большее из трех ячеек справа (справа и выше, справа, справа и ниже) и так далее. Если мы пройдемся таким образом справа налево, то по итогу в ячейках первого ряда у нас будут максимальные суммы золота, если мы будем стартовать с этой ячейки – нужно будет только выбрать самую большую.

Код:

def getMaxGold(gold, m, n): goldTable = [[0 for i in range(n)] for j in range(m)] for col in range(n-1, -1, -1): for row in range(m): if (col == n-1): right = 0 else: right = goldTable[row][col+1] if (row == 0 or col == n-1): right_up = 0 else: right_up = goldTable[row-1][col+1] if (row == m-1 or col == n-1): right_down = 0 else: right_down = goldTable[row+1][col+1] goldTable[row][col] = gold[row][col] + max(right, right_up, right_down) res = goldTable[0][0] for i in range(1, m): res = max(res, goldTable[i][0]) return res

Разбор: получаем в функцию двумерный массив и размерность этого массива. Создаем такой же массив, но забитый нулями. Проходимся двумя циклами по всему пришедшему двумерному массиву, от конца до начала. Тремя if вычисляем right, right_up и right_down – золото, которое мы получим, если перейдем на клетку справа. В клетку, в которой мы сейчас находимся, записываем максимум из этих трех right. Все, когда массив заполнен – используем переменную res для того, чтобы найти в первом ряду максимальное значение. Нашли – возвращаем.

Что еще почитать по теме

• Большой сборник задач на динамическое программирование.
• Более формальное объяснение на Википедии.

FAQ

Как часто возникает необходимость использования динамического программирования?

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

Что выбрать – рекурсию или динамическое программирование?

Везде, где можно, стоит использовать динамическое программирование вместо рекурсии, потому что обычно сложность ДП – O(n).

Подведем итоги 

Тезисно:

• Динамическое программирование – это подход к решению задач, которые можно разбить на повторяющиеся подзадачи.
• Кроме динамического программирования, по такому же принципу задачи решаются через «разделяй и властвуй» и рекурсию.
• Динамическое программирование – выгодная альтернатива рекурсии, потому что у ДП обычно линейная сложность (O(n)).
• Если вы не совсем понимаете, как работает динамическое программирование – не переживайте, это – сложная тема, которая на практике применяется очень редко.