В чем разница между снизу вверх и сверху вниз?

Question

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

сверху вниз состоит в том, чтобы решить проблему «естественным образом», и проверьте, рассчитали ли вы решение подзадачи ранее.

Я немного растерялся. В чем разница между этими двумя?

Answer 1

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(2)=fib(1)+fib(0)=1+0=1.Затем он, наконец, разрешит fib(3)=fib(2)+fib(1), но ему не нужно пересчитывать fib(2), потому что мы его кешируем.
  • Это начинается в верхней части дерева и оценивает подзадачи из листьев / поддеревьев назад.вверх к корню.

• Табуляция - Вы также можете думать о динамическом программировании как о алгоритме «заполнения таблицы» (хотя обычно многомерный, эта «таблица» может иметь неЕвклидова геометрия в очень редких случаях *).Это похоже на запоминание, но более активное и включает в себя еще один шаг: вы должны заблаговременно выбрать точный порядок, в котором вы будете выполнять вычисления.Это не должно подразумевать, что заказ должен быть статическим, но что у вас гораздо больше гибкости, чем в памятке.

  • пример: Если вы выполняете Фибоначчи, вы можете рассчитатьчисла в следующем порядке: fib(2), fib(3), fib(4) ... кэшируют каждое значение, чтобы вам было легче вычислять следующие.Вы также можете думать об этом как о заполнении таблицы (еще одна форма кэширования).
  • Лично я не часто слышу слово «табуляция», но это очень приличный термин.Некоторые люди считают это «динамическим программированием».
  • Перед запуском алгоритма программист рассматривает все дерево, а затем пишет алгоритм для оценки подзадач в определенном порядке по направлению к корню, обычно заполняя таблицу.
  • * сноска: иногда таблица'не является прямоугольным столом с сетчатым соединением, как таковым.Скорее, он может иметь более сложную структуру, такую ​​как дерево, или структуру, специфичную для проблемной области (например, города в пределах расстояния полета на карте), или даже решетчатую диаграмму, которая, хотя и имеет вид сетки, не имеетструктура соединения «вверх-вниз-влево-вправо» и т. д. Например, пользователь 3290797 связал пример динамического программирования для нахождения максимального независимого набора в дереве , который соответствует заполнению пробелов в дереве.

(В общем, в парадигме «динамического программирования» я бы сказал, что программист рассматривает все дерево, , а затем пишет алгоритм, который реализуетстратегия для оценки подзадач, которая может оптимизировать любые свойства, которые вы хотите (обычно это сочетание сложности времени и сложности пространства). Ваша стратегия должна начинаться где-то с какой-то конкретной подзадачи и, возможно, может адаптироваться на основе результатов этих оценок.В общем смысле «динамическое программирование», вы можете попробоватьдля кэширования этих подзадач и, в более общем смысле, постарайтесь не пересматривать подзадачи с тонким отличием, возможно, в случае графов в различных структурах данных.Очень часто эти структуры данных в своей основе, как массивы или таблицы.Решения подзадач можно отбросить, если они нам больше не нужны.)

[Ранее в этом ответе делалось утверждение о терминологии «сверху вниз» и «снизу вверх»;ясно, что есть два основных подхода, называемых Мемоизация и табуляция, которые могут быть в биографии с этими терминами (хотя и не полностью).Общий термин, который используют большинство людей, - это «Динамическое программирование», а некоторые говорят «Мемоизация» для обозначения этого конкретного подтипа «Динамическое программирование».В этом ответе отказывается указывать, что является «сверху вниз» и «снизу вверх», пока сообщество не сможет найти надлежащие ссылки в научных статьях.В конечном счете, важно понимать различие, а не терминологию.]

---

Плюсы и минусы

Простота кодирования

Запоминание кода очень просто (выобычно может * написать аннотацию "memoizer" или функцию-обертку, которая автоматически сделает это за вас), и должна быть вашей первой линией подхода.Недостатком табулирования является то, что вам нужно придумать порядок.

* (на самом деле это легко сделать, только если вы пишете функцию самостоятельно и / или программируете на нечистом / не функциональном языке программирования... например, если кто-то уже написал предварительно скомпилированную функцию fib, она обязательно делает рекурсивные вызовы сама себе, и вы не можете волшебным образом запоминать функцию, не гарантируя, что эти рекурсивные вызовы вызовут вашу новую запомненную функцию (а не оригинальную немемозированную функцию))

