Подход вниз-вверх (к динамическому программированию) заключается в том, что сначала рассматриваются "меньшие" подпроблемы, а затем решаются большие подпроблемы, используя решение меньших проблем.
Подход вверх-вниз заключается в том, чтобы решить задачу "естественным образом" и проверить, вычислили ли вы решение подпроблемы раньше.
Я немного запутался. В чем разница между этими двумя способами?
rev4: Очень красноречивый комментарий пользователя Sammaron отметил, что, возможно, этот ответ ранее путал "сверху вниз" и "снизу вверх". Хотя изначально в этом ответе (rev3) и других ответах говорилось, что "снизу вверх - это запоминание" ("предположить подзадачи"), это может быть инверсия (т.е. "сверху вниз" может быть "предположить подзадачи", а "снизу вверх" может быть "составить подзадачи"). Раньше я читал о том, что запоминание - это другой вид динамического программирования, а не подтип динамического. Я цитировал эту точку зрения, несмотря на то, что не подписался на нее. Я переписал этот ответ, чтобы быть агностичным по отношению к терминологии до тех пор, пока в литературе не будут найдены соответствующие ссылки. Я также переписал этот ответ в вики-сообщество. Пожалуйста, отдавайте предпочтение академическим источникам. Список ссылок: {Веб: 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
(В некоторых других редких случаях это дерево может быть бесконечным в некоторых ветвях, представляя собой бесконечность, и, таким образом, дно дерева может быть бесконечно большим. Более того, в некоторых проблемах вы можете не знать, как выглядит полное дерево раньше времени. Таким образом, вам может понадобиться стратегия/алгоритм, чтобы решить, какие подпроблемы выявить).
Существует как минимум два основных метода динамического программирования, которые не являются взаимоисключающими:
Заучивание - это подход, основанный на принципе "laissez-faire": Вы предполагаете, что уже вычислили все подзадачи и не имеете представления об оптимальном порядке оценки. Обычно вы выполняете рекурсивный вызов (или какой-нибудь итерационный эквивалент) от корня и либо надеетесь, что приблизитесь к оптимальному порядку оценки, либо получаете доказательство того, что вы поможете достичь оптимального порядка оценки. Вы убедитесь, что рекурсивный вызов никогда не пересчитывает подзадачи, потому что вы кэшируете результаты, и, таким образом, дублирующие поддеревья не пересчитываются.
example: Если вы вычисляете последовательность Фибоначчи fib(100)
, то вы просто вызываете ее, и она вызывает fib(100)=fib(99)+fib(98)
, которая вызывает fib(99)=fib(98)+fib(97)
, ....и т.д....., которая вызывает fib(2)=fib(1)+fib(0)=1+0=1
. Тогда в конце концов fib(3)=fib(2)+fib(1)
, но ему не нужно перечислять fib(2)
, потому что мы кэшировали его.
Это начинается с вершины дерева и вычисляет подзадачи от листьев/поддеревеньев обратно к корню.
Табуляция - Можно также подумать о динамическом программировании как об алгоритме "заполнения таблицы" (хотя обычно эта "таблица" многомерна, в очень редких случаях* она может иметь неевклидовую геометрию). Это похоже на запоминание, но более активно и предполагает один дополнительный шаг: Вы должны заранее выбрать точный порядок, в котором будут выполняться вычисления. Это не должно означать, что порядок должен быть статическим, но что у вас гораздо больше гибкости, чем запоминание.
пример: Если вы выполняете Фибоначчи, вы можете выбрать для вычисления числа в этом порядке: fib(2)
,fib(3)
,fib(4)
... кэшировать каждое значение, чтобы Вам было легче вычислять следующие. Вы также можете думать об этом, как о заполнении таблицы (другая форма кэширования).
Лично я нечасто слышу слово "табуляция", но это очень приличный термин. Некоторые считают это "динамическим программированием".
Прежде чем запустить алгоритм, программист рассматривает целое дерево, затем пишет алгоритм оценки подпроблем в определенном порядке по направлению к корню, обычно заполняя таблицу.
*примечание: Иногда "таблица" не является прямоугольной таблицей со связью, подобной сетке, как таковой. Скорее, она может иметь более сложную структуру, например, дерево, или структуру, специфичную для проблемной области (например, города в пределах расстояния полета на карте), или даже шпалерную диаграмму, которая, хотя и похожа на решетку, но не имеет структуры связи вверх-вниз-лево-право и т.д. Например, user3290797 связал динамический пример программирования нахождения максимального независимого множества в дереве, что соответствует заполнению пробелов в дереве.
(На самом общем, в парадигме "динамического программирования" я бы сказал, что программист рассматривает целое дерево, тогда пишет алгоритм, реализующий стратегию оценки подпроблем, которая может оптимизировать любые свойства (обычно это комбинация временнóй сложности и пространственно-сложности). Ваша стратегия должна начинаться где-то, с какой-то конкретной подзадачи, и, возможно, может адаптироваться по результатам этих оценок. В общем смысле "динамического программирования", Вы можете попытаться кэшировать эти подзадачи, а в более общем смысле, попытаться избежать повторного рассмотрения подзадач с тонким разграничением, возможно, в случае графов в различных структурах данных. Очень часто эти структуры данных лежат в основе, как массивы или таблицы. Решения подпроблем можно выбросить, если они нам больше не нужны)).
[Ранее в этом ответе говорилось о терминологии "сверху вниз" по сравнению с терминологией "снизу вверх"; очевидно, что существует два основных подхода, называемых "запоминание" и "табуляция", которые могут биться с этими терминами (хотя и не полностью). Общим термином, используемым большинством людей, по-прежнему является "Динамическое программирование", а некоторые говорят "заучивание" для обозначения этого конкретного подтипа "Динамическое программирование". Этот ответ отказывается говорить, что "сверху вниз" и "снизу вверх" до тех пор, пока сообщество не найдет подходящие ссылки в научных работах. В конечном счете, важно понимать различие, а не терминологию].
Запись очень проста в программировании (обычно* можно написать аннотацию "memoizer" или функцию обертки, которая автоматически сделает это за вас), и должна быть вашей первой линией подхода. Недостатком табуляции является то, что вы должны придумать заказ.
*(на самом деле это просто, если вы пишете функцию сами, и/или кодируете на нечистом/нефункциональном языке программирования... например, если кто-то уже написал прекомпилированную функцию fib
, то она обязательно делает рекурсивные вызовы самой себе, и вы не можете волшебным образом запомнить функцию, не убедившись, что эти рекурсивные вызовы вызовут вашу новую функцию memoized (а не оригинальную безмятежную функцию)).
Обратите внимание, что как сверху вниз, так и снизу вверх может быть реализовано с помощью рекурсивного или итеративного заполнения таблиц, хотя это может быть неестественно.
С помощью запоминания, если дерево очень глубокое (например, fib(10^6)
), у вас закончится пространство стека, потому что каждое задержанное вычисление должно быть помещено на стек, и у вас будет 10^6 из них.
Любой из подходов может оказаться неоптимальным по времени, если порядок, в котором вы посещаете (или пытаетесь посетить) подзадачи, не является оптимальным, особенно, если есть более одного способа вычислить подзадачи (обычно кэширование решило бы эту проблему, но теоретически возможно, что в некоторых экзотических случаях кэширование может и не быть оптимальным). Пометка обычно добавляет к пространству сложности (например, при использовании табуляции у вас больше свободы выброса вычислений, как использование табуляции с помощью Fib позволяет использовать пространство O(1), но пометка с помощью Fib использует пространство стека O(N)).
Если вы также занимаетесь чрезвычайно сложными проблемами, у вас может не быть другого выбора, кроме как делать табуляцию (или, по крайней мере, играть более активную роль в управлении запоминанием там, где вы хотите, чтобы оно проходило). Также, если вы находитесь в ситуации, когда оптимизация является абсолютно критичной и вы должны оптимизировать, табуляция позволит вам сделать оптимизации, которые в противном случае не позволили бы вам сделать в здравом уме. По моему скромному мнению, в обычной программной инженерии ни один из этих двух случаев никогда не возникает, поэтому я бы просто использовал запоминание ("функция, которая кэширует свои ответы"), если только что-то (например, пространство стека) не делает табуляцию необходимой.... хотя технически, чтобы избежать пробоя стека, можно 1) увеличить лимит размера стека в языках, которые это позволяют, или 2) съесть постоянный фактор дополнительной работы по виртуализации стека (ick), или 3) программу в стиле continue-passing, которая, по сути, также виртуализирует ваш стек (не уверен в сложности этого, но, в принципе, вы фактически возьмете цепочку отложенных вызовов из стека размера N и де-факто засунете ее в N последовательно вложенных функций thunk... хотя в некоторых языках без оптимизации хвостового вызова вам, возможно, придется батутировать вещи, чтобы избежать пробоя стека).
Здесь мы приводим примеры, представляющие особый интерес, которые не только являются общими проблемами 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)
Я лично считаю мемоизация гораздо более естественным. Вы можете воспользоваться рекурсивной функции и метод его механическим способом (первый поиск ответа в кэш и вернуть его, если возможно, в противном случае вычислить рекурсивно, а затем, прежде чем вернуться, нужно сохранить расчет в кэше для дальнейшего использования), а делать снизу вверх динамического программирования требует кодирование последовательности, в которой решения вычисляются таким образом, что нет "большая проблема" и вычисляется прежде чем меньшие проблемы, от которого он зависит.
Ключевой особенностью динамического программирования является наличие перекрывающиеся подзадачи. То есть, проблема, которую вы пытаетесь решить можно разбить на подзадачи, и многие из этих подзадач поделиться subsubproblems. Это похоже на "разделяй и властвуй", но вы в конечном итоге делает то же самое много, много раз. Пример, который я использовал с 2003 года при обучении или объяснении этих вопросов: вы можете вычислить Фибоначчи рекурсивно.
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
Используйте ваш любимый язык и попробовать запустить его на Фибо(50). Это займет очень, очень долго. Примерно столько же времени, как Фибо(50)
сама! Однако, много ненужной работы делается. приврали(50)
позвонит приврали(49)
и приврали(48), но тогда оба будут в конечном итоге звоню привирать(47)
, хотя значение одно и то же. В самом деле, приврали(47)
будет вычисляться три раза: по прямой связи с привирать(49), по прямой связи из
приврали(48), а также путем прямого вызова из другой приврали(48)
, который был порожден расчет приврали(49)
... Итак, вы видите, у нас есть перекрывающиеся подзадачи.
Хорошая новость: нет необходимости, чтобы вычислить то же значение много раз. После того как вы вычислить его один раз, кэшировать результаты, и в следующий раз использовать кэшированное значение! В этом и заключается суть динамического программирования. Вы можете называть ее "сверху вниз" и "Ну мемоизация-то", или то, что вы хотите. Этот подход очень понятный и очень легко реализовать. Просто напишите рекурсивное решение, во-первых, проверить его на небольшие тесты, добавить мемоизация (кэширование уже вычисленных значений), и --- бинго! --- вы сделали.
Как правило, вы также можете написать эквивалент итерационная программа, которая работает снизу вверх, без рекурсии. В этом случае это будет более естественный подход: цикл от 1 до 50 вычисления чисел Фибоначчи, как вы идете.
fib[0] = 0
fib[1] = 1
for i in range(48):
fib[i+2] = fib[i] + fib[i+1]
В какие-нибудь интересные сценарии снизу-вверх обычно более трудно понять. Однако, как только вы понимаете это, как правило, вы'д получите более ясную картину того, как алгоритм работает. На практике, при решении нетривиальных задач, я рекомендую сначала писать сверху вниз и протестировать его на небольших примерах. Потом писать снизу-вверх и сравнить два, чтобы убедиться, что вы получаете то же самое. В идеале, автоматически сравнить два решения. Написать небольшую процедуру, которая будет генерировать множество тестов, в идеале -- все небольшие тесты до определенного размера --- и проверить, что оба решения дают одинаковый результат. После этого снизу доверху решения в производстве, но держать верх-низ кода закомментирован. Это позволит сделать его проще для других разработчиков, чтобы понять, что это такое, что вы делаете: снизу-вверх код может быть совершенно непонятной, даже вы это написали и даже если вы точно знаете, что вы делаете.
Во многих областях применения подхода "снизу вверх" немного быстрее, из-за накладных расходов на рекурсивные вызовы. Переполнение стека также может быть проблемой в некоторых проблем, и отмечают, что это может очень сильно зависеть от входных данных. В некоторых случаях вы не сможете написать тест вызывает переполнение стека, если вы Don'т понять динамического программирования достаточно хорошо, но однажды это может случиться.
Сейчас существуют проблемы, где подход "сверху вниз" является единственным возможным решением, потому что проблему пространства настолько велик, что невозможно решить все подзадачи. Однако, в "кэширование" по-прежнему работает в разумные сроки, потому что ваш вклад должен только часть подзадач, которые нужно решить --- но это слишком сложно, чтобы однозначно определить, что подзадачи необходимо решить, а следовательно, и писать снизу-вверх. С другой стороны, бывают ситуации, когда вы знаете, что вам понадобится, чтобы решить все подзадачи. В этом случае пойти дальше и использовать снизу вверх.
Я бы лично использую верх-низ для пункт оптимизации.к.а слово обернуть оптимизации проблема (Смотреть до кнута-Пласс разрыв строки алгоритмов; как минимум Tex использует его, и некоторое программное обеспечение компании Adobe Systems применяет аналогичный подход). Я бы использовал "снизу-вверх" для быстрого преобразования Фурье]3.
Рассмотрим ряд Фибоначчи в качестве примера
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-го числа. Этот метод на самом деле называется "снизу вверх" методов.
Последние два, алгоритмы полного заполнения требования динамического программирования. Но один сверху и другой снизу вверх. Оба алгоритма имеют аналогичные помещения и сложности времени.
Динамическое программирование часто называют мемоизация!
1.Мемоизация-это нисходящий метод(начать решать данную проблему, разбив ее) и динамическое программирование снизу-вверх метод(начало решения от тривиальных суб-проблема, к данной проблеме)
2.ДП находит решение, начиная от базового варианта(ов) и работает свой путь вверх. ДП решает все проблемы, потому что он делает это снизу вверх
в отличие от мемоизации, который решает только нужны подпроблемы
ДП имеет потенциал для преобразования экспоненциальное время перебором решений полиномиальных алгоритмов.
ДП может быть гораздо более эффективным, потому что его итерационный
наоборот, мемоизация должны оплатить (часто значительные) издержки из-за рекурсии.
Чтобы быть более простым, мемоизация использует подход "сверху вниз", чтобы решить проблему, т. е. начать с основной(главной) проблемы, затем разбивает ее на подзадачи и решить эти проблемы так же. В этом подходе же проблема может возникать несколько раз и потреблять больше циклов процессора, следовательно, увеличить сложность времени. В то время как в динамическом программировании же суб-проблема не будет решена несколько раз, но до результата будут использоваться для оптимизации решения.
Проще говоря, сверху вниз подход использует рекурсию для вызова подпроблемы снова и снова <БР> где, как подход "снизу вверх" используют один, не призывая ни кого и поэтому является более эффективным.
Ниже приводится ДП решение для редактирования расстояние проблеме, которая есть сверху вниз. Я надеюсь, это также поможет в понимании мира динамического программирования:
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];
}
Вы можете думать о своей рекурсивной реализации в вашем доме. Это'ы довольно хорошо и интересно, если вы еще'т решать что-то подобное.