Проблемы с динамическим программированием с использованием итерации

Question

Я потратил много времени, чтобы узнать о реализации/визуализации задач динамического программирования с помощью итерации, но мне очень сложно понять, я могу реализовать то же самое с помощью рекурсии с memoization, но она медленна при сравнении к итерации.

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

Спасибо!

Answer 1

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

Для более простого примера рассмотрим последовательность Фибоначчи. Скажем, мы хотели бы вычислить F(101). Когда это рекурсивно, мы начнем с нашей большой проблемы - F(101). Для этого мы замечаем, что нам нужно вычислить F(99) и F(100). Затем для F(99) нам нужны F(97) и F(98). Мы продолжаем, пока не достигнем наименьшей разрешимой подзадачи, которая равна F(1), и запомните результаты. При этом итеративно мы начинаем с наименьшей подзадачи, F(1) и продолжаем все, сохраняя результаты в таблице (так что в этом случае это просто простой цикл от 1 до 101).

Давайте рассмотрим проблему умножения матричной цепочки, которую вы запросили. Мы начнем с наивной рекурсивной реализации, затем рекурсивного DP и, наконец, итеративного DP. Это будет реализовано в супе C/C++, но вы должны уметь следовать, даже если вы не очень хорошо знакомы с ними.

/* Solve the problem recursively (naive) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_rn(int p[], int n, int i, int j) { 
    // A matrix multiplied by itself needs no operations 
    if (i == j) return 0; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    int min = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_rn(p, n, i, k) + solve_rn(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < min) min = tmp; 
    } 

    // Return solution for this sub-problem 
    return min; 
} 

Чтобы вычислить результат, начинается с большой проблемой:

solve_rn(p, n, 1, n - 1) 

Ключ DP должен помнить все решения для подзадачи вместо забвения их, так что мы не» нужно перепроверить их.Это тривиально, чтобы сделать несколько изменений в коде выше, с тем чтобы добиться того, что:

/* Solve the problem recursively (DP) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_r(int p[], int n, int i, int j) { 
    /* We need to remember the results for state i..j. 
     This can be done in a matrix, which we call dp, 
     such that dp[i][j] is the best solution for the 
     state i..j. We initialize everything to 0 first. 

     static keyword here is just a C/C++ thing for keeping 
     the matrix between function calls, you can also either 
     make it global or pass it as a parameter each time. 

     MAXN is here too because the array size when doing it like 
     this has to be a constant in C/C++. I set it to 100 here. 
     But you can do it some other way if you don't like it. */ 
    static int dp[MAXN][MAXN] = {{0}}; 

    /* A matrix multiplied by itself has 0 operations, so we 
     can just return 0. Also, if we already computed the result 
     for this state, just return that. */ 
    if (i == j) return 0; 
    else if (dp[i][j] != 0) return dp[i][j]; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    dp[i][j] = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_r(p, n, i, k) + solve_r(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < dp[i][j]) dp[i][j] = tmp; 
    } 

    // Return solution for this sub-problem 
    return dp[i][j];; 
} 

Мы начинаем с большой проблемой, а также:

solve_r(p, n, 1, n - 1) 

Итерационный решение только, ну, перебирать все государства, вместо того, начиная с верхней:

/* Solve the problem iteratively 

    p - matrix dimensions 
    n - size of p 

    We don't need to pass state, because we iterate the states. */ 
int solve_i(int p[], int n) { 
    // But we do need our table, just like before 
    static int dp[MAXN][MAXN]; 

    // Multiplying a matrix by itself needs no operations 
    for (int i = 1; i < n; ++i) 
     dp[i][i] = 0; 

    // L represents the length of the chain. We go from smallest, to 
    // biggest. Made L capital to distinguish letter l from number 1 
    for (int L = 2; L < n; ++L) { 
     // This double loop goes through all the states in the current 
     // chain length. 
     for (int i = 1; i <= n - L + 1; ++i) { 
      int j = i + L - 1; 
      dp[i][j] = std::numeric_limits<int>::max(); 

      for (int k = i; k <= j - 1; ++k) { 
       int tmp = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]; 
       if (tmp < dp[i][j]) 
        dp[i][j] = tmp; 
      } 
     } 
    } 

    // Return the result of the biggest problem 
    return dp[1][n-1]; 
} 

Чтобы вычислить результат, назвать его просто:

solve_i(p, n) 

---

Объяснение счетчиков циклов в последнем примере:

Допустим, нам нужно оптимизировать умножение матриц 4: A B C D. Мы делаем итеративный подход, поэтому сначала вычислим цепи длиной 2: (A B) C D, A (B C) D и A B (C D). А затем цепи из трех: (A B C) D и A (B C D). Вот что такое L, i и j для.

L представляет длину цепи, оно идет от 2 к n - 1 (n в этом случае 4, так что это 3).

i и j представляют начальное и конечное положение цепочки. В случае L = 2, i идет от 1 к 3 и j идет от 2 к 4:

(A B) C D  A (B C) D  A B (C D) 
^^   ^^   ^^ 
i j    i j    i j 

В случае L = 3, i идет от 1 к 2 и j идет от 3 к 4:

(A B C) D  A (B C D) 
^ ^  ^^
i j   i j 

Как правило, i идет от 1 до n - L + 1, и j - i + L - 1.

Теперь давайте продолжим использование алгоритма, предполагая, что мы находимся на том этапе, на котором у нас есть (A B C) D. Теперь нам нужно учесть подзадачи (которые уже рассчитаны): ((A B) C) D и (A (B C)) D. Это то, для чего стоит k. Он проходит через все позиции между i и j и вычисляет вспомогательные проблемы.

Надеюсь, я помог.

Answer 2

Проблема с рекурсией - это большое количество кадров стека, которые необходимо вытолкнуть/выскочить. Это может быстро стать бутылочным горлом.

Серия Фибоначчи может быть рассчитана с помощью итеративного DP или рекурсии с записью. Если мы вычисляем F (100) в DP, то все, что нам нужно, это массив длиной 100, например. int[100], и это мужество нашей используемой памяти.Мы вычисляем все записи предварительного заполнения массива f[0] и f[1], поскольку они определены как 1. и каждое значение просто зависит от предыдущих двух.

Если мы используем рекурсивное решение, мы начинаем с fib(100) и работаем вниз. Каждый вызов метода от 100 до 0 помещается в стек, И проверено, сохранено ли оно. Эти операции складываются, и итерация не страдает ни от одного из них. В итерации (снизу вверх) мы уже знаем, что все предыдущие ответы действительны. Большее влияние, вероятно, представляет собой стек кадров; и с учетом большего ввода вы можете получить StackOverflowException для того, что было иначе тривиально с итеративным подходом DP.