La optimización de Knuth en programación dinámica se aplica específicamente para problemas óptimos de árbol binario. (Lea sobre los árboles de búsqueda binarios óptimos en la sección del árbol de búsqueda binaria del volumen 3 “El arte de la programación de computadoras” de Knuth para más detalles)
Es aplicable en el caso donde la recurrencia es en la forma:
dp [ i ] [ j ] = mini < k < j { dp [ i ] [ k ] + dp [ k ] [ j ]} + C [ i ] [ j ]
La condición suficiente para la aplicabilidad es:
A [ i , j – 1] ≤ A [ i , j ] ≤ A [ i + 1, j ]
- ¿Cuál es el significado de determinista y no determinista en informática?
- ¿Qué opinas sobre un mundo donde todos puedan codificar y conocer decentemente la informática?
- ¿Cuáles son algunos problemas no resueltos en la conversión de texto a imagen?
- Escritores y autores: ¿Cuáles son sus situaciones típicas al obtener nuevas ideas o un mensaje "clics" en la mente?
- ¿Cuál es la mejor manera de entrevistar a los candidatos de doctorado de CS que no codifican con tanta frecuencia?
Dónde,
- A [ i ] [ j ]: la k más pequeña que da una respuesta óptima, por ejemplo en:
- dp [ i ] [ j ] = dp [ i – 1] [ k ] + C [ k ] [ j ]
- C [ i ] [ j ] – función de costo dada
- Además, es importante tener en cuenta que Knuth Optimization es aplicable si: C [ i ] [ j ] cumple las siguientes 2 condiciones:
- desigualdad cuadrangular :
- monotonicidad :
No sabía sobre la condición de desigualdad del cuadrilátero hasta que lo leí @ Optimizaciones de programación dinámica – Codeforces
La aplicación de esta optimización reduce la complejidad del tiempo de O (n ^ 3) a O (n ^ 2) y es útil para resolver un grupo particular de problemas, como:
Problemas :: Mostrar problema
La optimización de Knuths funciona para la optimización en subcadenas para las cuales el punto medio óptimo depende monótono de los puntos finales. Supongamos que mid [l, r] es el primer punto medio para la subcadena (l, r) que da un resultado óptimo. Se puede demostrar que mid [l, r-1] <= mid [l, r] <= mid [l + 1, r] – esto significa monotonicidad de mid por l y r.
La aplicación de esta optimización reduce la complejidad del tiempo de O (k ^ 3) a O (k ^ 2) porque con s fijo (longitud de subcadena) tenemos m_right (l) = mid [l + 1] [r] = m_left (l + 1 ) Es por eso que los bucles L y M anidados requieren no más de 2k iteraciones en general.
for (int s = 0; s<=k; s++) //s - length(size) of substring for (int l = 0; l+s<=k; l++) { //l - left point int r = l + s; //r - right point if (s < 2) { res[l][r] = 0; //DP base - nothing to break mid[l][r] = l; //mid is equal to left border continue; } int mleft = mid[l][r-1]; //Knuth's trick: getting bounds on m int mright = mid[l+1][r]; res[l][r] = 1000000000000000000LL; for (int m = mleft; m tres) { //relax current solution res[l][r] = tres; mid[l][r] = m; } } } int64 answer = res[0][k]; Fuente de ejemplo: Foros de TopCoder
