Оптимізація Кнута

Оптимізація Кнута, також відома як прискорення Кнута-Яо (Knuth-Yao Speedup), — це особливий випадок динамічного програмування на відрізках, який дозволяє покращити часову складність розв'язків у лінійну кількість разів: зі стандартного $O(n^3)$ для ДП на відрізках до $O(n^2)$.

Коли підходить цей алгоритм?

• Чи має перехід вигляд ДП на відрізках $dp(i, j) = \min_{i \leq k < j} [ dp(i, k) + dp(k+1, j) + C(i, j) ]$, який потрібно прискорити з $O(n^3)$ до $O(n^2)$?
• Чи виконується нерівність на оптимальну точку розбиття $opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j)$ (достатньо, щоб $C$ задовольняла $C(b, c) \leq C(a, d)$ та нерівність чотирикутника $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ для $a \leq b \leq c \leq d$)?
• Чи розбиття відрізка на дві частини, а не вибір однієї точки з попереднього рядка? (якщо ні → ДП «розділяй і володарюй»)

Умови

Прискорення застосовне для переходів вигляду

$$dp(i, j) = \min_{i \leq k < j} [ dp(i, k) + dp(k+1, j) + C(i, j) ].$$

Подібно до ДП «розділяй і володарюй», нехай $opt(i, j)$ — це максимальне значення $k$, яке мінімізує вираз у переході (далі в цій статті $opt$ ми називаємо «оптимальною точкою розбиття»). Оптимізація вимагає, щоб виконувалося таке:

$$opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j).$$

Ми можемо показати, що це правда, коли функція вартості $C$ задовольняє такі умови для $a \leq b \leq c \leq d$:

1. $C(b, c) \leq C(a, d)$;

2. $C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ (нерівність чотирикутника [QI]).

Цей результат доведено нижче.

Алгоритм

Оброблятимемо стани ДП так, щоб обчислити $dp(i, j-1)$ та $dp(i+1, j)$ перед $dp(i, j)$, а заразом обчислити й $opt(i, j-1)$ та $opt(i+1, j)$. Тоді для обчислення $opt(i, j)$ замість перебору значень $k$ від $i$ до $j-1$ нам достатньо перебрати лише від $opt(i, j-1)$ до $opt(i+1, j)$. Щоб обробляти пари $(i,j)$ у такому порядку, достатньо використати вкладені цикли for, у яких $i$ йде від максимального значення до мінімального, а $j$ — від $i+1$ до максимального значення.

Загальна реалізація

Хоча реалізація може відрізнятися, ось доволі загальний приклад. Структура коду майже ідентична до ДП на відрізках.

C++

int solve() {
    int N;
    ... // зчитуємо N та вхідні дані
    int dp[N][N], opt[N][N];

    auto C = [&](int i, int j) {
        ... // Реалізуємо функцію вартості C.
    };

    for (int i = 0; i < N; i++) {
        opt[i][i] = i;
        ... // Ініціалізуємо dp[i][i] відповідно до задачі
    }

    for (int i = N-2; i >= 0; i--) {
        for (int j = i+1; j < N; j++) {
            int mn = INT_MAX;
            int cost = C(i, j);
            for (int k = opt[i][j-1]; k <= min(j-1, opt[i+1][j]); k++) {
                if (mn >= dp[i][k] + dp[k+1][j] + cost) {
                    opt[i][j] = k; 
                    mn = dp[i][k] + dp[k+1][j] + cost; 
                }
            }
            dp[i][j] = mn; 
        }
    }

    return dp[0][N-1];
}

Python

def solve():
    N = ...  # зчитуємо N та вхідні дані
    dp = [[0] * N for _ in range(N)]
    opt = [[0] * N for _ in range(N)]

    def C(i, j):
        ...  # Реалізуємо функцію вартості C.

    for i in range(N):
        opt[i][i] = i
        ...  # Ініціалізуємо dp[i][i] відповідно до задачі

    # i йде від максимального значення до мінімального,
    # тож dp(i, j-1) та dp(i+1, j) уже обчислені до dp(i, j)
    for i in range(N - 2, -1, -1):
        for j in range(i + 1, N):
            mn = float("inf")
            cost = C(i, j)
            # перебираємо лише вікно [opt(i, j-1), opt(i+1, j)]
            for k in range(opt[i][j - 1], min(j - 1, opt[i + 1][j]) + 1):
                if mn >= dp[i][k] + dp[k + 1][j] + cost:
                    opt[i][j] = k
                    mn = dp[i][k] + dp[k + 1][j] + cost
            dp[i][j] = mn

    return dp[0][N - 1]

TypeScript