Рекурсивность

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

Практические проблемы

При наличии заметки, если дерево очень глубокое (например, fib(10^6)), вам не хватит места в стеке, потому что каждое отложенное вычисление должно быть помещено в стек, и у вас будет 10 ^ 6 из них.

Оптимальность

Любой подход не может быть оптимальным по времени, если вы выполняете заказ (или пытаетесь)Посещение подзадач не является оптимальным, в частности, если существует несколько способов вычисления подзадачи (обычно это может решить кэширование, но теоретически возможно, что в некоторых экзотических случаях кэширование может быть невозможным).Мемоизация, как правило, добавляет сложность времени к сложности пространства (например, при табулировании у вас больше свободы в отбрасывании вычислений, например, при использовании табуляции в Fib позволяет использовать пространство O (1), но при запоминании в Fib используется O (N).пространство стека).

Расширенные возможности оптимизации

Если вы также решаете чрезвычайно сложные проблемы, у вас может не быть иного выбора, кроме как выполнять табулирование (или, по крайней мере, играть более активную роль в управлении мемоизацией, куда вы хотите ее направить),Кроме того, если вы находитесь в ситуации, когда оптимизация абсолютно необходима, и вы должны оптимизировать, табулирование позволит вам выполнить оптимизацию, которую в противном случае запоминание не позволило бы вам сделать разумным способом.По моему скромному мнению, в обычной разработке программного обеспечения ни один из этих двух случаев никогда не встречался, поэтому я бы просто использовал памятку («функция, которая кэширует свои ответы»), если что-то (например, пространство стека) не делает необходимым табулирование ... хотяТехнически, чтобы избежать выброса стека, вы можете: 1) увеличить предельный размер стека в языках, которые позволяют это, или 2) потреблять постоянный фактор дополнительной работы для виртуализации вашего стека (ick), или 3) программы в стиле передачи продолжения, которыйв действительности также виртуализирует ваш стек (не уверен, что это сложно, но в основном вы будете эффективно извлекать цепочку отложенных вызовов из стека размера N и фактически вставлять ее в N последовательных вложенных функций thunk ... хотя в некоторых языках безДля оптимизации хвостового вызова вам, возможно, придется батутить вещи, чтобы избежать выброса из стека.)

---

Более сложные примеры

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

• алгоритм для вычисления расстояния редактирования [ 4 ],интересен как нетривиальный пример двумерного алгоритма заполнения таблиц

Answer 2

Сверху вниз и снизу вверх 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)

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

Answer 3

Ключевой особенностью динамического программирования является наличие перекрывающихся подзадач .То есть проблема, которую вы пытаетесь решить, может быть разбита на подзадачи, и многие из этих подзадач имеют общие подзадачи.Это как «Разделяй и властвуй», но в конечном итоге ты делаешь одно и то же много, много раз.Пример, который я использовал с 2003 года при обучении или объяснении этих вопросов: вы можете вычислить числа Фибоначчи рекурсивно.

def fib(n):
  if n < 2:
    return n
  return fib(n-1) + fib(n-2)

Используйте свой любимый язык и попробуйте запустить его для fib(50).Это займет очень и очень много времени.Примерно столько же времени, сколько и само по себе * 1009!Тем не менее, много ненужной работы делается.fib(50) вызовет fib(49) и fib(48), но тогда оба из них в итоге вызовут fib(47), даже если значение будет одинаковым.Фактически, fib(47) будет вычисляться три раза: прямым вызовом из fib(49), прямым вызовом из fib(48), а также прямым вызовом из другого fib(48), который был порожден вычислениемиз fib(49) ... Итак, вы видите, у нас есть перекрывающиеся подзадачи .

Хорошие новости: нет необходимости вычислять одно и то же значение много раз.Как только вы вычислите его один раз, кэшируйте результат, а в следующий раз используйте кэшированное значение!Это суть динамического программирования.Вы можете назвать это «сверху вниз», «памятка» или как угодно.Этот подход очень интуитивно понятен и очень прост в реализации.Просто сначала напишите рекурсивное решение, протестируйте его на небольших тестах, добавьте памятку (кэширование уже вычисленных значений) и --- бинго!--- все готово.

