La optimización de Knuth es una herramienta muy poderosa en programación dinámica , que puede usarse para reducir la complejidad temporal de las soluciones principalmente de O(N 3 ) a O(N 2 ) . Normalmente, se usa para problemas que se pueden resolver usando el rango DP, suponiendo que se cumplan ciertas condiciones. En este artículo, primero exploraremos la optimización en sí y luego resolveremos un problema con ella.
Criterios de optimización:
La optimización de Knuth se aplica a problemas de DP con una transición de la siguiente forma:
dp[i][j] = coste[i][j] + min i≤k<j (dp[i][k] + dp[k+1][j])
Además, la función de costo debe satisfacer las siguientes condiciones (para a ≤ b ≤ c ≤ d) –
- Es un monótono en la red de intervalos (MLI) [costo (b, c) ≤ costo (a, d)]
- Satisface la desigualdad del cuadrilátero (QI) [coste(a, c) + coste(b, d) ≤ coste(b, c) + coste(a, d)]
Mejoramiento:
Para una solución que se ejecuta en el tiempo O(N 3 ) , iteraríamos a través de todos los valores de k desde i hasta j-1 . Sin embargo, podemos hacerlo mejor que esto usando la siguiente optimización:
- Definamos otra array además de la array dp: opt[N][N] . Defina opt[i][j] como el valor máximo (o mínimo) de k para el cual dp[i][j] se minimiza en la transición dp.
opt[i][j] = argmin i≤k<j (dp[i][k] + dp[k+1][j]) - La clave para la optimización de Knuth y varias otras optimizaciones en DP, como la optimización Divide and Conquer (que no debe confundirse con el algoritmo divide y vencerás explicado en este artículo ), es la siguiente desigualdad:
optar[i][j-1] ≤ optar[i][j] ≤ optar[i+1][j]
- Esto ayuda porque ahora, para cada transición dp[] para calcular dp[i][j] , solo tenemos que probar los valores de k entre opt[i][j-1] y opt[i+1][j] en su lugar entre i y j-1 . Esto reduce la complejidad del tiempo del algoritmo por un factor lineal, lo que es una mejora significativa.
Prueba de corrección:
Para probar la corrección de este algoritmo, solo necesitamos probar la desigualdad :
opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j] .
Siga la siguiente sección para la prueba de la corrección del algoritmo:
Supuestos: Si cost(i, j) es un MLI y satisface la Desigualdad del Cuadrángulo, entonces dp[i][j] también satisface la desigualdad.
Ahora, considere la siguiente configuración:
- Para i < j , tenemos algunos índices i ≤ p ≤ q < j-1 .
- Sea dp k [i][j] = costo[i][j] + dp[i][k] + dp[k+1][j] .
Si podemos demostrar que:
dp p [i][j-1] ≥ dp q [i][j-1] ⇒ dp p [i][j] ≥ dp q [i][j]
luego establecer q = opt[i][j-1] , quedará claro que opt[i][j] será al menos tanto como opt[i][j-1] , debido a la implicación de lo anterior desigualdad para todos los índices p menores que opt[i][j-1] .
Esto probará que opt[i][j-1] ≤ opt[i][j] .Prueba: Usando la desigualdad del cuadrilátero en la array dp , obtenemos:
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] + costo(i, j-1)) + (dp[i, q] + dp[q+1][j] + costo(i, j))
≤ (dp[i, q] + dp[q+1][j-1] + costo(i, j-1)) + (dp[i, p] + dp[p+1][j] + costo( 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].Por tanto, se demuestra que: dp p [i][j-1] ≥ dp q [i][j-1] ⇒ dp p [i][j] ≥ dp q [i][j]
La segunda parte de la desigualdad (es decir , opt[i][j] ≤ opt[i+1][j] ) se puede mostrar con la misma idea, comenzando con la desigualdad
dp[i][p]+dp[i+1][q] ≤ dp[i][q]+dp[i+1][p] .
La prueba de estas dos desigualdades combinadas da: opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]
Ejemplo:
Dada una array arr[] de N elementos, la tarea es encontrar el costo mínimo para reducir la array a un solo elemento en N-1 operaciones donde en cada operación:
- Elimine los elementos en los índices i e i+1 para algún índice i válido , reemplazándolos con su suma.
- El costo de hacerlo es arr[i] + arr[i+1] , donde arr[] es el estado del arreglo justo antes de la operación.
- Este coste se sumará al coste final.
Ejemplos:
Entrada: arr[] = {3, 4, 2, 1, 7}
Salida: 37
Explicación:
elimine los elementos en el índice 0 y 1. arr[] = {7, 2, 1, 7}, Costo = 3 + 4 = 7
Eliminar los elementos del índice 1 y 2. arr[] = {7, 3, 7}, Costo = 2 + 1 = 3
Elimina los elementos del índice 1 y 2, arr[] = {7, 10}, Costo = 3 + 7 = 10
Elimina los dos últimos elementos. arr[] = {17}, Costo = = 7 + 10 = 17
Costo total = 7 + 3 + 10 + 17 = 37
Este es el costo total mínimo posible para esta array.Entrada: arr[] = {1, 2, 3, 4}
Salida: 19
Explicación:
elimine los elementos de índice 0 y 1. array[] = {3, 3, 4}. Costo = 1 + 2 = 3
Eliminar los elementos de índice 0 y 1. array[] = {6, 4}. Costo = 3 + 3 = 6
Elimine los elementos de índice 0 y 1. array[] = {10}. Costo = 6 + 4 = 10
Costo total = 3 + 6 + 10 = 19.
Este es el mínimo costo posible.
Solución subóptima (usando Range DP): El problema se puede resolver usando la siguiente idea:
- Sea arr[] la array original antes de realizar cualquier modificación.
- Para un elemento de la array que se haya derivado de los índices i a j de a[], el costo de la operación final para formar este único elemento será la suma arr[i] + arr[i+1] + . . . + arr[j] . Sea este valor denotado por la función costo(i, j).
- Para encontrar el costo mínimo para la sección arr[i, i+1, … j] , considere el costo de convertir los pares de subarreglos arr[i, i+1. . . k] & arreglo[k+1, k+2 . . . j]en elementos individuales , y elija el mínimo entre todos los valores posibles de k de iaj-1 (ambos inclusive).
Para implementar la idea anterior:
- La función de costo se puede calcular en tiempo constante con preprocesamiento, utilizando una array de suma de prefijos :
- Calcule la suma de prefijos (digamos almacenados en la array pref[]).
- Entonces, el costo (i, j) se puede calcular como (pref [j] – pref [i-1]).
- Travesía de i = 0 a N-1:
- Traverse j = i+1 a N-1 para generar todo el subarreglo del arreglo principal:
- Resuelva este problema para todos estos subarreglos posibles con la siguiente transición dp:
dp[i][j] = cost(i, j) + min i≤k≤j-1 (dp[i][k] + dp[k+ 1][j]) como se explica en la idea anterior.
- Resuelva este problema para todos estos subarreglos posibles con la siguiente transición dp:
- Traverse j = i+1 a N-1 para generar todo el subarreglo del arreglo principal:
- Aquí dp[i][j] es el costo mínimo de aplicar (j – i) operaciones en el subarreglo arr[i, i+1, . . . j] para convertirlo en un solo elemento.
cost(i, j) indica el costo de la operación final, es decir, el costo de sumar los dos últimos valores para convertir arr[i, i+1, . . ., j] a un solo elemento. - La respuesta final se almacenará en dp[0][N-1] .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum cst
int minCost(int arr[], int N)
{
// Creating the prefix sum array
int pref[N+1], dp[N][N];
pref[0] = 0;
memset(dp, 0, sizeof(dp));
// Loop to calculate the prefix sum
for (int i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
}
// Iterating through all subarrays
// of length 2 or greater
for (int i = N - 2; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
// Cost function = sum of
// all elements in the subarray
int cost = pref[j + 1] - pref[i];
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
// dp transition
dp[i][j]
= min(dp[i][j], dp[i][k]
+ dp[k + 1][j] + cost);
}
}
}
// Return answer
return dp[0][N - 1];
}
// Driver code
int main()
{
int arr[] = { 3, 4, 2, 1, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << minCost(arr, N);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
// Function to find the minimum cst
static int minCost(int[] arr, int N)
{
// Creating the prefix sum array
int pref[] = new int[N+1];
int dp[][] = new int[N][N];
pref[0] = 0;
// Loop to calculate the prefix sum
for (int i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
}
// Iterating through all subarrays
// of length 2 or greater
for (int i = N - 2; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
// Cost function = sum of
// all elements in the subarray
int cost = pref[j + 1] - pref[i];
dp[i][j] = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
// dp transition
dp[i][j]
= Math.min(dp[i][j], dp[i][k]
+ dp[k + 1][j] + cost);
}
}
}
// Return answer
return dp[0][N - 1];
}
// Driver Code
public static void main (String[] args) {
int[] arr = { 3, 4, 2, 1, 7 };
int N = arr.length;
// Function call
System.out.println(minCost(arr, N));
}
}
// This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum cst
static int minCost(int[] arr, int N)
{
// Creating the prefix sum array
int[] pref = new int[N+1];
int[,] dp = new int[N, N];
pref[0] = 0;
// Loop to calculate the prefix sum
for (int i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
}
// Iterating through all subarrays
// of length 2 or greater
for (int i = N - 2; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
// Cost function = sum of
// all elements in the subarray
int cost = pref[j + 1] - pref[i];
dp[i, j] = Int32.MaxValue;
for (int k = i; k < j; k++) {
// dp transition
dp[i, j]
= Math.Min(dp[i,j], dp[i,k]
+ dp[k + 1, j] + cost);
}
}
}
// Return answer
return dp[0, N - 1];
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 3, 4, 2, 1, 7 };
int N = arr.Length;
// Function call
Console.WriteLine(minCost(arr, N));
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the minimum cst
function minCost(arr, N)
{
// Creating the prefix sum array
let pref = new Array(N + 1), dp = new Array(N);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(N);
}
for (let i = 0; i < dp.length; i++) {
for (let j = 0; j < dp[i].length; j++) {
dp[i][j] = 0;
}
}
pref[0] = 0;
// Loop to calculate the prefix sum
for (let i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
}
// Iterating through all subarrays
// of length 2 or greater
for (let i = N - 2; i >= 0; i--) {
for (let j = i + 1; j < N; j++) {
// Cost function = sum of
// all elements in the subarray
let cost = pref[j + 1] - pref[i];
dp[i][j] = Number.MAX_VALUE;
for (let k = i; k < j; k++) {
// dp transition
dp[i][j]
= Math.min(dp[i][j], dp[i][k]
+ dp[k + 1][j] + cost);
}
}
}
// Return answer
return dp[0][N - 1];
}
// Driver code
let arr = [3, 4, 2, 1, 7];
let N = arr.length;
// Function call
document.write(minCost(arr, N));
// This code is contributed by Potta Lokesh
</script>
37
Complejidad temporal: O(N 3 )
Espacio auxiliar: O(N 2 )
Solución óptima (usando la optimización de Knuth) :
Las condiciones para aplicar la optimización de Knuth son válidas para esta pregunta:
cost(i, j) es simplemente la suma de todos los elementos en el subarreglo delimitado por los índices iy j . Además, la función de transición de la programación dinámica coincide con el caso general para aplicar esta técnica.
Siga los pasos mencionados aquí para implementar la idea de la optimización de Knuth:
- Defina la array opt[N][N] y la array dp[][] .
- Ahora, procese los subarreglos en orden creciente de longitud, con el estado inicial dp[i][i] = 0 y opt[i][i] = i ( porque el valor debe ser i para minimizar el valor dp[i][ yo] ).
- Así, cuando llegamos al subarreglo arr[i, . . ., j] , ya se conocen los valores de opt[i][j-1] y opt[i+1][j] . Entonces, solo verifique la condición opt[i][j-1] ≤ k ≤ opt[i+1][j] , para encontrar opt[i][j] y dp[i][j] .
- Aquí también la función de costo se calcula de la misma manera que en el enfoque anterior utilizando la array de suma de prefijos .
Nota: En el código que se proporciona a continuación, se utiliza una forma diferente de recorrer todos los subconjuntos (en lugar de recorrer en orden creciente de longitud). Sin embargo, asegúrese de que opt[i+1][j] y opt[i][j- 1] se calculan antes de dp[i][j].
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum possible cost
int minCost(int arr[], int N)
{
// Creating the prefix sum array
int pref[N + 1], dp[N][N], opt[N][N];
pref[0] = 0;
memset(dp, 0, sizeof(dp));
memset(dp, 0, sizeof(dp));
// Loop to calculate the prefix sum
for (int i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
opt[i][i] = i;
}
// Iterating through all sub-arrays
// of length 2 or greater
for (int i = N - 2; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
// Cost function = sum of
// all elements in the sub-array
int cost = pref[j + 1] - pref[i];
int mn = INT_MAX;
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) {
// Updating opt table
opt[i][j] = k;
// Updating minimum cost
mn = dp[i][k]
+ dp[k + 1][j] + cost;
}
}
// dp transition
dp[i][j] = mn;
}
}
return dp[0][N - 1];
}
// Driver code
int main()
{
int arr[] = { 3, 4, 2, 1, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
cout << minCost(arr, N);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
class GFG
{
// Function to find the minimum possible cost
static int minCost(int arr[], int N)
{
// Creating the prefix sum array
int pref[] = new int[N + 1];
int dp[][] = new int[N][N];
int opt[][] = new int[N][N];
pref[0] = 0;
// Loop to calculate the prefix sum
for (int i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
opt[i][i] = i;
}
// Iterating through all sub-arrays
// of length 2 or greater
for (int i = N - 2; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
// Cost function = sum of
// all elements in the sub-array
int cost = pref[j + 1] - pref[i];
int mn = Integer.MAX_VALUE;
for (int 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) {
// Updating opt table
opt[i][j] = k;
// Updating minimum cost
mn = dp[i][k]
+ dp[k + 1][j] + cost;
}
}
// dp transition
dp[i][j] = mn;
}
}
return dp[0][N - 1];
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 4, 2, 1, 7 };
int N = arr.length;
// Function call
System.out.println(minCost(arr, N));
}
}
// This code is contributed by sanjoy_62.
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the minimum possible cost
static int minCost(int[] arr, int N)
{
// Creating the prefix sum array
int[] pref = new int[N + 1];
int[,] dp = new int[N, N];
int[,] opt = new int[N, N];
pref[0] = 0;
// Loop to calculate the prefix sum
for (int i = 0; i < N; i++) {
pref[i + 1] = pref[i] + arr[i];
opt[i, i] = i;
}
// Iterating through all sub-arrays
// of length 2 or greater
for (int i = N - 2; i >= 0; i--) {
for (int j = i + 1; j < N; j++) {
// Cost function = sum of
// all elements in the sub-array
int cost = pref[j + 1] - pref[i];
int mn = Int32.MaxValue;
for (int 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) {
// Updating opt table
opt[i, j] = k;
// Updating minimum cost
mn = dp[i, k]
+ dp[k + 1, j] + cost;
}
}
// dp transition
dp[i, j] = mn;
}
}
return dp[0, N - 1];
}
// Driver Code
public static void Main()
{
int[] arr = { 3, 4, 2, 1, 7 };
int N = arr.Length;
// Function call
Console.Write(minCost(arr, N));
}
}
// This code is contributed by spevel62.
37
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por omkarbajaj000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA