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

Занятие 1. Введение в динамическое программирование

Введение в динамическое программирование (ДП)

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

Позднее формулировка понятия была доработана и усовершенствованна до современного вида самим же Беллманом.

Слово «программирование» в контексте «динамическое программирование» на самом деле к классическому пониманию программирования (написанию кода на языке программирования) практически никакого отношения не имеет. Слово «Программирование» имеет такой же смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».

Поэтому программы будут использоваться в качестве оптимальной последовательности действий для получения решения задачи.

В общем же для начала, неформальное определение понятия динамического программирования может звучать так:

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

Задачи комбинаторики, как правило, отвечают на вопрос, сколько существует объектов, обладающих теми или иными свойствами, или сколько существует комбинаторных объектов, обладающих заданными свойствами.

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

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

Рис. 1.1. Неформальное объяснение свойства оптимальности у подзадач

Более подробно неформальное объяснение рассматривается ниже.

Примеры, решаемых при помощи динамического программирования задач

Сначала рассмотрим задачи оптимизации (задачи 1-5):

Целевой функцией здесь является расстояние от А до Б. Т.е. наша цель — минимизировать расстояние.

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

Целевая функция: минимизация расходов (либо на издержки на поддержку старого автомобиля, либо на покупку нового).

Переменная выбора: каждый год принимать решение продать машину или оставить.

Целевая функция: максимизация средних доходов, т.к. на бирже доход получается вероятностным путем, т.е. это статистический процесс, вероятностный.

Переменная выбора: то, какой портфель вложений будет: сколько акций и какой фирмы нам необходимо купить.

Целевая функция: максимизация прибыли.

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

Целевая функция: максимизация вероятности выигрыша или максимизация среднего выигрыша и т.д.

Переменная выбора здесь зависит от конкретной игры.

Задачи 1 — 5 — это примеры задач оптимизации.

Комбинаторика:

Это краткое описание задач для динамического программирования, которые подробно будут рассмотрены позднее.

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

Неформальное объяснение оптимальности подзадач ДП.

Рассмотрим неформальную идею ДП.

Итак, возьмем пример с заводом, изготавливающим мебель.

Для достижения цели максимизации прибыли необходимо решить множество подзадач:

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

Поэтому ДП предлагает следующее:

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

Формальная идея ДП

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