function solve(): number {
  const N: number = ...; // зчитуємо N та вхідні дані
  const dp: number[][] = Array.from({ length: N }, () => new Array(N).fill(0));
  const opt: number[][] = Array.from({ length: N }, () => new Array(N).fill(0));

  const C = (i: number, j: number): number => {
    ...; // Реалізуємо функцію вартості C.
  };

  for (let i = 0; i < N; i++) {
    opt[i][i] = i;
    ...; // Ініціалізуємо dp[i][i] відповідно до задачі
  }

  // i йде від максимального значення до мінімального,
  // тож dp(i, j-1) та dp(i+1, j) уже обчислені до dp(i, j)
  for (let i = N - 2; i >= 0; i--) {
    for (let j = i + 1; j < N; j++) {
      let mn = Infinity;
      const cost = C(i, j);
      // перебираємо лише вікно [opt(i, j-1), opt(i+1, j)]
      for (let k = opt[i][j - 1]; k <= Math.min(j - 1, opt[i + 1][j]); k++) {
        if (mn >= dp[i][k] + dp[k + 1][j] + cost) {
          opt[i][j] = k;
          mn = dp[i][k] + dp[k + 1][j] + cost;
        }
      }
      dp[i][j] = mn;
    }
  }

  return dp[0][N - 1];
}

Go

func solve() int {
    var N int
    ... // зчитуємо N та вхідні дані
    dp := make([][]int, N)
    opt := make([][]int, N)
    for i := range dp {
        dp[i] = make([]int, N)
        opt[i] = make([]int, N)
    }

    C := func(i, j int) int {
        ... // Реалізуємо функцію вартості C.
    }

    for i := 0; i < N; i++ {
        opt[i][i] = i
        ... // Ініціалізуємо dp[i][i] відповідно до задачі
    }

    // i йде від максимального значення до мінімального,
    // тож dp(i, j-1) та dp(i+1, j) уже обчислені до dp(i, j)
    for i := N - 2; i >= 0; i-- {
        for j := i + 1; j < N; j++ {
            mn := math.MaxInt
            cost := C(i, j)
            // перебираємо лише вікно [opt(i, j-1), opt(i+1, j)]
            for k := opt[i][j-1]; k <= min(j-1, opt[i+1][j]); k++ {
                if mn >= dp[i][k]+dp[k+1][j]+cost {
                    opt[i][j] = k
                    mn = dp[i][k] + dp[k+1][j] + cost
                }
            }
            dp[i][j] = mn
        }
    }

    return dp[0][N-1]
}

Складність

Складність алгоритму можна оцінити такою сумою:

$$\sum\limits_{i=1}^N \sum\limits_{j=i+1}^N [opt(i+1,j)-opt(i,j-1)] = \sum\limits_{i=1}^N \sum\limits_{j=i}^{N-1} [opt(i+1,j+1)-opt(i,j)].$$

Як бачимо, більшість доданків у цьому виразі взаємно скорочуються, окрім додатних доданків з $j=N-1$ та від'ємних доданків з $i=1$. Тому всю суму можна оцінити як

$$\sum\limits_{k=1}^N[opt(k,N)-opt(1,k)] = O(n^2),$$

а не як $O(n^3)$, як було б, якби ми використовували звичайне ДП на відрізках.

На практиці

Найпоширеніше застосування оптимізації Кнута — це ДП на відрізках із заданим переходом. Єдина складність полягає в тому, щоб довести, що функція вартості задовольняє наведені умови. Найпростіший випадок — коли функція вартості $C(i, j)$ є просто сумою елементів підмасиву $S[i, i+1, ..., j]$ для деякого масиву (залежно від задачі). Утім, іноді вони бувають складнішими.

Зауважимо, що важливішою за умови на перехід ДП і функцію вартості є нерівність на оптимальну точку розбиття. У деяких задачах, як-от задача про оптимальне бінарне дерево пошуку (яка, до речі, і є початковою задачею, для якої цю оптимізацію було розроблено), переходи та функції вартості будуть менш очевидними, проте все одно можна довести, що $opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j)$, а отже, скористатися цією оптимізацією.

Доведення коректності

Щоб довести коректність цього алгоритму в термінах умов на $C(i,j)$, достатньо довести, що

$$opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j)$$

за умови, що задані умови виконуються.

Лема

$dp(i, j)$ також задовольняє нерівність чотирикутника, якщо виконуються умови задачі.

Доведення

