Что такое динамическое программирование ?
Чем он отличается от рекурсии, запоминания и т. Д.?
Я читал статью в Википедии , но до сих пор не понимаю этого.
algorithm
dynamic-programming
smac89
источник
источник
Ответы:
Динамическое программирование - это когда вы используете знания прошлого, чтобы облегчить решение будущей проблемы.
Хорошим примером является решение последовательности Фибоначчи для n = 1 000 002.
Это будет очень долгий процесс, но что если я дам вам результаты для n = 1 000 000 и n = 1 000 001? Внезапно проблема стала более управляемой.
Динамическое программирование часто используется в задачах со строками, таких как задачи редактирования строк. Вы решаете подмножество проблем, а затем используете эту информацию для решения более сложной исходной проблемы.
При динамическом программировании вы обычно сохраняете свои результаты в какой-то таблице. Когда вам нужен ответ на проблему, вы ссылаетесь на таблицу и смотрите, знаете ли вы, что это такое. Если нет, то вы используете данные в своей таблице, чтобы стать шагом к ответу.
В книге «Алгоритмы Кормена» есть отличная глава о динамическом программировании. И это бесплатно в Google Книгах! Проверьте это здесь.
источник
Динамическое программирование - это метод, используемый для избежания многократного вычисления одной и той же подзадачи в рекурсивном алгоритме.
Давайте возьмем простой пример чисел Фибоначчи: найти n- е число Фибоначчи, определенное как
F n = F n-1 + F n-2 и F 0 = 0, F 1 = 1
Рекурсия
Очевидный способ сделать это рекурсивно:
Динамическое программирование
Рекурсия выполняет много ненужных вычислений, потому что данное число Фибоначчи будет вычислено несколько раз. Простой способ улучшить это - кэшировать результаты:
Лучший способ сделать это - полностью избавиться от рекурсии, оценивая результаты в правильном порядке:
Мы даже можем использовать постоянное пространство и хранить только необходимые частичные результаты на этом пути:
Как применить динамическое программирование?
Динамическое программирование, как правило, работает для задач с внутренним порядком слева направо, таких как строки, деревья или целочисленные последовательности. Если наивный рекурсивный алгоритм не вычисляет одну и ту же подзадачу несколько раз, динамическое программирование не поможет.
Я сделал набор проблем, чтобы помочь понять логику: https://github.com/tristanguigue/dynamic-programing
источник
if n in cache
как в примере сверху вниз или я что-то упускаю.Мемоизация - это когда вы сохраняете предыдущие результаты вызова функции (реальная функция всегда возвращает одно и то же, учитывая одни и те же входные данные). Это не имеет значения для алгоритмической сложности до сохранения результатов.
Рекурсия - это метод вызова функции, обычно с меньшим набором данных. Поскольку большинство рекурсивных функций могут быть преобразованы в аналогичные итеративные функции, это не имеет значения и для алгоритмической сложности.
Динамическое программирование - это процесс решения подзадач, которые легче решить, и выработка ответа на него. Большинство алгоритмов DP будут работать во времени между алгоритмом Гриди (если таковой существует) и экспоненциальным (перечислите все возможности и найдите лучший).
источник
Это оптимизация вашего алгоритма, которая сокращает время выполнения.
Хотя алгоритм жадности обычно называют наивным , поскольку он может запускаться несколько раз на одном и том же наборе данных, динамическое программирование позволяет избежать этой ловушки за счет более глубокого понимания частичных результатов, которые должны быть сохранены, чтобы помочь в создании окончательного решения.
Простым примером является прохождение дерева или графика только через узлы, которые могли бы внести вклад в решение, или внесение в таблицу решений, которые вы нашли до сих пор, чтобы вы могли избегать обхода одних и тех же узлов снова и снова.
Вот пример проблемы, которая подходит для динамического программирования от онлайн-эксперта UVA: Edit Steps Ladder.
Я собираюсь кратко рассказать о важной части анализа этой проблемы, взятой из книги «Проблемы программирования», я предлагаю вам проверить это.
Здесь очень конкретный анализ того, что требуется для получения наиболее оптимальных частичных результатов, - это то, что делает решение «динамическим».
Вот альтернативное, полное решение той же проблемы. Это также «динамический», хотя его исполнение отличается. Я предлагаю вам проверить, насколько эффективно это решение, представив его онлайн-судье UVA. Я нахожу удивительным, как такая тяжелая проблема была решена так эффективно.
источник
Ключевыми моментами динамического программирования являются «перекрывающиеся подзадачи» и «оптимальная подструктура». Эти свойства проблемы означают, что оптимальное решение состоит из оптимальных решений ее подзадач. Например, задачи кратчайшего пути демонстрируют оптимальную подструктуру. Кратчайший путь от A до C - это кратчайший путь от A до некоторого узла B, за которым следует кратчайший путь от этого узла B к C.
Более подробно, чтобы решить проблему кратчайшего пути, вы:
Поскольку мы работаем снизу вверх, у нас уже есть решения для подзадач, когда приходит время их использовать, запоминая их.
Помните, что задачи динамического программирования должны иметь как перекрывающиеся подзадачи, так и оптимальную подструктуру. Генерация последовательности Фибоначчи не является проблемой динамического программирования; он использует запоминание, потому что у него есть перекрывающиеся подзадачи, но у него нет оптимальной подструктуры (потому что нет проблем с оптимизацией).
источник
Динамическое программирование
Определение
Динамическое программирование (DP) - это общая методика проектирования алгоритмов для решения задач с перекрывающимися подзадачами. Эта техника была изобретена американским математиком Ричардом Беллманом в 1950-х годах.
Ключевая идея
Основная идея заключается в том, чтобы сохранить ответы перекрывающихся небольших подзадач, чтобы избежать повторного вычисления.
Свойства динамического программирования
источник
Я также очень плохо знаком с динамическим программированием (мощный алгоритм для определенного типа задач)
Проще говоря, просто думайте, что динамическое программирование - это рекурсивный подход с использованием предыдущих знаний
Предыдущие знания - это то, что здесь важнее всего. Следите за решением подзадач, которые у вас уже есть.
Рассмотрим это, самый простой пример для дп из Википедии
Нахождение последовательности Фибоначчи
Давайте разберем вызов функции, скажем, n = 5
В частности, fib (2) был рассчитан три раза с нуля. В более крупных примерах пересчитывается намного больше значений fib или подзадач, что приводит к экспоненциальному алгоритму времени.
Теперь давайте попробуем это, сохранив значение, которое мы уже обнаружили в структуре данных, скажем, Map
Здесь мы сохраняем решение подзадач на карте, если у нас его еще нет. Этот метод сохранения значений, который мы уже рассчитали, называется Memoization.
Наконец, для проблемы сначала попытайтесь найти состояния (возможные подзадачи и постарайтесь придумать лучший рекурсивный подход, чтобы вы могли использовать решение предыдущей подзадачи в последующих).
источник
Динамическое программирование - это метод решения задач с перекрывающимися подзадачами. Алгоритм динамического программирования решает каждую подзадачу всего один раз, а затем сохраняет свой ответ в виде таблицы (массива). Избегайте повторного вычисления ответа каждый раз, когда возникает проблема с подзадачей. Основная идея динамического программирования заключается в следующем: избегайте вычисления одного и того же материала дважды, обычно ведя таблицу известных результатов подзадач.
Семь шагов в разработке алгоритма динамического программирования следующие:
источник
6. Convert the memoized recursive algorithm into iterative algorithm
обязательный шаг? Это будет означать, что его окончательная форма не рекурсивна?Короче говоря, разница между запоминанием рекурсии и динамическим программированием
Динамическое программирование, как следует из названия, использует предыдущее вычисленное значение для динамического построения следующего нового решения.
Где применять динамическое программирование: если ваше решение основано на оптимальной подструктуре и перекрывающейся подзадаче, то в этом случае будет полезно использовать ранее вычисленное значение, поэтому вам не придется его пересчитывать. Это подход снизу вверх. Предположим, вам нужно вычислить fib (n). В этом случае все, что вам нужно сделать, - это добавить предыдущее вычисленное значение fib (n-1) и fib (n-2).
Рекурсия: в основном подразделение вашей задачи на меньшую часть, чтобы с легкостью решить ее, но имейте в виду, что это не предотвратит повторное вычисление, если у нас будет то же значение, вычисленное ранее в другом вызове рекурсии.
Заметка: По сути, сохранение старого вычисленного значения рекурсии в таблице известно как запоминание, которое позволит избежать повторного вычисления, если оно уже было вычислено каким-либо предыдущим вызовом, поэтому любое значение будет вычислено один раз. Таким образом, перед вычислением мы проверяем, было ли это значение уже вычислено или нет, если оно уже рассчитано, то мы возвращаем то же самое из таблицы вместо пересчета. Это также подход сверху вниз
источник
Вот простой код питона пример
Recursive
,Top-down
,Bottom-up
подход для ряда Фибоначчи:Рекурсивный: O (2 n )
Сверху вниз: O (n) Эффективно для большего ввода
Вверху: O (n) Для простоты и небольших входных размеров
источник