Optimización de Knuth

La optimización de Knuth, también conocida como aceleración de Knuth-Yao, es un caso especial de programación dinámica sobre rangos, que puede optimizar la complejidad temporal de las soluciones en un factor lineal, de $O(n^3)$ para la DP de rangos estándar a $O(n^2)$ .

Condiciones

La aceleración se aplica a transiciones de la forma

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

De forma similar a la DP de divide y vencerás, sea $opt(i, j)$ el valor máximo de $k$ que minimiza la expresión de la transición ( $opt$ se denomina el «punto de corte óptimo» más adelante en este artículo). La optimización requiere que se cumpla lo siguiente:

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

Podemos mostrar que esto vale cuando la función de costo $C$ satisface las siguientes condiciones para $a \leq b \leq c \leq d$ :

$C(b, c) \leq C(a, d)$ ;
$C(a, c) + C(b, d) \leq C(a, d) + C(b, c)$ (la desigualdad del cuadrángulo [QI]).

Este resultado se demuestra más abajo.

Algoritmo

Procesemos los estados de la DP de modo que calculemos $dp(i, j-1)$ y $dp(i+1, j)$ antes que $dp(i, j)$ , y al hacerlo también calculemos $opt(i, j-1)$ y $opt(i+1, j)$ . Entonces, para calcular $opt(i, j)$ , en lugar de probar valores de $k$ desde $i$ hasta $j-1$ , solo hay que probar desde $opt(i, j-1)$ hasta $opt(i+1, j)$ . Para procesar los pares $(i,j)$ en este orden basta con usar bucles for anidados en los que $i$ va del valor máximo al mínimo y $j$ va de $i+1$ al valor máximo.

Implementación genérica

Aunque la implementación varía, aquí hay un ejemplo bastante genérico. La estructura del código es casi idéntica a la de la DP de rangos.



int solve() {
    int N;
    ... // leer N y la entrada
    int dp[N][N], opt[N][N];

    auto C = [&](int i, int j) {
        ... // Implementar la función de costo C.
    };

    for (int i = 0; i < N; i++) {
        opt[i][i] = i;
        ... // Inicializar dp[i][i] según el problema
    }

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

Complejidad

La complejidad del algoritmo se puede estimar como la siguiente suma:

$\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)].$

Como se ve, la mayoría de los términos de esta expresión se cancelan entre sí, salvo los términos positivos con $j=N-1$ y los términos negativos con $i=1$ . Así, toda la suma se puede estimar como

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

en lugar de $O(n^3)$ , como sería si usáramos una DP de rangos habitual.

En la práctica

La aplicación más común de la optimización de Knuth es en la DP de rangos, con la transición dada. La única dificultad está en demostrar que la función de costo satisface las condiciones dadas. El caso más simple es cuando la función de costo $C(i, j)$ es simplemente la suma de los elementos del subarreglo $S[i, i+1, …, j]$ para algún arreglo (según el enunciado). Sin embargo, a veces pueden ser más complicadas.

Nótese que, más que las condiciones sobre la transición de la DP y la función de costo, la clave de esta optimización es la desigualdad sobre el punto de corte óptimo. En algunos problemas, como el del árbol binario de búsqueda óptimo (que es, de hecho, el problema original para el que se desarrolló esta optimización), las transiciones y las funciones de costo serán menos evidentes; no obstante, aún se puede demostrar que $opt(i, j-1) \leq opt(i, j) \leq opt(i+1, j)$ y, por lo tanto, usar esta optimización.

Demostración de corrección

Para demostrar la corrección de este algoritmo en términos de las condiciones sobre $C(i,j)$ , basta con demostrar que

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

asumiendo que se cumplen las condiciones dadas.

Lema

dp(i, j)

también satisface la desigualdad del cuadrángulo, dadas las condiciones del problema.

Demostración

La demostración de este lema usa inducción fuerte. Se tomó del artículo Efficient Dynamic Programming Using Quadrangle Inequalities , de F. Frances Yao, que introdujo la aceleración de Knuth-Yao (este enunciado en particular es el Lema 2.1 del artículo). La idea es inducir sobre la longitud

