Что такое динамическое программирование — объясняют эксперты

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

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

Денис Хоружий

технический директор iD EAST

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

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

Важная особенность чтобы этот процесс не зациклился нужно чтобы на каком-то этапе задача сводилась к примитивному случаю, ответ на который известен сразу. Пример — вычисление факториала числа. Такую задачу можно решить и с помощью простого алгоритма n!=1·2·3·…·n, в этом случае можно сразу получить значение (например 4! = 1·2·3·4 = 24, а 5! = 1·2·3·4·5 = 120). Но эту же задачу можно решить и рекурсивно, ведь 5! = 5·4!, а 4! = 4·3! и так далее. Значит можно написать простую функцию расчета факториала n!, которая будет умножать число на результат вызова самой себя для более простого случая (n-1)!. И только в примитивном случае 1! функция вызывать саму себя не будет, а сразу вернёт 1, это важный момент, чтобы не возникло зацикливания.

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

Взять, к примеру, задачу поиска кратчайшего маршрута по городу из точки А в точку Б. На практике такие задачи решаются с использованием теории графов, когда каждой улице в городе ставится в соответствие ребро графа, а каждой возможной точке пребывания — узел графа. Каждому ребру приписывается некоторая условная «стоимость», соответствующая, например времени прохождения или даже непосредственно денежная стоимости проезда по соответствующей «улице». Эта стоимость в реальности может даже меняться с течением времени, например из-за пробок. Тогда необходима функция, находящая кратчайший маршрут — такую последовательность узлов, пройдя через которые мы получим минимальную «стоимость» прохождения всех соединяющих их рёбер.

И вот для таких задач методы динамического программирования становится практически единственными рабочими вариантами решения. Методы рекурсии здесь уже не подойдут: можно, конечно, решить эту задачу и таким образом: написать функцию, возвращающую стоимость ухода из точки А по каждой из возможных «улиц», каждая из этих функций в свою очередь добавит к ней стоимость участка до следующего «перекрёстка», вызвав саму себя еще раз, и повторит это многократно, пока в результате не «дойдёт» до точки Б. По итогу, среди всех цепочек ответов можно будет выбрать ту, стоимость которой минимальна и получить ответ на задачу. Но на практике сделать такое возможно только для очень простых графов с десятками узлов, например для карты метро. А вот уже в масштабах карты улиц города подобные алгоритмы становятся нереалистичными.

Дмитрий Романовский

тимлид в ADCI Solutions

Если вкратце, то динамическое программирование — это способ решить задачу, разбив её на мелкие задачи и скомбинировав их решения.

Обычно динамическое программирование применяют в задачах, связанных с оптимизацией, например, когда нужно найти кратчайший маршрут для перемещения из города A в город B. Либо это могут быть задачи, где нужно просчитать все возможные комбинации переходов или расположения элементов. Классический пример, в котором используется этот метод — последовательность чисел Фибоначчи.

F(n) = F(n-1) + F(n-2);
F(0)=0;
F(1)=F(2)=1;

Как видно, для решения задачек с последовательностями, нужно определить следующие условия: рекуррентная зависимость элементов последовательности друг от друга, начальное состояние. Они не всегда могут быть заданы в условии напрямую, как это было в задаче выше. Например, в видео «Динамическое программирование: траектории кузнечика» разбирают задание с количеством переходов из точки A в B.

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

• массивы,
• векторы,
• отрезки внутри массивов,
• деревья,
• подмножества,
• динамика по профилю
• и т. д.

Поиск оптимального состояния динамики, переходов и порядка пересчёта (прямой или обратный) и включает в себя метод динамического программирования.

Узнать подробности о применениях этого метода и способах его оптимизации можно почти во всех в книжках по алгоритмам, например, в книге «Алгоритмы. Построение и анализ».

Олег Лекшин

начальник отдела разработки прикладного ПО в компании ИВК

