Оптимизация Кнута в динамическом программировании

Оптимизация Кнута — очень мощный инструмент динамического программирования, который можно использовать для уменьшения временной сложности решений в основном с O(N ³ ) до O(N ² ) . Обычно он используется для задач, которые можно решить с помощью диапазона DP при выполнении определенных условий. В этой статье мы сначала исследуем саму оптимизацию, а затем решим с ее помощью задачу.

Критерии оптимизации:

Оптимизация Кнута применяется к задачам ДП с переходом следующего вида –

dp[i][j] = cost[i][j] + min_i≤k<j(dp[i][k] + dp[k+1][j])

Кроме того, функция стоимости должна удовлетворять следующим условиям (для a ≤ b ≤ c ≤ d) —

1. Это монотон на решетке интервалов (MLI) [стоимость (b, c) ≤ стоимость (a, d)]
2. Он удовлетворяет четырехугольному неравенству (QI) [стоимость (a, c) + стоимость (b, d) ≤ стоимость (b, c) + стоимость (a, d)]

Оптимизация:

Для решения, которое выполняется за время O(N ³ ) , мы перебираем все значения k от i до j-1 . Однако мы можем добиться большего, используя следующую оптимизацию:

• Определим еще один массив в дополнение к массиву dp — opt[N][N] . Определите opt[i][j] как максимальное (или минимальное) значение k , для которого dp[i][j] минимизируется при переходе dp.
  opt[i][j] = argmin _i≤k<j (dp[i][k] + dp[k+1][j])
• Ключом к оптимизации Кнута и нескольким другим оптимизациям в DP, таким как оптимизация «разделяй и властвуй» (не путать с алгоритмом «разделяй и властвуй», описанным в этой статье), является следующее неравенство:

opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]

• Это помогает, потому что теперь для каждого перехода dp[] для вычисления dp[i][j] нам нужно только проверить значения k между opt[i][j-1] и opt[i+1][j] вместо этого между i к j-1 . Это снижает временную сложность алгоритма в линейный раз, что является значительным улучшением.

Доказательство правильности:

Чтобы доказать правильность этого алгоритма, нам нужно только доказать неравенство :

opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j].

Следуйте приведенному ниже разделу для доказательства правильности алгоритма:

Assumptions: If cost(i, j) is an MLI and satisfies the Quadrangle Inequality, then dp[i][j] also satisfies the inequality.  
Now, consider the following setup – 

• For i < j, we have some indices i ≤ p ≤ q < j-1. 
• Let dp_k[i][j] = cost[i][j] + dp[i][k] + dp[k+1][j]. 

If we can show that:

dp_p[i][j-1] ≥ dp_q[i][j-1] ⇒ dp_p[i][j] ≥ dp_q[i][j] 

then setting q = opt[i][j-1], it will be clear that opt[i][j] will be at least as much as opt[i][j-1], due to the implication of the above inequality for all indices p less than opt[i][j-1]. 
This will prove that opt[i][j-1] ≤ opt[i][j].

Proof: Using the quadrangle inequality on the dp array, we get –

dp[p+1][j-1] + dp[q+1][j] ≤ dp[q+1][j-1] + dp[p+1][j]
⇒ (dp[i, p] + dp[p+1][j-1] + cost(i, j-1)) + (dp[i, q] + dp[q+1][j] + cost(i, j))
     ≤ (dp[i, q] + dp[q+1][j-1] + cost(i, j-1)) + (dp[i, p] + dp[p+1][j] + cost(i, j))
⇒ dp_p[i][j-1] + dp_q[i][j] ≤ dp_p[i][j] + dp_q[i][j-1]
⇒ dp_p[i][j-1] – dp_q[i][j-1] ≤ dp_p[i][j] – dp_q[i][j]

dp_p[i][j-1] ≥ dp_q[i][j-1] 
⇒ 0 ≤ dp_p[i][j-1] – dp_q[i][j-1] ≤ dp_p[i][j] – dp_q[i][j] 
⇒ dp_p[i][j] ≥ dp_q[i][j]. 

Hence it is proved that: dp_p[i][j-1] ≥ dp_q[i][j-1] ⇒ dp_p[i][j] ≥ dp_q[i][j]

The second part of the inequality (i.e. opt[i][j] ≤ opt[i+1][j]) can be shown with the same idea, starting with the inequality

dp[i][p]+dp[i+1][q] ≤ dp[i][q]+dp[i+1][p].

The proof of these two inequalities combinedly gives: opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]

Пример:

Для заданного массива arr[] из N элементов задача состоит в том, чтобы найти минимальную стоимость сокращения массива до одного элемента за N-1 операций, где в каждой операции:

