Динамическое программирование и мемуаризация: восходящий и нисходящий подходы

сверху вниз и снизу вверх DP-это два разных способа решения одних и тех же проблем. Рассмотрим мемуарное (сверху вниз) vs динамическое (снизу вверх) программное решение для вычисления чисел Фибоначчи.

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(49) и fib(48), но тогда оба они в конечном итоге вызовут fib(47), хотя значение одно и то же. На самом деле,fib(47) будет вычисляться три раза: по прямой связи от fib(49), по прямому звонку от fib(48), а также по прямой связи от другого fib(48), который был порожден расчета fib(49)... Так что вы видите, у нас есть перекрывающихся подзадач.

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

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

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

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

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

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

Я бы лично использовал top-bottom для оптимизации абзаца a. k. a слово оберните задачу оптимизации (посмотрите алгоритмы линейного взлома Knuth-Plass; по крайней мере, 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 находит решение, начиная с базового случая(ов) и продвигается вверх. ДП решает все проблемы, потому что он делает это снизу вверх

в отличие от Мемуаризация, которая решает только необходимые подзадачи

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

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

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

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

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

Ниже приводится решение на основе 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];
}

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