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

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

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

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

rev4: очень красноречивый комментарий пользователя Sammaron отметил, что, возможно, этот ответ ранее путал сверху вниз и снизу вверх. Хотя первоначально в этом ответе (rev3) и других ответах говорилось, что «снизу вверх - это запоминание» («примите подзадачи»), он может быть обратным (то есть «сверху вниз» может означать «принять подзадачи» и « снизу вверх "может быть" составить подзадачи "). Ранее я читал о запоминании как о другом типе динамического программирования, в отличие от подтипа динамического программирования. Я цитировал эту точку зрения, хотя и не подписывался на нее. Я переписал этот ответ, чтобы не зависеть от терминологии, пока в литературе не будут найдены соответствующие ссылки. Я также преобразовал этот ответ в вики сообщества. Пожалуйста, предпочитайте академические источники. Список литературы:} {Литература: 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), потому что мы его кэшировали.
  • Это начинается в верхней части дерева и оценивает подзадачи от листьев / поддеревьев назад к корню.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сверху вниз и снизу вверх 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)... Итак, вы видите, у нас есть перекрывающиеся подзадачи ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сверху вниз : отслеживание вычисленного значения до настоящего времени и возврат результата при выполнении базового условия.

int n = 5;
fibTopDown(1, 1, 2, n);

private int fibTopDown(int i, int j, int count, int n) {
    if (count > n) return 1;
    if (count == n) return i + j;
    return fibTopDown(j, i + j, count + 1, n);
}

Снизу вверх : текущий результат зависит от результата его подзадачи.

int n = 5;
fibBottomUp(n);

private int fibBottomUp(int n) {
    if (n <= 1) return 1;
    return fibBottomUp(n - 1) + fibBottomUp(n - 2);
}