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

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

В информатике есть несколько способов описания подхода к решению алгоритма. Жадный, наивный, разделяй и властвуй — всё это способы решения алгоритмов. Один из таких способов называется динамическим программированием (DP). В этой статье мы рассмотрим, что такое динамическое программирование, его характеристики и два основных подхода к решению алгоритмов с помощью DP.

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

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

Скажем, например, у нас есть рюкзак, в который может поместиться только определённое количество предметов. Какая комбинация предметов даст нам максимальную ценность? Или предположим, что у нас есть рюкзак определённой грузоподъёмности. Какая комбинация предметов с заданным весом даст нам максимальную ценность?

Наивные решения

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

Нисходящие решения

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

Решения снизу-вверх

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

Фибоначчи

Последовательность Фибоначчи — это последовательность чисел, каждое из которых представляет собой сумму двух предыдущих чисел, начиная с 0 и 1:

Fn = 0, 1, 1, 2, 3, 5, 8, 13, 21…и т.д.
0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21
13 + 21 = 34…и т.д.

Подсказка

По заданному числу n найдите n- е число в последовательности Фибоначчи.

Решение 1. Наивно

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

Пример наивного решения для Фибоначчи выглядит так:

const fibNaive = (num) => <
if(num <
if(num Читайте также: Разработка приложений для iOS или Android: какую платформу выбрать?

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

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

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

Это решение изменяет временную сложность с O (2 n) на O (n).

Решение 3. Подход к динамическому программированию № 2 — снизу-вверх с табуляцией

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

for(let i = 3; i <
//find all the substrings.
substrs = [];
maxString = «»;
otherString = «»;
if(str1.length > str2.length) <
maxString = str1;
otherString = str2;
> else <
maxString = str2;
otherString = str1;
>

for(let i = 0; i < // O(m)
if(new RegExp(string).test(otherString)) <
if(maxLength <

let i = str1.length;
let j = str2.length;
//if the strings don’t exist, return 0
if(i === 0 || j === 0) <
return count;
>

if(str1[i — 1] === str2[j — 1]) < // if the chars are the same, up the count and shorten string by 1
count = topDown(str1.slice(0, i — 1), str2.slice(0, j — 1), count + 1);
>
count = Math.max(count, //max between count and the other function
Math.max( // max between looking at shortening one word vs shortening the other word.
topDown(str1.slice(0, i), str2.slice(0, j — 1), 0),
topDown(str1.slice(0, i — 1), str2.slice(0, j), 0)));

Сложность по времени для этого решения составляет O (n + m), чтобы учесть размеры различных строк.

Решение 3. Восходящее решение с табуляцией

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

for (let i = 0; i <
let table = create2DArray(A, B); // create the table
let max = 0; // initialize and declare max substring length to be 0
//start i and j at 1 so we can compare characters to previous row and column
for (let i = 1; i

Источник

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

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

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

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

Содержание

История

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

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

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

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

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

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

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

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

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

Языки программирования могут запоминать результат вызова функции с определенным набором аргументов (мемоизация), чтобы ускорить «вычисление по имени». В некоторых языках такая возможность встроена (например, Scheme, Common Lisp, Perl), а в некоторых требует дополнительных расширений (C++).

Известны сериальное динамическое программирование, включённое во все учебники по исследованию операций, и несериальное динамическое программирование (НСДП), которое в настоящее время слабо известно, хотя было открыто в 1960-х годах.

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

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

Источник

Динамическое программирование — базовые понятия

Общие принципы

Рассмотрим такую задачу: найти N-е число Фибоначчи.

Эту задачу можно решить рекурсивно:

Почему? Потому что, чтобы посчитать N-е число, нам нужно будет независимо посчитать (N-1)-е число и (N-2)-е число, и это в минимум в два раза больше действий, чем нужно для (N-2). А значит, для подсчета N-го числа Фибоначчи необходимо 2 раза посчитать (N-2)-е число, и это занимает в два раза больше времени, а значит это хотя бы \(2^\frac<2>\) действий.

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

Чтобы решить задачу по динамике вы должны ответить на 5 вопросов: * Что лежит в массиве? (самый важный вопрос чаще всего) * Как инициализировать начало массива? * Как обходить массив? (чаще всего слева направо, но не всегда) * Какой формулой считать элементы массива? * Где в массиве лежит ответ?

Одномерная динамика: кузнечик

Рассмотрим такую задачу:

Как решать такие задачи? Нужно придумать рекуррентную формулу, как ответ для N зависит от ответа для меньших чисел.

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

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

Очень похоже на числа Фибоначчи, да? Можете посмотреть на числа, которые мы уже выписали, там все отлично подходит:

dp[4] = 4 = 1 + 1 + 2 = dp[1] + dp[2] + dp[3]

dp[5] = 7 = 1 + 2 + 4 = dp[2] + dp[3] + dp[4].

Так что программа пишется легко:

Давайте изменим немного задачу: Теперь некоторые из клеток закрыты. То есть нам известно про конкретные клетки, что на них кузнечик прыгать не может. Тогда задача все еще решается так же, только нужно убедиться, что dp[x] = 0 для всех запрещенных x!

Так как до этих клеток есть ровно один путь.

Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив.

Восстановление ответа

В последней задаче было здорово найти, что в оптимальном пути черепашки набирается 113 монет, но интересно, что именно это за путь. Такую задачу называют восстановлением ответа в динамике.

Есть два способа, которыми можно это сделать.

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

Задание

Решите как можно больше задач из простого контеста:

А также решите как можно больше задач из сложного контеста:

Разбор еще нескольких задач

Давайте разберем еще несколько задач.

Последовательности без 3 единиц подряд

Условие:

Решение:

Давайте хранить в \(dp[N]\) ровно число таких последовательностей длины \(N\) (это первое, что должно приходить в голову).

Давайте посмотрим для начала для маленьких чисел:

Сходу закономерность можно не увидеть. Нужно догадаться сгруппировать эти числа по том, сколько в конце единичек. Например, для dp[4]:

Так мы замечаем и доказываем формулу: \(dp[N] = dp[N-1] + dp[N-2] + dp[N-3]\)

Теперь за \(O(N)\) ее легко посчитать.

Лесенки

Условие:

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

Решение:

По числам построить закономерность сложно, и по самим лесенкам тоже. Не видно какого-то рассуждения вида “ко всем лесенкам размера N-1 можно положить на любой слой еще один кубик”, иногда ведь и нельзя.

Теперь осталось понять как инициализировать этот массив и аккуратно по нему пройтись. Давайте инициализируем его ровно для случая \(n=0, m=0\) :

Для всех \(n > 0\) наша формула будет находить ответ через числа с меньшим n, а значит алгоритм корректен.

Источник

Занятие 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, то формула соответствует нахождению последовательности чисел Фибоначчи.

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

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

Источник