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

277

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

Чем он отличается от рекурсии, запоминания и т. Д.?

Я читал статью в Википедии , но до сих пор не понимаю этого.

smac89
источник
1
Вот одно руководство Майкла А. Трика из CMU, которое мне показалось особенно полезным: mat.gsia.cmu.edu/classes/dynamic/dynamic.html Это, безусловно, в дополнение ко всем ресурсам, которые рекомендовали другие (все другие ресурсы, особенно CLR и Кляйнберг, Тардос очень хорошие!). Причина, по которой мне нравится этот урок, заключается в том, что он вводит передовые концепции довольно постепенно. Это немного староватый материал, но это хорошее дополнение к списку ресурсов, представленных здесь. Также проверьте страницу и лекции Стивен Скиена на динамическом программировании: cs.sunysb.edu/~algorith/video-lectures Http:
Эдмон
11
Я всегда находил «Динамическое программирование» запутанным термином - «Динамическое» предполагает не статическое, но что такое «Статическое программирование»? И «... Программирование» напоминает «Объектно-ориентированное программирование» и «Функциональное программирование», предполагая, что DP - это парадигма программирования. У меня нет лучшего названия (возможно, «Динамические алгоритмы»?), Но очень жаль, что мы застряли с этим.
dimo414
3
@ dimo414 «Программирование» здесь больше относится к «линейному программированию», которое относится к классу методов математической оптимизации. См. Статью Математическая оптимизация для списка других методов математического программирования.
syockit
1
@ dimo414 «Программирование» в данном контексте относится к табличному методу, а не к написанию компьютерного кода. - Coreman
user2618142
Проблема минимизации стоимости билета на автобус, описанная в cs.stackexchange.com/questions/59797/… , лучше всего решается в динамическом программировании.
Trueadjustr

Ответы:

211

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

Хорошим примером является решение последовательности Фибоначчи для n = 1 000 002.

Это будет очень долгий процесс, но что если я дам вам результаты для n = 1 000 000 и n = 1 000 001? Внезапно проблема стала более управляемой.

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

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

В книге «Алгоритмы Кормена» есть отличная глава о динамическом программировании. И это бесплатно в Google Книгах! Проверьте это здесь.

samoz
источник
50
Вы только что не описали памятку?
ужасный ужас
31
Я бы сказал, что запоминание - это форма динамического программирования, когда запомненная функция / метод является рекурсивной.
Даниэль Хакстеп
6
Хороший ответ, добавил бы только упоминание об оптимальной подструктуре (например, каждое подмножество любого пути по кратчайшему пути от A до B само является кратчайшим путем между двумя конечными точками, предполагая метрику расстояния, которая соблюдает неравенство треугольника).
Ши
5
Я бы не сказал «проще», но быстрее. Распространенным заблуждением является то, что dp решает проблемы, которые не могут наивные алгоритмы, а это не так. Дело не в функциональности, а в производительности.
andandandand
6
Используя запоминание, проблемы динамического программирования могут быть решены сверху вниз. то есть, вызывая функцию для вычисления окончательного значения, а эта функция, в свою очередь, вызывает ее саморекурсивно для решения подзадач. Без этого проблемы динамического программирования могут быть решены только снизу вверх.
Пранав
176

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

Давайте возьмем простой пример чисел Фибоначчи: найти n- е число Фибоначчи, определенное как

F n = F n-1 + F n-2 и F 0 = 0, F 1 = 1

Рекурсия

Очевидный способ сделать это рекурсивно:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

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

  • Сверху вниз - памятка

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

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]
  • Вверх дном

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

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

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

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi
  • Как применить динамическое программирование?

    1. Найдите рекурсию в задаче.
    2. Сверху вниз: сохраните ответ для каждой подзадачи в таблице, чтобы избежать необходимости пересчитывать их.
    3. Снизу вверх: найдите правильный порядок оценки результатов, чтобы при необходимости были доступны частичные результаты.

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

Я сделал набор проблем, чтобы помочь понять логику: https://github.com/tristanguigue/dynamic-programing

Тристан
источник
3
Это отличный ответ, и сбор проблем на Github также очень полезен. Спасибо!
p4sh4
Просто из любопытства прояснить ситуацию - на ваш взгляд, рекурсивная реализация с использованием рекуррентных отношений и запоминания - это динамическое программирование?
Кодор
Спасибо за объяснение. Отсутствует ли условие снизу вверх: if n in cacheкак в примере сверху вниз или я что-то упускаю.
DavidC
Правильно ли я понимаю тогда, что любой цикл, в котором значения, вычисленные на каждой итерации, используются в последующих итерациях, является примером динамического программирования?
Алексей
Не могли бы вы дать какие-либо ссылки на интерпретацию, которую вы дали, включая нисходящие и восходящие специальные случаи?
Алексей
38

