Подход снизу вверх (к динамическому программированию) состоит в том, чтобы сначала рассмотреть «меньшие» подзадачи, а затем решить более крупные подзадачи, используя решение меньших проблем.
Нисходящий заключается в решении проблемы «естественным образом» и проверке, рассчитывали ли вы решение подзадачи ранее.
Я немного запутался. В чем разница между этими двумя?
rev4: Очень красноречивый комментарий пользователя Sammaron отметил, что, возможно, в этом ответе ранее путались нисходящие и восходящие. Хотя первоначально в этом ответе (rev3) и в других ответах говорилось, что «снизу вверх - это мемоизация» («предполагать подзадачи»), это может быть обратное (то есть «сверху вниз» может быть «предполагать подзадачи» и « снизу вверх "может быть" составить подзадачи "). Раньше я читал о мемоизации как о другом виде динамического программирования в отличие от подтипа динамического программирования. Я цитировал эту точку зрения, хотя и не подписывался под ней. Я переписал этот ответ, чтобы не зависеть от терминологии, пока в литературе не будут найдены соответствующие ссылки. Я также преобразовал этот ответ в вики сообщества. Пожалуйста, отдайте предпочтение академическим источникам. Список ссылок: {Web: 1, 2} {Литература: 5}
Суть динамического программирования заключается в упорядочивании вычислений таким образом, чтобы избежать повторного вычисления дублирующей работы. У вас есть основная проблема (корень вашего дерева подзадач) и подзадачи (поддеревья). Подзадачи обычно повторяются и перекрываются.
Например, рассмотрим ваш любимый пример Фибонначи. Это полное дерево подзадач, если мы сделали наивный рекурсивный вызов:
TOP of the tree
fib(4)
fib(3)...................... + fib(2)
fib(2)......... + fib(1) fib(1)........... + fib(0)
fib(1) + fib(0) fib(1) fib(1) fib(0)
fib(1) fib(0)
BOTTOM of the tree
(В некоторых других редких задачах это дерево может быть бесконечным в некоторых ветвях, представляя незавершенность, и, таким образом, нижняя часть дерева может быть бесконечно большой. Кроме того, в некоторых задачах вы можете не знать, как выглядит полное дерево перед времени. Таким образом, вам может потребоваться стратегия / алгоритм, чтобы решить, какие подзадачи выявить.)
Существует как минимум два основных метода динамического программирования, которые не исключают друг друга:
Мемоизация - это подход невмешательства: вы предполагаете, что уже вычислили все подзадачи и что вы не знаете, каков оптимальный порядок оценки. Как правило, вы выполняете рекурсивный вызов (или некоторый итерационный эквивалент) из корня и либо надеетесь, что приблизитесь к оптимальному порядку оценки, либо получите доказательство того, что вы поможете вам достичь оптимального порядка оценки. Вы можете гарантировать, что рекурсивный вызов никогда не будет повторно вычислять подзадачу, потому что вы кешируете результаты, и, таким образом, повторяющиеся поддеревья не пересчитываются.
fib(100), you would just call this, and it would call fib(100)=fib(99)+fib(98), which would call fib(99)=fib(98)+fib(97), ...etc..., which would call fib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolve fib(3)=fib(2)+fib(1), but it doesn't need to recalculate fib(2), because we cached it.Табулирование - вы также можете думать о динамическом программировании как об алгоритме «заполнения таблицы» (хотя обычно эта «таблица» многомерна, в очень редких случаях эта «таблица» может иметь неевклидову геометрию *). Это похоже на мемоизацию, но более активную и включает в себя один дополнительный шаг: вы должны заранее выбрать точный порядок, в котором вы будете выполнять свои вычисления. Это не должно означать, что порядок должен быть статическим, но у вас гораздо больше гибкости, чем у мемоизации.
fib(2),fib(3),fib(4)... caching every value so you can compute the next ones more easily. You can also think of it as filling up a table (another form of caching).(В самом общем случае, в парадигме «динамического программирования», я бы сказал, что программист рассматривает все дерево целиком, затем пишет алгоритм, реализующий стратегию оценки подзадач, которая может оптимизировать любые свойства, которые вы хотите ( обычно сочетание временной сложности и пространственной сложности). Ваша стратегия должна где-то начинаться с какой-то конкретной подзадачи и, возможно, может адаптироваться на основе результатов этих оценок. В общем смысле "динамического программирования" вы можете попробовать чтобы кэшировать эти подзадачи и, в более общем плане, старайтесь избегать повторения подзадач с тонкими различиями, возможно, в случае графов в различных структурах данных. Очень часто эти структуры данных лежат в основе своей, как массивы или таблицы. Решения подзадач можно выбросить. если они нам больше не нужны.)
[Ранее в этом ответе говорилось о нисходящей и восходящей терминологии; очевидно, что существует два основных подхода, называемых мемоизацией и табулированием, которые могут противоречить этим терминам (хотя и не полностью). Общий термин, который большинство людей использует по-прежнему, - «динамическое программирование», а некоторые люди говорят «мемоизация», имея в виду этот конкретный подтип «динамического программирования». В этом ответе не говорится, какой из них идет сверху вниз или снизу вверх, до тех пор, пока сообщество не найдет подходящие ссылки в научных статьях. В конце концов, важно понимать различие, а не терминологию.]
Мемоизацию очень легко кодировать (обычно вы * можете написать аннотацию или функцию-оболочку «мемоизатора», которая автоматически сделает это за вас), и она должна быть вашим первым подходом. Обратной стороной табуляции является то, что вам нужно придумать порядок.
* (на самом деле это просто, если вы сами пишете функцию и / или кодируете на нечистом / нефункциональном языке программирования ... например, если кто-то уже написал предварительно скомпилированную fib функцию, он обязательно выполняет рекурсивные вызовы к себе, и вы не можете волшебным образом запоминать функцию без обеспечения того, чтобы эти рекурсивные вызовы вызывали вашу новую запомненную функцию (а не исходную немомизированную функцию))
Обратите внимание, что как сверху вниз, так и снизу вверх можно реализовать рекурсию или итеративное заполнение таблицы, хотя это может быть неестественным.
С мемоизацией, если дерево очень глубокое (например, fib(10^6)), у вас закончится пространство стека, потому что каждое отложенное вычисление должно быть помещено в стек, и у вас будет 10 ^ 6 из них.
Любой из подходов может быть неоптимальным по времени, если порядок, в котором вы происходите (или пытаетесь) посещать подзадачи, не является оптимальным, в частности, если существует более одного способа вычисления подзадачи (обычно кэширование решает эту проблему, но теоретически возможно, что кеширование может не в каких-то экзотических случаях). Мемоизация обычно добавляет вашу временную сложность к вашей пространственной сложности (например, с табуляцией у вас больше свободы отбрасывать вычисления, например, использование табуляции с Fib позволяет вам использовать пространство O (1), но мемоизация с Fib использует O (N) пространство стека).
Если вы также решаете чрезвычайно сложные задачи, у вас может не быть другого выбора, кроме как делать табуляции (или, по крайней мере, играть более активную роль в управлении мемоизацией, куда вы хотите). Кроме того, если вы находитесь в ситуации, когда оптимизация абсолютно критична и вы должны оптимизировать, табуляция позволит вам выполнить оптимизацию, которую мемоизация в противном случае не позволила бы вам сделать разумным способом. По моему скромному мнению, в обычной разработке программного обеспечения ни один из этих двух случаев никогда не возникает, поэтому я бы просто использовал мемоизацию («функцию, которая кэширует свои ответы»), если что-то (например, пространство стека) не делает табуляцию необходимой ... хотя технически, чтобы избежать выброса стека, вы можете 1) увеличить предел размера стека на языках, которые это позволяют, или 2) съесть постоянный фактор дополнительной работы для виртуализации вашего стека (ick), или 3) программу в стиле с продолжением передачи, что по сути, также виртуализирует ваш стек (не уверен в сложности этого, но в основном вы эффективно берете цепочку отложенных вызовов из стека размера N и де-факто вставляете ее в N последовательно вложенных функций преобразователя ... хотя на некоторых языках без оптимизация хвостового вызова, вам, возможно, придется прыгать с трамплина, чтобы избежать выброса стека).
Здесь мы перечисляем примеры, представляющие особый интерес, которые не являются просто общими проблемами DP, но интересно различают мемоизацию и табуляцию. Например, одна формулировка может быть намного проще, чем другая, или может быть оптимизация, которая в основном требует табуляции:
python memoization decorator; некоторые языки позволяют писать макрос или код, инкапсулирующий шаблон мемоизации. Шаблон мемоизации - это не что иное, как вызов функции, поиск значения из кеша (если значение отсутствует, вычислите его и сначала добавьте в кеш).
- person ninjagecko; 12.12.2012
fib, но ИМО, это больше не DP, поскольку вы просто повторяете свое решение.)
- person mgiuffrida; 03.12.2015
fib(513). Мне кажется, здесь мешает перегруженная терминология. 1) Вы всегда можете выбросить ненужные подзадачи. 2) Вы всегда можете избежать подсчета ненужных вам подзадач. 3) 1 и 2 может быть намного сложнее закодировать без явной структуры данных для хранения подзадач, ИЛИ, сложнее, если поток управления должен переплетаться между вызовами функций (вам может потребоваться состояние или продолжения).
- person ninjagecko; 03.12.2015
DP сверху вниз и снизу вверх - это два разных способа решения одних и тех же проблем. Рассмотрим мемоизированное (сверху вниз) и динамическое (снизу вверх) программное решение для вычисления чисел Фибоначчи.
fib_cache = {}
def memo_fib(n):
global fib_cache
if n == 0 or n == 1:
return 1
if n in fib_cache:
return fib_cache[n]
ret = memo_fib(n - 1) + memo_fib(n - 2)
fib_cache[n] = ret
return ret
def dp_fib(n):
partial_answers = [1, 1]
while len(partial_answers) <= n:
partial_answers.append(partial_answers[-1] + partial_answers[-2])
return partial_answers[n]
print memo_fib(5), dp_fib(5)
Лично я считаю, что мемоизация более естественна. Вы можете взять рекурсивную функцию и запоминать ее с помощью механического процесса (сначала ищите ответ в кеше и возвращайте его, если возможно, в противном случае вычисляйте его рекурсивно, а затем перед возвратом вы сохраняете вычисление в кеше для будущего использования), тогда как выполнение снизу вверх динамическое программирование требует, чтобы вы закодировали порядок, в котором вычисляются решения, так, чтобы никакая «большая проблема» не вычислялась раньше меньшей проблемы, от которой она зависит.
fib_cache значениями для 0 и 1 не более естественно, чем добавление кода со специальным регистром?
- person Deduplicator; 25.02.2021
Возьмем для примера ряд Фибоначчи.
1,1,2,3,5,8,13,21....
first number: 1
Second number: 1
Third Number: 2
Другими словами,
Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21
В случае первых пяти чисел Фибоначчи
Bottom(first) number :1
Top (fifth) number: 5
Теперь давайте посмотрим на рекурсивный алгоритм ряда Фибоначчи в качестве примера.
public int rcursive(int n) {
if ((n == 1) || (n == 2)) {
return 1;
} else {
return rcursive(n - 1) + rcursive(n - 2);
}
}
Теперь, если мы выполним эту программу со следующими командами
rcursive(5);
Если мы внимательно посмотрим на алгоритм, чтобы сгенерировать пятое число, ему требуются 3-е и 4-е числа. Итак, моя рекурсия фактически начинается сверху (5), а затем доходит до нижних / нижних чисел. Этот подход на самом деле является подходом сверху вниз.
Чтобы не выполнять одни и те же вычисления несколько раз, мы используем методы динамического программирования. Мы сохраняем ранее вычисленное значение и повторно используем его. Этот прием называется мемоизацией. К динамическому программированию относятся не только мемоизация, но и не требуется для обсуждения текущей проблемы.
Сверху вниз
Давайте перепишем наш оригинальный алгоритм и добавим мемоизированные техники.
public int memoized(int n, int[] memo) {
if (n <= 2) {
return 1;
} else if (memo[n] != -1) {
return memo[n];
} else {
memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
}
return memo[n];
}
И мы выполняем этот метод следующим образом
int n = 5;
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
memoized(n, memo);
Это решение по-прежнему нисходящее, поскольку алгоритм начинается с верхнего значения и идет вниз на каждом шаге, чтобы получить наше верхнее значение.
Снизу вверх
Но вопрос в том, можем ли мы начать снизу, например, с первого числа Фибоначчи, а затем пройти путь вверх. Давайте перепишем его, используя эту технику,
public int dp(int n) {
int[] output = new int[n + 1];
output[1] = 1;
output[2] = 1;
for (int i = 3; i <= n; i++) {
output[i] = output[i - 1] + output[i - 2];
}
return output[n];
}
Теперь, если мы посмотрим на этот алгоритм, он фактически начнет с более низких значений, а затем перейдет к началу. Если мне нужно 5-е число Фибоначчи, я фактически вычисляю 1-е, затем второе, затем третье до 5-го числа. Эти приемы на самом деле называются методами «снизу вверх».
Последние два, алгоритмы полностью удовлетворяют требованиям динамического программирования. Но один идет сверху вниз, а другой снизу вверх. Оба алгоритма имеют одинаковую пространственную и временную сложность.
Ключевой особенностью динамического программирования является наличие перекрывающихся подзадач. То есть проблему, которую вы пытаетесь решить, можно разбить на подзадачи, и многие из этих подзадач имеют общие подзадачи. Это похоже на «Разделяй и властвуй», но в конечном итоге вы делаете одно и то же много-много раз. Пример, который я использовал с 2003 года при обучении или объяснении этих вопросов: вы можете вычислить числа Фибоначчи рекурсивно. .
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
Используйте свой любимый язык и попробуйте запустить его для fib(50). Это займет очень и очень много времени. Примерно столько же времени, сколько и сам fib(50)! Однако делается много ненужной работы. fib(50) вызовет fib(49) и fib(48), но затем оба они вызовут fib(47), даже если значение одно и то же. Фактически, fib(47) будет вычисляться три раза: прямым вызовом из fib(49), прямым вызовом из fib(48), а также прямым вызовом из другого fib(48), того, который был порожден вычислением _12 _... Итак, вы видите , у нас есть перекрывающиеся подзадачи.
Отличные новости: нет необходимости вычислять одно и то же значение много раз. После того, как вы вычислите его один раз, кешируйте результат, а в следующий раз используйте кешированное значение! В этом суть динамического программирования. Вы можете называть это «сверху вниз», «мемоизацией» или как угодно еще. Этот подход очень интуитивно понятен и очень прост в реализации. Просто сначала напишите рекурсивное решение, протестируйте его на небольших тестах, добавьте мемоизацию (кеширование уже вычисленных значений) и --- бинго! --- вы сделали.
Обычно вы также можете написать эквивалентную итеративную программу, которая работает снизу вверх, без рекурсии. В этом случае это был бы более естественный подход: цикл от 1 до 50, вычисляя все числа Фибоначчи по ходу дела.
fib[0] = 0
fib[1] = 1
for i in range(48):
fib[i+2] = fib[i] + fib[i+1]
В любом интересном сценарии решение снизу вверх обычно труднее понять. Однако, как только вы это поймете, обычно вы получите гораздо более четкую общую картину того, как работает алгоритм. На практике при решении нетривиальных задач я рекомендую сначала написать нисходящий подход и протестировать его на небольших примерах. Затем напишите восходящее решение и сравните два, чтобы убедиться, что вы получаете то же самое. В идеале сравнивайте два решения автоматически. Напишите небольшую процедуру, которая генерирует множество тестов, в идеале - все небольшие тесты до определенного размера - и проверяет, что оба решения дают одинаковый результат. После этого используйте восходящее решение в производстве, но оставьте верхний нижний код закомментированным. Это поможет другим разработчикам понять, что вы делаете: восходящий код может быть совершенно непонятным, даже если вы его написали и даже если вы точно знаете, что делаете.
Во многих приложениях восходящий подход немного быстрее из-за накладных расходов на рекурсивные вызовы. Переполнение стека также может быть проблемой при определенных проблемах, и обратите внимание, что это может очень сильно зависеть от входных данных. В некоторых случаях вы не сможете написать тест, вызывающий переполнение стека, если вы недостаточно хорошо разбираетесь в динамическом программировании, но когда-нибудь это все равно может произойти.
Теперь есть проблемы, для которых подход сверху вниз является единственным возможным решением, потому что проблемное пространство настолько велико, что невозможно решить все подзадачи. Однако «кеширование» по-прежнему работает в разумные сроки, потому что ваш ввод требует решения только части подзадач - но слишком сложно явно определить, какие подзадачи вам нужно решить, и, следовательно, написать нижний вверх решение. С другой стороны, бывают ситуации, когда вы знаете, что вам нужно будет решить все подзадачи. В этом случае продолжайте и используйте восходящее движение.
Я бы лично использовал верхний нижний для оптимизации абзаца, также известной как проблема оптимизации переноса слов (найдите Knuth -Алгоритмы разделения строк в классах; по крайней мере, TeX использует его, а в некотором программном обеспечении Adobe Systems используется аналогичный подход). Я бы использовал восходящее движение для быстрого преобразования Фурье.
Динамическое программирование часто называют мемоизацией!
1. Мемоизация - это метод сверху вниз (начните решать данную проблему с ее разбиения), а динамическое программирование - это метод снизу вверх (начните решение от тривиальной подзадачи вверх к данной проблеме).
2. DP находит решение, начиная с базового (-ых) случая (-ов), и продвигается вверх. DP решает все подзадачи, потому что делает это снизу вверх
В отличие от мемоизации, которая решает только необходимые подзадачи.
DP может преобразовать решения методом перебора с экспоненциальным временем в алгоритмы с полиномиальным временем.
DP может быть намного более эффективным, потому что его итеративная
Напротив, мемоизация должна оплачивать (часто значительные) накладные расходы из-за рекурсии.
Чтобы быть более простым, Memoization использует нисходящий подход для решения проблемы, то есть он начинается с основной (основной) проблемы, затем разбивает ее на подзадачи и решает эти подзадачи аналогичным образом. При таком подходе одна и та же подзадача может возникать несколько раз и потреблять больше цикла ЦП, что увеличивает временную сложность. В то время как в динамическом программировании одна и та же подзадача не будет решаться несколько раз, но предыдущий результат будет использоваться для оптимизации решения.
Проще говоря, подход «сверху вниз» использует рекурсию для вызова проблем Sub снова и снова,
где при подходе снизу вверх использовать сингл, не вызывая ни одного, и, следовательно, он более эффективен.
Проблемы динамического программирования можно решать, используя подходы снизу вверх или сверху вниз.
Как правило, восходящий подход использует метод табуляции, тогда как нисходящий подход использует метод рекурсии (с запоминанием).
Но вы также можете использовать подходы снизу вверх и сверху вниз с использованием рекурсии, как показано ниже.
Снизу вверх: начните с базового условия и рекурсивно передайте вычисленное до настоящего момента значение. Как правило, это хвостовые рекурсии.
int n = 5;
fibBottomUp(1, 1, 2, n);
private int fibBottomUp(int i, int j, int count, int n) {
if (count > n) return 1;
if (count == n) return i + j;
return fibBottomUp(j, i + j, count + 1, n);
}
Сверху вниз: начните с последнего условия и рекурсивно получите результат его подзадач.
int n = 5;
fibTopDown(n);
private int fibTopDown(int n) {
if (n <= 1) return 1;
return fibTopDown(n - 1) + fibTopDown(n - 2);
}
Ниже приведено решение на основе DP для задачи редактирования расстояния, расположенное сверху вниз. Я надеюсь, что это также поможет в понимании мира динамического программирования:
public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
int m = word2.length();
int n = word1.length();
if(m == 0) // Cannot miss the corner cases !
return n;
if(n == 0)
return m;
int[][] DP = new int[n + 1][m + 1];
for(int j =1 ; j <= m; j++) {
DP[0][j] = j;
}
for(int i =1 ; i <= n; i++) {
DP[i][0] = i;
}
for(int i =1 ; i <= n; i++) {
for(int j =1 ; j <= m; j++) {
if(word1.charAt(i - 1) == word2.charAt(j - 1))
DP[i][j] = DP[i-1][j-1];
else
DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
}
}
return DP[n][m];
}
Вы можете подумать о его рекурсивной реализации у себя дома. Это неплохо и сложно, если вы раньше не решали что-то подобное.