В теории вычислительных систем под термином «динамическое программирование» понимается способ решения сложных задач путём разбиения их на более простые подзадачи. Динамическое программирование применимо не ко всем задачам, а лишь к тем, которые обладают «оптимальной структурой». Оптимальная структура означает, что задача может быть разбита на несколько аналогичных задач меньшего размера, при этом для решения конечной задачи могут быть использованы результаты решения меньших задач. Примеры задач с оптимальной структурой — вычисление факториала числа, построение ряда чисел Фибоначчи, вычисление расстояния Левенштейна (красивое название, скрывающееся внутри всем известной задачи diff, вычисляющей разницу между двумя текстовыми файлами). Программист, не знакомый с теорией вычислительных систем, может подумать, здесь кроется какая-то сложная математика, но на самом деле речь идёт о всем хорошо знакомом подходе — рекурсии. Все знают, как вычислить факториал числа: нужно умножить это число на факториал числа, меньшего на единицу: F(n) = n*F(n-1) (для краткости опущена проверка n >= 1) — просто и изящно.

Так вот, динамическое программирование — это рекурсия с сохранением результатов вычислений. Представим, что нам постоянно нужно вычислять факториал разных чисел. Каждый раз, когда нам нужно вычислить факториал, например, числа 5, нам необходимо произвести 4 умножения — 5*4*3*2*1. А что, если сохранить промежуточные результаты? Допустим, мы когда-то раньше вычислили 4! = 24. Значит, нам нужно проделать только одно умножение — 5*24. А в следующий раз, когда нас спросят 5!, мы вообще можем вернуть результат сразу же. Понятно, что при таком подходе растёт скорость вычислений, но и возрастает потребление памяти. Что важнее — скорость или память — вечный вопрос. Принимать решение нужно исходя из конкретных условий.

Михаил Адигеев

руководитель отдела программных разработок и поддержки компании «ГЭНДАЛЬФ»

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

Суть метода в следующем: имеющуюся задачу рекурсивно разбиваем на более маленькие подзадачи, их — на ещё меньшие и так далее. Но решаем задачи в обратном порядке: сначала маленькие (запоминаем их решение), потом переходим к задачам побольше (строим их решение на основе сохранённых решений маленьких задач) и так далее, пока не решим исходную большую задачу.

Преимущества метода:

• за счёт запоминания решения промежуточных подзадач мы каждую такую подзадачу решаем только один раз, т.е. экономим время;
• избавляемся от рекурсии (заменяем её на вложенные циклы).

Недостаток: обычно требуется много памяти для хранения промежуточных результатов.

Александр Бармин

Lead Software Engineer в EPAM

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

Некоторые подобные задачи можно решить путем разбиения исходной задачи на подзадачи меньшего размера и сложности, решив которые и объединив результаты, можно получить решение исходной задачи. Такой подход называется динамическим программированием и был предложен Ричардом Беллманом в 1940-х годах.

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

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

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

С помощью чисел Фибоначчи описываются многие явления, однако, давайте посмотрим на более практический пример ― задачу коммивояжера или, на современный лад, курьера ― курьер должен посетить N адресов, побывав на каждом из адресов ровно по одному разу и завершить свой маршрут в исходной точке. Задача заключается в нахождении маршрута минимальной длинны.

Данную задачу можно решить методом полного перебора ― сгенерировать все возможные маршруты (всего их N!) для N адресов, а затем выбрать маршрут минимальной длины. Сложность данного алгоритма O(N! * N) и время вычисления очень быстро растет при росте количества адресов ― если для трех адресов нужно рассмотреть шесть вариантов, то для 10 уже около четырех миллионов!

Использование подходов динамического программирования может не дать наилучшего решения, но, тем не менее, оно будет достаточно хорошим и за приемлемое время. Суть подхода к решению данной задачи заключается в поиске ближайшего адреса на каждом шаге ― из исходной точки, затем следующего ближайшего пункта назначения из первого адреса и так далее. Полученное решение не будет идеальным, но потребует гораздо меньше времени ― O(N^2 * 2^N), что для тех же 10 адресов 1124 вычислений.

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

Глеб Лысов

старший разработчик систем автоматизации и поддержки сервисов мониторинга и реагирования на киберугрозы в BI.ZONE

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

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

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

Данный метод применяют, чтобы ускорить и упростить решение задачи.

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

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

Напоминаем, что вы можете задать свой вопрос экспертам, а мы соберём на него ответы, если он окажется интересным. Вопросы, которые уже задавались, можно найти в списке выпусков рубрики. Если вы хотите присоединиться к числу экспертов и прислать ответ от вашей компании или лично от вас, то пишите на experts@tproger.ru, мы расскажем, как это сделать.