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

13

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

анонимное
источник

Ответы:

9

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

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

Юваль Фильмус
источник
Тогда счетчик будет заключаться в том, что всякий раз, когда сложность запоминания больше, чем входные данные (возможно, просто> O (N)), скорее всего, динамическое программирование не поможет. То есть когда вы нечасто сталкиваетесь с одной и той же ситуацией.
edA-qa mort-ora-y
1
Памятка! = Динамическое программирование!
Рафаэль
1
Я не думаю, что мы говорим об этом, но вопрос указывает на уменьшение сложности времени. Динамическое программирование само по себе просто решает проблему. Динамическое программирование + запоминание - это общий способ улучшить временную сложность, где это возможно .
edA-qa mort-ora-y
@ edA-qamort-ora-y: Верно. Я думаю, что важно четко указать на это, поскольку ФП, по-видимому, смешивает / смешивает понятия.
Рафаэль
8

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

  • не имеет побочных эффектов и
  • зависит только от его параметров (т.е. не от какого-то состояния).

Это сэкономит вам время, если (и только если) функция вызывается с одними и теми же параметрами снова и снова. Популярные примеры включают в себя рекурсивное определение чисел Фибоначчи, то есть

f(0)=0f(1)=1f(n+2)=f(n+1)+f(n), n0

Если оценивать наивно, то вызывается экспоненциально часто. С запоминанием, всегда вычислялось уже , таким образом, остается только линейное количество вызовов.f ( n ) f ( n + 1 )ff(n)f(n+1)

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

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


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

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

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

Теперь, это только описывает класс проблем, которые могут быть выражены определенным видом рекурсии. Оценка их (часто) эффективна, потому что запоминание может быть применено с большим эффектом (см. Выше); обычно меньшие подзадачи возникают как часть многих более крупных проблем. Популярные примеры включают расстояние редактирования и алгоритм Беллмана-Форда .

Рафаэль
источник
Вы говорите, что бывают случаи, когда динамическое программирование приведет к лучшей временной сложности, но запоминание не поможет (или, по крайней мере, не так сильно)? У вас есть примеры? Или вы просто говорите, что динамическое программирование полезно только для подмножества проблем, где запоминание?
svick
@svick: Динамическое программирование не ускорит ничего по сути, только если рекурсия DP оценивается с мемоизация (который, как правило , () случай!). Опять же: DP - это способ моделирования проблем с точки зрения рекурсии, запоминание - это метод ускорения подходящих рекурсивных алгоритмов (независимо от того, используется ли DP). Нет смысла сравнивать оба напрямую. Конечно, вы пытаетесь смоделировать проблему как DP, потому что вы ожидаете применить запоминание и, следовательно, решить его быстрее, чем наивный подход. Но точка зрения DP также не всегда приводит к наиболее эффективному алгоритму.
Рафаэль
Если у вас есть несколько доступных процессоров, динамическое программирование значительно повышает реальную производительность, поскольку вы можете распараллеливать части. Это на самом деле не меняет сложность времени.
edA-qa mort-ora-y
@ edA-qamort-ora-y: Это верно для любой рекурсии. Однако не ясно, что это создает хорошее ускорение, потому что запоминание менее эффективно по сравнению с границами процессора.
Рафаэль
Исправление: оценка DP-рецидивов наивно все же может быть (намного) быстрее, чем грубая сила; ср сюда .
Рафаэль