6 ответов:
какая разница между мемоизация и динамического программирования?
Memoization - это термин, описывающий метод оптимизации, в котором вы кэшируете ранее вычисленные результаты и возвращаете кэшированный результат, когда снова требуется то же вычисление.
динамическое программирование является методом рекурсивного решения задач и применим при вычислениях подзадач частично покрывать.
динамическое программирование обычно реализовано с помощью табуляции, но также может быть реализовано с помощью memoization. Так что, как вы можете видеть, ни один из них не является "подмножеством" другого.
разумный вопрос такой: в чем разница между табулирования (типичный метод динамического программирования) и мемоизация?
при решении задачи динамического программирования с помощью табуляции вы решаете проблему "снизу вверх", то есть, сначала решая все связанные подзадачи, как правило, заполняя n-размерная таблица. На основе результатов, приведенных в таблице, затем вычисляется решение "верхней" / исходной задачи.
Если вы используете memoization для решения проблемы, вы делаете это, поддерживая карту уже решенных подзадач. Ты сделаешь это"сверху вниз" в том смысле, что вам решать "сверху" проблему (которая, как правило, рекурсивно вызывает вниз, чтобы решить подзадачи).
хороший слайд с
здесь(ссылка теперь мертва, слайд все еще хорош):
- если все подзадачи должны быть решены хотя бы один раз, восходящий алгоритм динамического программирования обычно превосходит нисходящий записанный алгоритм на постоянный коэффициент
- нет накладных расходов для рекурсии и меньше накладных расходов для поддержания таблицы
- есть некоторые проблемы, для которых обычные шаблон доступа к таблицам в алгоритме динамического программирования может быть использован для еще большего сокращения времени или пространства
- если некоторые подзадачи в пространстве подзадач вообще не нужно решать, то запомненное решение имеет преимущество решения только тех подзадач, которые определенно требуются
дополнительные материалы:
- Википедия: Memoization, Динамическое Программирование
- связанный так Q / A: Memoization или табличный подход для динамического программирования
Это было переписано как статья здесь.
динамическое программирование-это алгоритмическая парадигма, которая решает заданную задачу сложная задача путем разбиения ее на подзадачи и сохранения результатов подзадач, чтобы избежать вычисления тех же результатов снова.
http://www.geeksforgeeks.org/dynamic-programming-set-1/
Memoization-это простой метод отслеживания ранее решенных решений (часто реализуемый как пара значений хэш-ключа, в отличие от табуляции, которая часто основана на массивы), так что они не пересчитываются, когда они встречаются снова. Он может использоваться как снизу вверх, так и сверху вниз.
посмотреть эта дискуссия на memoization против табуляции.
динамическое программирование часто называют Memoization!
Memoization-это метод сверху вниз(начните решать данную проблему, разбивая ее), а динамическое программирование-это метод снизу вверх (начните решать от тривиальной подзадачи, вплоть до данной проблемы)
DP находит решение, начиная с базового случая(ов) и работает свой путь вверх. ДП решает все проблемы, потому что это снизу-вверх
в отличие от мемоизации, который решает только нужны подпроблемы
DP имеет потенциал для преобразования экспоненциально-временных решений грубой силы в алгоритмы полиномиального времени.
DP может быть гораздо более эффективным, потому что его итерационный
напротив, Мемуаризация должна оплачивать (часто значительные) накладные расходы из-за рекурсия.
чтобы быть более простым, Memoization использует нисходящий подход для решения проблемы, т. е. он начинается с основной(основной) проблемы, затем разбивает ее на подзадачи и решает эти подзадачи аналогично. При таком подходе одна и та же подзадача может возникать несколько раз и потреблять больше циклов процессора, следовательно, увеличивать временную сложность. В то время как в динамическом программировании одна и та же подзадача не будет решена несколько раз, но предыдущий результат будет использоваться для оптимизации решение.
(1) Memoization и DP, принципиально, это действительно одно и то же. Потому что: рассмотрим определение DP:" перекрывающиеся подзадачи ""и оптимальная подструктура". Мемуаризация полностью обладает этими 2.
(2) Memoization-это DP с риском переполнения стека, рекурсия глубока. DP снизу вверх не имеет этого риска.
(3) Memoization нуждается в хэш-таблице. Так что дополнительное пространство и некоторое время поиска.
Итак, чтобы ответить вопрос:
-принципиально, (1) означает, что это одно и то же.
-принимая во внимание (2), Если вы действительно хотите, memoization является подмножеством DP, в том смысле, что проблема, разрешимая memoization, будет разрешима DP, но проблема, разрешимая DP, может быть не разрешима memoization (потому что она может переполняться стеком).
-принимая во внимание (3), они имеют незначительные различия в производительности.
из Википедии:
Memoization
в вычислениях memoization-это метод оптимизации, используемый в первую очередь чтобы ускорить работу компьютерных программ с помощью вызовов функций, избегайте повторения расчет результатов для ранее обработанных входных данных.
Динамическое Программирование
в математике и информатике динамическое программирование является методом для решения сложных проблем разбивая их на более простые подзадачи.
разбивая задачу на более мелкие/простые подзадачи, мы часто сталкиваемся с одной и той же подзадачей более одного раза - поэтому мы используем Memoization для сохранения результатов предыдущих вычислений, поэтому нам не нужно их повторять.
динамическое программирование часто сталкивается с ситуациями, когда имеет смысл использовать memoization, но вы можете использовать любой метод, не обязательно используя другой.
Как Memoization, так и динамическое программирование решают отдельные подзадачи только один раз.
Memoization использует рекурсию и работает сверху вниз, в то время как динамическое программирование движется в противоположном направлении, решая проблему снизу вверх.
Ниже приводится интересная аналогия -
сверху вниз - сначала вы говорите, что я возьму на себя мир. Как ты это сделаешь? Вы говорите, что я первым возьму Азию. Как ты это сделаешь? Сначала я возьму на себя Индию. Я буду стал главным министром Дели, и т. д. так далее.
снизу-вверх - вы говорите, что я стану см Дели. Затем захватит Индию, затем все другие страны Азии и, наконец, я возьму на себя весь мир.
Comments