Обычно вы также можете написать эквивалентную итеративную программу, которая работает снизу вверх без рекурсии.В этом случае это был бы более естественный подход: цикл от 1 до 50 вычисляет все числа Фибоначчи по ходу движения.

fib[0] = 0
fib[1] = 1
for i in range(48):
  fib[i+2] = fib[i] + fib[i+1]

В любом интересном сценарии восходящее решение обычно труднее понять.Однако, как только вы поймете это, обычно вы получите более ясную картину того, как работает алгоритм.На практике при решении нетривиальных задач я рекомендую сначала написать нисходящий подход и протестировать его на небольших примерах.Затем напишите восходящее решение и сравните оба, чтобы убедиться, что вы получаете то же самое.В идеале, сравните два решения автоматически.Напишите небольшую подпрограмму, которая будет генерировать множество тестов, в идеале - все небольшие тесты до определенного размера - и проверить, что оба решения дают одинаковый результат.После этого используйте восходящее решение в производстве, но оставьте код сверху вниз, закомментированный.Это облегчит другим разработчикам понимание того, что вы делаете: восходящий код может быть совершенно непонятным, даже если вы его написали, и даже если вы точно знаете, что делаете.

Во многихВ приложениях восходящий подход немного быстрее из-за накладных расходов на рекурсивные вызовы.Переполнение стека также может быть проблемой в определенных проблемах, и обратите внимание, что это может очень сильно зависеть от входных данных.В некоторых случаях вы не сможете написать тест, вызывающий переполнение стека, если вы недостаточно хорошо разбираетесь в динамическом программировании, но однажды это все же может произойти.

Теперь возникают проблемы, когдаПодход «вниз» - единственно возможное решение, потому что пространство проблем настолько велико, что невозможно решить все подзадачи.Тем не менее, «кэширование» все еще работает в разумные сроки, потому что вашему вводу требуется только часть подзадач, которые необходимо решить - но слишком сложно явно определить, какие подзадачи вам нужно решить, и, следовательно, написать нижнююрешениеС другой стороны, бывают ситуации, когда вы знаете, что вам нужно решить все подзадачи.В этом случае продолжайте и используйте снизу вверх.

Я бы лично использовал сверху вниз для оптимизации абзацев, то есть Задача оптимизации переноса слов (посмотрите алгоритмы переноса строк Кнута-Пласса; по крайней мере, TeX использует его, а некоторые программы Adobe Systems используют аналогичный подход). Я бы использовал восходящее для быстрого преобразования Фурье .

Answer 4

Давайте возьмем ряд Фибоначчи в качестве примера

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), а затем идет до нижних / нижних чисел. Этот подход на самом деле является нисходящим.

Чтобы не выполнять одни и те же вычисления несколько раз, мы используем методы динамического программирования. Мы храним ранее вычисленное значение и используем его повторно. Эта техника называется запоминанием. В динамическом программировании есть нечто большее, чем запоминание, которое не нужно для обсуждения текущей проблемы.

Top-Down

Давайте перепишем наш оригинальный алгоритм и добавим запомненные приемы.

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-го числа. Эта техника фактически называется восходящей техникой.

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

Answer 5

Динамическое программирование часто называют Memoization!

1.Memoization - это нисходящий метод (начните решать данную проблему, разбив ее), а динамическое программирование - это восходящий метод (начните решать с тривиальной подзадачи, вплоть до данной проблемы) *

2.DP находит решение, начиная с базового (ых) случая (ов) и продвигаясь вверх. DP решает все подзадачи, потому что он делает это снизу вверх

В отличие от Memoization, которая решает только необходимые подзадачи

1. У DP есть потенциал, чтобы преобразовать экспоненциальные решения грубой силы в алгоритмы полиномиального времени.

2. DP может быть намного более эффективным, потому что его итеративный

Напротив, мемоизация должна оплачивать (часто существенные) накладные расходы из-за рекурсии.

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

Answer 6

Проще говоря, нисходящий подход использует рекурсию для повторного вызова проблем Sub.
, где в качестве восходящего подхода используется сингл без вызова, и, следовательно, он более эффективен.

Answer 7

Ниже приведено решение на основе ДП для задачи редактирования расстояния, которое сверху вниз. Я надеюсь, что это также поможет понять мир динамического программирования:

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];
}

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