function fact (a: integer): integer; begin if (a

Кроме того, может возникнуть такой вопрос: для того чтобы найти, например, минимум или максимум, почему бы нам не найти производную? или не использовать множества Ла-Гранжа, или другие методы аппарата математического анализа? Зачем нужно ДП, если есть большой арсенал средств?

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

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

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

Простой пример решения задач при помощи ДП

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

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

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

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

Простой пример, где пока неоправданно используется ДП (искусственно), демонстрирует принцип идей ДП.

Рассмотрим еще один пример.

Решение:

Рассмотрим самые простые варианты (подзадачи):

f(a3) = 3 (1 — перешагнуть первую ступеньку, 2 — шагнуть на первую и перешагнуть вторую, 3 — прошагать все 3 ступеньки).

Рассмотрим пример из i ступенек

Как мы можем попасть на i ступеньку:

Например, как попасть на 4-ю ступеньку:

Т.о., общее количество способов попасть на i ступеньку:
f(a_i) = f(a_i-1) + f(a_i-2)

Определим начальные значения, с которых следует начинать решать задачу.
Если начинать с 1, то формула соответствует нахождению последовательности чисел Фибоначчи.

Мы видим, что задача по сути комбинаторная (т.е. количество способов сделать что-либо) свелась к вычислению некоторой рекуррентной последовательности.

Дополните код:

Источник

Идеи динамического программирования: одномерные задачи, часть 1

Авторизуйтесь

Идеи динамического программирования: одномерные задачи, часть 1

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

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

Числа трибоначчи

Числа трибоначчи — это числовой ряд, начинающийся с трёх чисел 0, 0, 1, где каждое последующее число вычисляется как сумма трёх чисел перед ним:

Рассмотрим следующую задачу: дан массив чисел с порядковыми номерами чисел трибоначчи, например: [73, 10, 4, 15, 20, 7], числа в массиве не превышают 100, требуется вернуть массив, содержащий числа трибоначчи под указанными номерами: [73-е число трибоначчи, 10-е число трибоначчи, и так далее].

Если вы какое-то время работаете с языками программирования, то наверняка решали задачи нахождения факториала или степени числа через рекурсию. Попробуем применить такую же идею здесь:

Запускаем функцию с вычислением времени:

41-е число вычисляется 135 секунд. Кажется, что быстрее вручную посчитать числа, подставить в массив все 100 значений (ограничение задачи) и просто вернуть число на нужной позиции. В чём же проблема, как так получилось, что простой алгоритм работает так долго? Можно заметить, что следующее число вычисляется в 2 раза дольше, чем предыдущее. Давайте посмотрим на рекурсивное дерево вызовов:

Можно заметить, что при вычислении через рекурсию многие числа будут считаться по несколько раз, например, число 37 будет посчитано 6 раз. В замерах времени выше мы видели, что вычисление этого занимает 11 секунд, т.е. займёт половину времени от вычислений числа 41 — 66 секунд из 135.

15–17 ноября, Онлайн, Беcплатно

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

Пробуем выполнить новую функция с теми же входными данными:

Во-первых, мы видим, что выполнение теперь занимает доли миллисекунд. Во-вторых, замечаем понижение времени при каждом новом вызове. Это связано с оптимизациями компилятора JavaScript после определенного количества вызова кода. После пары вызовов время уменьшается на 0.1 миллисекунды (для моего компьютера), следовательно, 100 вычислений, которые нам требуются для исходной задачи, пройдут за 0.01 секунду.

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

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

В 0 позиций массива tribonacciNumbersCache — первое число трибонначи, главное не забыть вычитать единицу при получении значения.

Напишем решение исходной задачи — по массиву номеров получить массив с числами трибонначи:

Задачи на LeetCode и CodeWars для тренировки вычислений чисел фибонначи, трибонначи.

Основные идеи

Мы использовали несколько подходов, типичных для динамического программирования:

Кузнечик и кувшинки

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

Рассмотрим вариант с 4-мя кувшинками. Можем перебрать варианты и посчитать, что до последней кувшинки можно добраться 3-мя разными способами:

Грустный кузнечик прыгает по кувшинкам

Можем заметить, что на четвёртую кувшинку мы можем прыгнуть только со второй или с третьей и что количество путей до неё равно количеству путей до второй кувшинки + количество путей до третьей кувшинки. Немного порассуждаем, почему так получается.

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

Аналогичные рассуждения можно провести для дальнейших перемещений, т.е. просто складываем количество путей до предыдущих двух кувшинок.

Понятно, как переходить от одной подзадачи к другой, осталось найти начальные условия. Возьмём за начальные условия количество вариантов попасть на вторую и третью кувшинки, т.е. 1 и 2.

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

Получается следующая функция:

Задача решена, но можем заметить, что все значения, кроме двух последних, не используются, и упростить решение:

В цикле происходит смещение количества путей до i + 1 кувшинки. В начале way1 указывает на количество путей до первой кувшинки, way2 — до второй. После первого выполнения тела цикла way1 указывает на количество путей до второй кувшинки, way2 до третьей, и так далее. В конце выполнения цикла в way2 получится количество путей до n кувшинки.

Максимальный(по сумме элементов) подмассив

Условие задачи: дан массив чисел, требуется найти непрерывную последовательность чисел с максимальной суммой.

Например, получен такой массив:

Массив для нахождения максимального подмассива

Т.е. мы идём слева направо, суммируя элементы, если сумма становится отрицательной, то игнорируем подсумму, если положительной, то прибавляем дальше:

Суммы, используемые для нахождения максимального подмассива

Рассмотрим решение в коде:

Рассмотрим массив arrayOfSums, на каждом шаге итерации:

Видим, что максимальное значение 7. Это и будет ответ в текущей задаче.

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

Реализуем эту идею в коде:

Заключение

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

Источник

Динамическое программирование. Классические задачи

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

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Последовательности

Классической задачей на последовательности является следующая.

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

Используя такую функцию, мы будем решать задачу «с конца» — будем шаг за шагом уменьшать n, пока не дойдем до известных значений.

Но как можно заметить, такая, казалось бы, простая программа уже при n = 40 работает заметно долго. Это связано с тем, что одни и те же промежуточные данные вычисляются по несколько раз — число операций нарастает с той же скоростью, с какой растут числа Фибоначчи — экспоненциально.

Один из выходов из данной ситуации — сохранение уже найденных промежуточных результатов с целью их повторного использования:

Приведенное решение является корректным и эффективным. Но для данной задачи применимо и более простое решение:

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

Именно такое решение и является классическим для динамического программирования: мы сначала решили все подзадачи (нашли все F_i для i 2, соответственно.

Следующая задача одномерного динамического программирования встречается в различных вариациях.

Задача 1. Посчитать число последовательностей нулей и единиц длины n, в которых не встречаются две идущие подряд единицы.

При n 2. То есть данная задача фактически сводится к нахождению чисел Фибоначчи.

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

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

Приведем пару формулировок таких задач:

Задача 2. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо или вниз. Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю.

Задача 3. Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, вниз или по диагонали вправо-вниз. В каждой клетке записано некоторое натуральное число. Необходимо попасть из верхней левой клетки в правую нижнюю. Вес маршрута вычисляется как сумма чисел со всех посещенных клеток. Необходимо найти маршрут с минимальным весом.

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

Рассмотрим более подробно задачу 2. В некоторую клетку с координатами (i,j) можно прийти только сверху или слева, то есть из клеток с координатами (i – 1, j) и (i, j – 1):

Таким образом, для клетки (i, j) число маршрутов A[i][j] будет равно
A[i – 1][j] + A[i][j – 1], то есть задача сводится к двум подзадачам. В данной реализации используется два параметра — i и j — поэтому применительно к данной задаче мы говорим о двумерном динамическом программировании.

Теперь мы можем пройти последовательно по строкам (или по столбцам) массива A, находя число маршрутов для текущей клетки по приведенной выше формуле. Предварительно в A[0][0] необходимо поместить число 1.

В задаче 3 в клетку с координатами (i, j) мы можем попасть из клеток с координатами
(i – 1, j), (i, j – 1) и (i – 1, j – 1). Допустим, что для каждой из этих трех клеток мы уже нашли маршрут минимального веса, а сами веса поместили в W[i – 1][j], W[i][j – 1],
W[i – 1][j – 1]. Чтобы найти минимальный вес для (i, j), необходимо выбрать минимальный из весов W[i – 1][j], W[i][j – 1], W[i – 1][j – 1] и прибавить к нему число, записанное в текущей клетке:

W[i][j] = min(W[i–1][j], W[i][j – 1], W[i – 1][j – 1]) + A[i][j];

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

На следующем рисунке приведен пример исходных данных и одного из шагов алгоритма.

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

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

Задачи на подпоследовательности

Рассмотрим задачу о возрастающей подпоследовательности.

Задача 4. Дана последовательность целых чисел. Необходимо найти ее самую длинную строго возрастающую подпоследовательность.

Начнем решать задачу с начала — будем искать ответ, начиная с первых членов данной последовательности. Для каждого номера i будем искать наибольшую возрастающую подпоследовательность, оканчивающуюся элементом в позиции i. Пусть исходная последовательность хранится в массиве A. В массиве L будем записывать длины максимальных подпоследовательностей, оканчивающихся текущим элементом. Пусть мы нашли все L[i] для 1

Источник

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

Авторизуйтесь

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

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

технический директор 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. Либо это могут быть задачи, где нужно просчитать все возможные комбинации переходов или расположения элементов. Классический пример, в котором используется этот метод — последовательность чисел Фибоначчи.

Как видно, для решения задачек с последовательностями, нужно определить следующие условия: рекуррентная зависимость элементов последовательности друг от друга, начальное состояние. Они не всегда могут быть заданы в условии напрямую, как это было в задаче выше. Например, в видео «Динамическое программирование: траектории кузнечика» разбирают задание с количеством переходов из точки 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 вычислений.

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

Источник