Восходящий подход (к динамическому программированию) состоит в том, чтобы сначала взглянуть на "меньшие" подзадачи, а затем решить более крупные подзадачи, используя решение меньших проблем.
Нисходящий процесс состоит в том, чтобы решить проблему "естественным образом" и проверить, рассчитали ли вы решение подзадачи ранее.
Я немного запутался. В чем разница между этими двумя?
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: вы предполагаете, что вы уже вычислили все подзадачи и не знаете, каков оптимальный порядок оценки. Как правило, вы выполняете рекурсивный вызов (или некоторый итерационный эквивалент) из корня и либо надеетесь, что вы приблизитесь к оптимальному порядку оценки, либо получите доказательство того, что вы поможете достичь оптимального порядка оценки. Вы должны убедиться, что рекурсивный вызов никогда не пересчитывает подзадачу, потому что вы кэшируете результаты, и, таким образом, дублированные поддеревья не пересчитываются.
fib(100), вы бы просто назвали это, и это вызвало бы fib(100)=fib(99)+fib(98), что вызвало бы fib(99)=fib(98)+fib(97) ,... и т.д., 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)... кэшировать каждое значение, чтобы вам было легче вычислять следующие. Вы также можете думать об этом как о заполнении таблицы (еще одна форма кэширования).(В самом общем смысле, в парадигме "динамического программирования", я бы сказал, что программист рассматривает все дерево, а затем пишет алгоритм, который реализует стратегию для оценки подзадач, которая может оптимизировать любые свойства, которые вы хотите (обычно сочетание сложности времени). и сложность пространства.) Ваша стратегия должна начинаться где-то с некоторой конкретной подзадачи и, возможно, может адаптироваться на основе результатов этих оценок. В общем смысле "динамического программирования" вы можете попытаться кэшировать эти подзадачи и многое другое. как правило, старайтесь не пересматривать подзадачи с тонким отличием, возможно, в случае графов в различных структурах данных. Очень часто эти структуры данных по своей сути похожи на массивы или таблицы. Решения подзадач могут быть выброшены, если они нам не нужны больше.)
[Ранее этот ответ сделал выражение о терминологии "сверху вниз" и "снизу вверх"; ясно, что есть два основных подхода, называемых Мемоизация и табуляция, которые могут быть в биографии с этими терминами (хотя и не полностью). Общий термин, который используют большинство людей, - это "Динамическое программирование", а некоторые говорят "Мемоизация" для обозначения этого конкретного подтипа "Динамическое программирование". В этом ответе отказывается указывать, что является "сверху вниз" и "снизу вверх", пока сообщество не сможет найти надлежащие ссылки в научных статьях. В конечном счете, важно понимать различие, а не терминологию.]
Memoization очень легко закодировать (обычно вы можете * написать аннотацию "memoizer" или функцию-обертку, которая автоматически сделает это за вас), и она должна быть вашей первой линией подхода. Недостатком табуляции является то, что вы должны придумать порядок.
* (это на самом деле легко, только если вы пишете функцию самостоятельно и/или пишете на нечистом/нефункциональном языке программирования... например, если кто-то уже написал предварительно скомпилированную функцию fib, она обязательно делает рекурсивные вызовы сама себе, и вы не можете волшебным образом запоминать функцию, не гарантируя, что эти рекурсивные вызовы вызовут вашу новую запомненную функцию (а не оригинальную неметизированную функцию))
Обратите внимание, что как сверху вниз, так и снизу вверх могут быть реализованы с помощью рекурсии или итеративного заполнения таблиц, хотя это может быть не естественным.
В случае с мемоизацией, если дерево очень глубокое (например, fib(10^6)), вам не хватит места в стеке, потому что каждое отложенное вычисление должно быть помещено в стек, и у вас будет 10 ^ 6 из них.
Любой подход может не быть оптимальным по времени, если порядок, в котором вы выполняете (или пытаетесь) посещать подзадачи, не является оптимальным, в частности, если существует несколько способов вычисления подзадачи (обычно это разрешает кэширование, но теоретически возможно, что кэширование может не в некоторых экзотических случаях). Мемоизация, как правило, добавляет сложность времени к сложности пространства (например, при табулировании у вас больше свободы в отбрасывании вычислений, например, при использовании табуляции в Fib позволяет использовать пространство O (1), но при запоминании в Fib используется O (N). пространство стека).
Если вы также решаете чрезвычайно сложные проблемы, у вас может не быть иного выбора, кроме как выполнять табулирование (или, по крайней мере, играть более активную роль в управлении напоминанием, куда вы хотите его направить). Кроме того, если вы находитесь в ситуации, когда оптимизация абсолютно необходима, и вы должны оптимизировать, табулирование позволит вам выполнить оптимизацию, которую в противном случае запоминание не позволило бы вам сделать разумным способом. По моему скромному мнению, в обычной разработке программного обеспечения ни один из этих двух случаев никогда не встречался, поэтому я бы просто использовал памятку ("функция, которая кэширует свои ответы"), если что-то (например, пространство стека) не делает необходимым табулирование... хотя Технически, чтобы избежать выброса стека, вы можете: 1) увеличить предельный размер стека в языках, которые позволяют это, или 2) потреблять постоянный фактор дополнительной работы для виртуализации вашего стека (ick), или 3) программы в стиле передачи продолжения, который в действительности также виртуализирует ваш стек (не уверен, что это сложно, но в основном вы будете эффективно извлекать цепочку отложенных вызовов из стека размера N и фактически вставлять ее в N последовательных вложенных функций thunk... хотя в некоторых языках без Оптимизация хвостовых вызовов: вам может потребоваться батут, чтобы избежать выброса из стека).
Здесь мы перечислили примеры, представляющие особый интерес, которые представляют собой не только общие проблемы DP, но и интересно различают запоминание и табулирование. Например, одна формулировка может быть намного проще, чем другая, или может быть оптимизация, которая в основном требует табуляции:
Сверху вниз и снизу вверх 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)
Лично я нахожу запоминание намного более естественным. Вы можете взять рекурсивную функцию и запомнить ее с помощью механического процесса (сначала ищите ответ в кеше и возвращайте его, если это возможно, в противном случае вычисляйте его рекурсивно, а затем перед возвратом сохраняйте вычисление в кеше для будущего использования), в то время как выполняете восходящие Динамическое программирование требует, чтобы вы закодировали порядок, в котором рассчитываются решения, так что "большая проблема" не вычисляется перед меньшей проблемой, от которой она зависит.
Ключевой особенностью динамического программирования является наличие перекрывающихся подзадач. То есть проблема, которую вы пытаетесь решить, может быть разбита на подзадачи, и многие из этих подзадач имеют общие подзадачи. Это как "Разделить и победить", но вы делаете то же самое много, много раз. Пример, который я использовал с 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), который был вызван вычислением fib(49)... Итак, вы видите, что у нас есть перекрывающиеся подзадачи.
Отличные новости: нет необходимости вычислять одно и то же значение много раз. Как только вы его вычислите один раз, кешируйте результат, а в следующий раз используйте кешированное значение! В этом суть динамического программирования. Вы можете называть его "сверху вниз", "меморандум" или все, что хотите. Этот подход очень интуитивно понятен и очень прост в реализации. Сначала напишите рекурсивное решение, проверьте его на небольших тестах, добавьте memoization (кеширование уже вычисленных значений) и --- bingo! --- все готово.
Обычно вы также можете написать эквивалентную итеративную программу, которая работает снизу вверх, без рекурсии. В этом случае это будет более естественный подход: цикл от 1 до 50 вычисляет все числа Фибоначчи, когда вы идете.
fib[0] = 0
fib[1] = 1
for i in range(48):
fib[i+2] = fib[i] + fib[i+1]
В любом интересном сценарии восходящее решение обычно сложнее понять. Однако, как только вы это поймете, обычно вы получите гораздо более четкую картину того, как работает алгоритм. На практике при решении нетривиальных проблем я рекомендую сначала написать подход сверху вниз и проверить его на небольших примерах. Затем напишите восходящее решение и сравните два, чтобы убедиться, что вы получаете то же самое. В идеале, сравните два решения автоматически. Напишите небольшую процедуру, которая будет генерировать множество тестов, в идеале - все небольшие тесты до определенного размера --- и подтвердите, что оба решения дают одинаковый результат. После этого используйте восходящее решение в производстве, но сохраняйте код верхнего уровня, закомментированный. Это упростит другим разработчикам понять, что вы делаете: снизу-код может быть совершенно непонятным, даже если вы его написали, и даже если вы точно знаете, что вы делаете.
Во многих приложениях подход снизу вверх немного быстрее из-за накладных расходов на рекурсивные вызовы. Переполнение стека также может быть проблемой при определенных проблемах, и обратите внимание, что это может сильно зависеть от входных данных. В некоторых случаях вы не сможете написать тест, вызывающий переполнение стека, если вы не понимаете динамическое программирование достаточно хорошо, но в какой-то момент это может произойти.
Теперь возникают проблемы, когда подход сверху вниз является единственным возможным решением, поскольку проблемное пространство настолько велико, что невозможно решить все подзадачи. Тем не менее, "кэширование" по-прежнему работает в разумные сроки, потому что вашему вводу нужна только часть подзадач, которые нужно решить --- но слишком сложно определить, какие подзадачи вам нужно решить, и, следовательно,. С другой стороны, бывают ситуации, когда вы знаете, что вам нужно будет решить все подзадачи. В этом случае продолжайте использовать снизу вверх.
Я лично использовал бы верхнюю дно для оптимизации абзаца, а также проблема оптимизации переноса Word (посмотрите алгоритмы линейного разрыва Knuth-Plass, по крайней мере, TeX использует его, и некоторое программное обеспечение Adobe Systems использует аналогичный подход). Я использовал бы снизу вверх для Fast Fourier Transform.
Давайте возьмем ряд фибоначчи в качестве примера
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), а затем идет вплоть до нижнего/нижнего числа. Этот подход - это подход сверху вниз.
Чтобы избежать такого же вычисления несколько раз, мы используем методы динамического программирования. Мы сохраняем ранее вычисленное значение и повторно используем его. Этот метод называется memoization. Для динамического программирования есть еще одно другое, а затем memoization, которое не требуется для обсуждения текущей проблемы.
Top-Down
Давайте перепишем наш оригинальный алгоритм и добавим memoized методы.
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);
Это решение по-прежнему остается сверху вниз, поскольку алгоритм начинается с верхнего значения и спускается на каждый шаг, чтобы получить наше главное значение.
Bottom-Up
Но, вопрос в том, можем ли мы начинать снизу, как, например, с первого числа фибоначчи, а затем пройти наш путь вверх. Давайте перепишем его с помощью этих методов,
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-го числа. Эти методы фактически называют восходящими методами.
Последние два, алгоритмы с полным заполнением требований динамического программирования. Но один сверху вниз, а другой - снизу вверх. Оба алгоритма имеют сходную пространственную и временную сложность.
Динамическое программирование часто называют Memoization!
1.Memoization - это метод сверху вниз (начать решение данной проблемы, разбив его), а динамическое программирование - это восходящая техника (начните решать из тривиальной подзадачи, вплоть до данной проблемы)
2.DP находит решение, начиная с базового футляра (я) и работает вверх. DP решает все подзадачи, потому что делает это снизу вверх
В отличие от Memoization, которая решает только необходимые суб-проблемы
DP имеет потенциал для преобразования экспоненциально-временных решений грубой силы в алгоритмы полиномиального времени.
DP может быть намного более эффективным, поскольку его итеративный
Наоборот, Memoization должна оплачивать (часто значительные) накладные расходы из-за рекурсии.
Чтобы быть более простым, Memoization использует подход сверху вниз для решения проблемы, то есть он начинается с основной (основной) проблемы, а затем разбивает ее на под-проблемы и аналогично решает эти проблемы. В этом подходе одна и та же суб-проблема может возникать несколько раз и потреблять больше циклов ЦП, что увеличивает временную сложность. Если в динамическом программировании одна и та же подзадача не будет решена несколько раз, но предыдущий результат будет использован для оптимизации решения.
Просто говоря, подход сверху вниз использует рекурсию для повторного вызова подпроцессов снова, где в качестве подхода снизу вверх используйте сингл без вызова какого-либо одного и, следовательно, он более эффективен.
Ниже приведено решение на основе 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];
}
Вы можете думать о своей рекурсивной реализации у себя дома. Это довольно хорошо и сложно, если вы еще не решили что-то подобное раньше.