Мемоизация - это когда вы сохраняете предыдущие результаты вызова функции (реальная функция всегда возвращает одно и то же, учитывая одни и те же входные данные). Это не имеет значения для алгоритмической сложности до сохранения результатов.

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

Динамическое программирование - это процесс решения подзадач, которые легче решить, и выработка ответа на него. Большинство алгоритмов DP будут работать во времени между алгоритмом Гриди (если таковой существует) и экспоненциальным (перечислите все возможности и найдите лучший).

  • Алгоритмы DP могут быть реализованы с рекурсией, но они не должны быть.
  • Алгоритмы DP не могут быть ускорены запоминанием, поскольку каждая подзадача решается только однажды (или вызывается функция «решить») один раз.
philomathohollic
источник
Очень четко изложено. Я бы хотел, чтобы инструкторы алгоритма могли это хорошо объяснить.
Келли С. Френч
22

Это оптимизация вашего алгоритма, которая сокращает время выполнения.

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

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

Вот пример проблемы, которая подходит для динамического программирования от онлайн-эксперта UVA: Edit Steps Ladder.

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

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

Подстановка - замените один символ из шаблона «s» на другой символ в тексте «t», например, изменив «выстрел» на «точечный».

Вставка - вставьте один символ в шаблон «s», чтобы он соответствовал тексту «t», например, изменив «назад» на «agog».

Удаление - удалите один символ из шаблона "s", чтобы он соответствовал тексту "t", например, изменив "час" на "наш".

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

Мы можем определить рекурсивный алгоритм, используя наблюдение, что последний символ в строке должен совпадать, заменяться, вставляться или удаляться. Отрезание символов в последней операции редактирования оставляет парную операцию, оставляет пару небольших строк. Пусть i и j будут последним символом соответствующего префикса и t соответственно. есть три пары более коротких строк после последней операции, соответствующих строке после сопоставления / замены, вставки или удаления. Если бы мы знали стоимость редактирования трех пар более мелких строк, мы могли бы решить, какой вариант приведет к наилучшему решению, и выбрать этот вариант соответствующим образом. Мы можем узнать эту стоимость с помощью потрясающей рекурсии:

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

Этот алгоритм является правильным, но также невероятно медленным.

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

Почему алгоритм такой медленный? Это занимает экспоненциальное время, потому что оно пересчитывает значения снова и снова и снова. В каждой позиции в строке рекурсия разветвляется тремя путями, что означает, что она растет со скоростью, по крайней мере, 3 ^ n - даже быстрее, поскольку большинство вызовов уменьшают только один из двух индексов, а не оба.

Итак, как мы можем сделать алгоритм практичным? Важным наблюдением является то, что большинство этих рекурсивных вызовов являются вычислительными вещами, которые уже были вычислены ранее. Откуда нам знать? Ну, может быть только | s | · | Т | возможные уникальные рекурсивные вызовы, поскольку существует только столько различных (i, j) пар, которые служат параметрами рекурсивных вызовов.

Сохраняя значения для каждой из этих (i, j) пар в таблице, мы можем избежать их пересчета и просто искать их по мере необходимости.

Таблица представляет собой двумерную матрицу m, где каждый из | s | · | t | В ячейках указана стоимость оптимального решения этой подзадачи, а также указатель родителя, объясняющий, как мы попали в это место:

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

Динамическая версия программирования имеет три отличия от рекурсивной версии.

Во-первых, он получает промежуточные значения, используя поиск в таблице вместо рекурсивных вызовов.

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

** В-третьих, ** В-третьих, в ней используется более общая целевая cell()функция вместо простого возврата m [| s |] [| t |] .cost. Это позволит нам применить эту процедуру к более широкому классу проблем.

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

Вот альтернативное, полное решение той же проблемы. Это также «динамический», хотя его исполнение отличается. Я предлагаю вам проверить, насколько эффективно это решение, представив его онлайн-судье UVA. Я нахожу удивительным, как такая тяжелая проблема была решена так эффективно.

andandandand
источник
Действительно ли хранилище требуется для динамического программирования? Разве пропущенный объем работы не квалифицирует алгоритм как динамический?
Nthalk
Вы должны собрать оптимальные пошаговые результаты, чтобы сделать алгоритм «динамическим». Динамическое программирование проистекает из работы Беллмана в ИЛИ, если вы говорите, что «пропустить любое количество слов - это динамическое программирование», вы обесцениваете термин, так как любой эвристический поиск будет динамическим программированием. ru.wikipedia.org/wiki/Dynamic_programming
andandandand
13

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