l = d - a

. El caso

l = 1

es trivial. Para

l > 1

consideramos 2 casos:

$b = c$
La desigualdad se reduce a $dp(a, b) + dp(b, d) \leq dp(a, d)$ (esto asume que $dp(i, i) = 0$ para todo $i$ , lo cual vale en todos los problemas que usan esta optimización). Sea $opt(a,d) = z$ .
- Si $z < j$ ,
  Nótese que
  
  $dp(a, b) \leq dp_{z}(a, b) = dp(a, z) + dp(z+1, b) + C(a, b).$
  
  Por lo tanto,
  
  $dp(a, b) + dp(b, d) \leq dp(a, z) + dp(z+1, b) + dp(b, d) + C(a, b)$
  
  Por la hipótesis inductiva, $dp(z+1, b) + dp(b, d) \leq dp(z+1, d)$ . Además, se da que $C(a, b) \leq C(a, d)$ . Combinar estos 2 hechos con la desigualdad de arriba produce el resultado deseado.
- Si $z \geq j$ , la demostración de este caso es simétrica al caso anterior.
$b < c$
Sean $opt(b, c) = z$ y $opt(a, d) = y$ .
- Si $z \leq y$ ,
  
  $dp(a, c) + dp(b, d) \leq dp_{z}(a, c) + dp_{y}(b, d)$
  
  donde
  
  $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).$
  
  Usar la QI sobre $C$ y sobre el estado de la DP para los índices $z+1 \leq y+1 \leq c \leq d$ (por la hipótesis inductiva) produce el resultado deseado.
- Si $z > y$ , la demostración de este caso es simétrica al caso anterior.

Esto completa la demostración del lema.

Ahora, consideremos el siguiente planteo. Tenemos 2 índices $i \leq p \leq q < j$ . Definimos $dp_{k} = C(i, j) + dp(i, k) + dp(k+1, j)$ .

Supongamos que mostramos que

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

Tomando $q = opt(i, j-1)$ , por definición, $dp_{p}(i, j-1) \geq dp_{q}(i, j-1)$ . Por lo tanto, aplicando la desigualdad a todos los $i \leq p \leq q$ , podemos inferir que $opt(i, j)$ es al menos tan grande como $opt(i, j-1)$ , lo que demuestra la primera mitad de la desigualdad.

Ahora, usando la QI sobre algunos índices $p+1 \leq q+1 \leq j-1 \leq j$ , obtenemos

$\begin{aligned} d p (p + 1, j - 1) + d p (q + 1, j) \leq d p (q + 1, j - 1) + d p (p + 1, j) \\ ⟹ & (d p (i, p) + d p (p + 1, j - 1) + C (i, j - 1)) + (d p (i, q) + d p (q + 1, j) + C (i, j)) \\ \leq & (d p (i, q) + d p (q + 1, j - 1) + C (i, j - 1)) + (d p (i, p) + d p (p + 1, j) + C (i, j)) \\ ⟹ & d p_{p} (i, j - 1) + d p_{q} (i, j) \leq d p_{p} (i, j) + d p_{q} (i, j - 1) \\ ⟹ & d p_{p} (i, j - 1) - d p_{q} (i, j - 1) \leq d p_{p} (i, j) - d p_{q} (i, j) \end{aligned}$

Finalmente,

$\begin{aligned} d p_{p} (i, j - 1) \geq d p_{q} (i, j - 1) \\ ⟹ 0 \leq d p_{p} (i, j - 1) - d p_{q} (i, j - 1) \leq d p_{p} (i, j) - d p_{q} (i, j) \\ ⟹ d p_{p} (i, j) \geq d p_{q} (i, j) \end{aligned}$

Esto demuestra la primera parte de la desigualdad, es decir, $opt(i, j-1) \leq opt(i, j)$ . La segunda parte $opt(i, j) \leq opt(i+1, j)$ se puede mostrar con la misma idea, partiendo de la desigualdad $dp(i, p) + dp(i+1, q) ≤ dp(i+1, p) + dp(i, q)$ .

Esto completa la demostración.