Доведення цієї леми використовує сильну індукцію. Його взято зі статті Efficient Dynamic Programming Using Quadrangle Inequalities авторства F. Frances Yao, у якій було введено прискорення Кнута-Яо (це конкретне твердження — Лема 2.1 у статті). Ідея полягає в тому, щоб провести індукцію за довжиною $l = d - a$. Випадок $l = 1$ тривіальний. Для $l > 1$ розглянемо 2 випадки:

1. $b = c$
   Нерівність зводиться до $dp(a, b) + dp(b, d) \leq dp(a, d)$ (тут припускаємо, що $dp(i, i) = 0$ для всіх $i$, що справджується для всіх задач, у яких використовується ця оптимізація). Нехай $opt(a,d) = z$.

   • Якщо $z < j$,
     зауважимо, що

     $$dp(a, b) \leq dp_{z}(a, b) = dp(a, z) + dp(z+1, b) + C(a, b).$$

     Отже,

     $$dp(a, b) + dp(b, d) \leq dp(a, z) + dp(z+1, b) + dp(b, d) + C(a, b)$$

     З припущення індукції $dp(z+1, b) + dp(b, d) \leq dp(z+1, d)$. Також задано, що $C(a, b) \leq C(a, d)$. Поєднання цих 2 фактів із наведеною вище нерівністю дає шуканий результат.

   • Якщо $z \geq j$, доведення цього випадку симетричне до попереднього.

2. $b < c$
   Нехай $opt(b, c) = z$ та $opt(a, d) = y$.

   • Якщо $z \leq y$,

     $$dp(a, c) + dp(b, d) \leq dp_{z}(a, c) + dp_{y}(b, d)$$

     де

     $$dp_{z}(a, c) + dp_{y}(b, d) = C(a, c) + C(b, d) + dp(a, z) + dp(z+1, c) + dp(b, y) + dp(y+1, d).$$

     Застосування QI до $C$ та до стану ДП для індексів $z+1 \leq y+1 \leq c \leq d$ (з припущення індукції) дає шуканий результат.

   • Якщо $z > y$, доведення цього випадку симетричне до попереднього.

На цьому доведення леми завершується.

Тепер розглянемо таку конструкцію. У нас є 2 індекси $i \leq p \leq q < j$. Покладемо $dp_{k} = C(i, j) + dp(i, k) + dp(k+1, j)$.

Припустимо, ми покажемо, що

$$dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \implies dp_{p}(i, j) \geq dp_{q}(i, j).$$

Поклавши $q = opt(i, j-1)$, за означенням маємо $dp_{p}(i, j-1) \geq dp_{q}(i, j-1)$. Отже, застосовуючи цю нерівність до всіх $i \leq p \leq q$, можемо зробити висновок, що $opt(i, j)$ щонайменше таке саме велике, як $opt(i, j-1)$, чим доводимо першу половину нерівності.

Тепер, застосовуючи QI до деяких індексів $p+1 \leq q+1 \leq j-1 \leq j$, отримуємо

$$\begin{align} &dp(p+1, j-1) + dp(q+1, j) ≤ dp(q+1, j-1) + dp(p+1, j) \\ \implies& (dp(i, p) + dp(p+1, j-1) + C(i, j-1)) + (dp(i, q) + dp(q+1, j) + C(i, j)) \\ \leq& (dp(i, q) + dp(q+1, j-1) + C(i, j-1)) + (dp(i, p) + dp(p+1, j) + C(i, j)) \\ \implies& dp_{p}(i, j-1) + dp_{q}(i, j) ≤ dp_{p}(i, j) + dp_{q}(i, j-1) \\ \implies& dp_{p}(i, j-1) - dp_{q}(i, j-1) ≤ dp_{p}(i, j) - dp_{q}(i, j) \\ \end{align}$$

Нарешті,

$$\begin{align} &dp_{p}(i, j-1) \geq dp_{q}(i, j-1) \\ &\implies 0 \leq dp_{p}(i, j-1) - dp_{q}(i, j-1) \leq dp_{p}(i, j) - dp_{q}(i, j) \\ &\implies dp_{p}(i, j) \geq dp_{q}(i, j) \end{align}$$

Це доводить першу частину нерівності, тобто $opt(i, j-1) \leq opt(i, j)$. Другу частину $opt(i, j) \leq opt(i+1, j)$ можна показати тією самою ідеєю, починаючи з нерівності $dp(i, p) + dp(i+1, q) ≤ dp(i+1, p) + dp(i, q)$.

На цьому доведення завершується.

Задачі для практики

• UVA - Cutting Sticks
• UVA - Prefix Codes
• SPOJ - Breaking String
• UVA - Optimal Binary Search Tree

Джерела

• Geeksforgeeks Article
• Doc on DP Speedups
• Efficient Dynamic Programming Using Quadrangle Inequalities