• Удалить элементы с индексами i и i+1 для некоторого допустимого индекса i , заменив их их суммой.
• Стоимость этого составляет arr[i] + arr[i+1] , где arr[] — это состояние массива непосредственно перед операцией.
• Эта стоимость будет добавлена к окончательной стоимости.

Примеры:

Input: arr[] = {3, 4, 2, 1, 7}
Output: 37
Explanation: 
Remove the elements at 0th and 1st index. arr[] = {7, 2, 1, 7}, Cost = 3 + 4 = 7
Remove 1st and 2nd index elements. arr[] = {7, 3, 7}, Cost = 2 + 1 = 3
Remove 1st and 2nd index elements, arr[] = {7, 10}, Cost = 3 + 7 = 10
Remove the last two elements. arr[] = {17}, Cost =  = 7 + 10 = 17
Total cost = 7 + 3 + 10 + 17 = 37
This is the minimum possible total cost for this array.

Input: arr[] = {1, 2, 3, 4}
Output: 19
Explanation: 
Remove the 0th and 1st index elements. arr[] = {3, 3, 4}. Cost = 1 + 2 = 3
Remove the 0th and 1st index elements. arr[] = {6, 4}. Cost = 3 + 3 = 6
Remove the 0th and 1st index elements. arr[] = {10}. Cost = 6 + 4 = 10
Total cost = 3 + 6 + 10 = 19.
This is the minimi=um possible cost.

Неоптимальное решение (с использованием Range DP): проблему можно решить, используя следующую идею:

• Let arr[] be the original array before any modifications are made. 
• For an element in the array that has been derived from indices i to j of a[], the cost of the final operation to form this single element will be the sum arr[i] + arr[i+1] + . . . + arr[j]. Let this value be denoted by the function cost(i, j).
• To find the minimum cost for the section arr[i, i+1, … j], consider the cost of converting the pairs of sub-arrays arr[i, i+1 . . . k] & arr[k+1, k+2 . . . j] into single elements, and choose the minimum over all possible values of k from i to j-1 (both inclusive).

Для реализации вышеуказанной идеи:

• Функцию стоимости можно рассчитать за постоянное время с предварительной обработкой, используя массив суммы префиксов:
  • Вычислить сумму префикса (скажем, сохраненную в массиве pref[]).
  • Таким образом, стоимость (i, j) может быть рассчитана как (pref[j] – pref[i-1]).
• Переход от i = 0 до N-1:
  • Перейдите от j = i+1 до N-1 , чтобы сгенерировать все подмассивы основного массива:
    • Решите эту проблему для всех этих возможных подмассивов со следующим переходом dp —
      dp[i][j] = cost(i, j) + min _i≤k≤j-1 (dp[i][k] + dp[k+1][j]) , как объяснено в приведенной выше идее.
• Здесь dp[i][j] — минимальная стоимость применения (j – i) операций над подмассивом arr[i, i+1, . . . дж] чтобы преобразовать его в один элемент.
  стоимость (i, j) обозначает стоимость последней операции, т. е. стоимость добавления двух последних значений для преобразования arr[i, i+1, . . ., j] к одному элементу.
• Окончательный ответ будет сохранен на dp[0][N-1] .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N ³ )
Вспомогательное пространство: O(N ² )

Оптимальное решение (с использованием оптимизации Кнута) :

Для этого вопроса выполняются условия применения оптимизации Кнута:

cost(i, j) is merely the sum of all elements in the subarray bounded by the indices i and j. Further, the transition function of dynamic programming matches the general case for applying this technique.

Выполните шаги, упомянутые здесь, чтобы реализовать идею оптимизации Кнута:

• Определите массив opt[N][N] и массив dp[][] .
• Теперь обработайте подмассивы в порядке возрастания длины с начальным состоянием dp[i][i] = 0 и opt[i][i] = i (поскольку значение должно быть i , чтобы минимизировать значение dp[i][i][ я] ).
• Таким образом, когда мы достигаем подмассива arr[i, . . ., j] , значение opt[i][j-1] и выберите [i+1][j] уже известны. Итак, проверяем только условие opt[i][j-1] ≤ k ≤ opt[i+1][j] , найти opt[i][j] и dp[i][j] .
• Здесь также функция стоимости рассчитывается так же, как и в предыдущем подходе, с использованием массива сумм префиксов .

Примечание. В приведенном ниже коде используется другой способ перебора всех подмассивов (вместо цикла в порядке возрастания длины). Однако, гарантируя, что opt[i+1][j] и opt[i][j- 1] вычисляются до dp[i][j].

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N ² )
Вспомогательное пространство: O(N ² )