Более подробно, чтобы решить проблему кратчайшего пути, вы:

  • найдите расстояния от начального узла до каждого касающегося его узла (скажем, от A до B и C)
  • найти расстояния от этих узлов до узлов, соприкасающихся с ними (от B до D и E, а также от C до E и F)
  • теперь мы знаем кратчайший путь от A до E: это кратчайшая сумма Ax и xE для некоторого узла x, который мы посетили (B или C)
  • повторяйте этот процесс, пока мы не достигнем конечного узла назначения

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

Помните, что задачи динамического программирования должны иметь как перекрывающиеся подзадачи, так и оптимальную подструктуру. Генерация последовательности Фибоначчи не является проблемой динамического программирования; он использует запоминание, потому что у него есть перекрывающиеся подзадачи, но у него нет оптимальной подструктуры (потому что нет проблем с оптимизацией).

Ник Льюис
источник
1
ИМХО, это единственный ответ, который имеет смысл с точки зрения динамического программирования. Мне любопытно с тех пор, когда люди начали объяснять DP, используя числа Фибоначчи (вряд ли уместно).
Терри Ли
@TerryLi, это может иметь «смысл», но это не так легко понять. Проблема числа Фибоначчи известна и проста для понимания.
Ajay
6

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

Определение

Динамическое программирование (DP) - это общая методика проектирования алгоритмов для решения задач с перекрывающимися подзадачами. Эта техника была изобретена американским математиком Ричардом Беллманом в 1950-х годах.

Ключевая идея

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

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

  • Экземпляр решается с использованием решений для небольших экземпляров.
  • Решения для меньшего экземпляра могут понадобиться несколько раз, поэтому сохраняйте их результаты в таблице.
  • Таким образом, каждый меньший случай решается только один раз.
  • Дополнительное пространство используется для экономии времени.
Сабир Аль Фатех
источник
5

Я также очень плохо знаком с динамическим программированием (мощный алгоритм для определенного типа задач)

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

Предыдущие знания - это то, что здесь важнее всего. Следите за решением подзадач, которые у вас уже есть.

Рассмотрим это, самый простой пример для дп из Википедии

Нахождение последовательности Фибоначчи

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

Давайте разберем вызов функции, скажем, n = 5

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

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

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

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

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

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

Аман Сингх
источник
Прямой плагиат из Википедии. Downvoted !!
Солидак
4

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

Семь шагов в разработке алгоритма динамического программирования следующие:

  1. Установите рекурсивное свойство, которое дает решение экземпляра проблемы.
  2. Разработать рекурсивный алгоритм согласно рекурсивному свойству
  3. Посмотрите, решается ли тот же самый экземпляр проблемы снова и снова в рекурсивных вызовах
  4. Разработайте запомненный рекурсивный алгоритм
  5. Смотрите шаблон в хранении данных в памяти
  6. Преобразовать запомненный рекурсивный алгоритм в итерационный алгоритм
  7. Оптимизируйте итерационный алгоритм, используя хранилище по мере необходимости (оптимизация хранилища)
Аднан Куреши
источник
Это 6. Convert the memoized recursive algorithm into iterative algorithmобязательный шаг? Это будет означать, что его окончательная форма не рекурсивна?
Trueadjustr
не обязательный, необязательный
Аднан Куреши
Цель состоит в том, чтобы заменить рекурсивный алгоритм, используемый для хранения данных в памяти, итерацией по сохраненным значениям, потому что итеративное решение сохраняет создание стека функций для каждого сделанного рекурсивного вызова.
Дэвид С. Ранкин
2

Короче говоря, разница между запоминанием рекурсии и динамическим программированием

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

Где применять динамическое программирование: если ваше решение основано на оптимальной подструктуре и перекрывающейся подзадаче, то в этом случае будет полезно использовать ранее вычисленное значение, поэтому вам не придется его пересчитывать. Это подход снизу вверх. Предположим, вам нужно вычислить fib (n). В этом случае все, что вам нужно сделать, - это добавить предыдущее вычисленное значение fib (n-1) и fib (n-2).

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

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

прилагать усилия
источник
-1

Вот простой код питона пример Recursive, Top-down, Bottom-upподход для ряда Фибоначчи:

Рекурсивный: O (2 n )

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

Сверху вниз: O (n) Эффективно для большего ввода

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

Вверху: O (n) Для простоты и небольших входных размеров

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))
0xAliHn
источник
Первый случай НЕ имеет времени выполнения n ^ 2, его сложность по времени составляет O (2 ^ n): stackoverflow.com/questions/360748/…
Сэм
обновил спасибо. @ Сэм
0xAliHn