Introducción
Contenido
- 1 Introducción
- 2 ¿Qué es la programación dinámica?
- 3 Algoritmo de corte de varilla
- 4 Problema simplificado de la mochila
- 5 El problema de la mochila tradicional
- 6 Distancia de Levenshtein
- 7 Implementación
- 8 Subsecuencia común más larga (LCS)
- 9 Otros problemas que utilizan la programación dinámica
- 10 Conclusión
La programación dinámica se utiliza normalmente para optimizar algoritmos recursivos, ya que tienden a escalar exponencialmente. La idea principal es dividir los problemas complejos (con muchas llamadas recursivas) en subproblemas más pequeños y luego guardarlos en la memoria para que no tengamos que volver a calcularlos cada vez que los usemos.
Para comprender los conceptos de programación dinámica, debemos familiarizarnos con algunos temas:
- ¿Qué es la programación dinámica?
- Algoritmo de corte de varilla
- El problema simplificado de la mochila
- El problema de la mochila tradicional
- Distancia de Levenshtein
- LCS – Subsecuencia común más larga
- Otros problemas que utilizan la programación dinámica
- Conclusión
¿Qué es la programación dinámica?
La programación dinámica es un principio de programación en el que un problema muy complejo se puede resolver dividiéndolo en subproblemas más pequeños. Este principio es muy similar a la recursividad, pero con una diferencia clave, cada subproblema distinto debe resolverse solo una vez.
Para comprender lo que esto significa, primero tenemos que comprender el problema de resolver las relaciones de recurrencia. Cada problema complejo puede dividirse en subproblemas muy similares, esto significa que podemos construir una relación de recurrencia entre ellos.
Echemos un vistazo a un ejemplo con el que todos estamos familiarizados, ¡la secuencia de Fibonacci ! La secuencia de Fibonacci se define con la siguiente relación de recurrencia:
$$
fibonacci (n) = fibonacci (n-1) + fibonacci (n-2)
$$
Nota: Una relación de recurrencia es una ecuación que define de forma recursiva una secuencia en la que el siguiente término es una función de los términos anteriores. La secuencia de Fibonacci es un gran ejemplo de esto.
Entonces, si queremos encontrar el n-thnúmero en la secuencia de Fibonacci, tenemos que conocer los dos números que preceden al n-then la secuencia.
Sin embargo, cada vez que queremos calcular un elemento diferente de la secuencia de Fibonacci, tenemos ciertas llamadas duplicadas en nuestras llamadas recursivas, como se puede ver en la siguiente imagen, donde calculamos Fibonacci (5):
Por ejemplo, si queremos calcular F (5), obviamente necesitamos calcular F (4) y F (3) como requisito previo. Sin embargo, para calcular F (4), necesitamos calcular F (3) y F (2), lo que a su vez requiere que calculemos F (2) y F (1) para obtener F (3) – y así en.
Esto conduce a muchos cálculos repetidos, que son esencialmente redundantes y ralentizan significativamente el algoritmo. Para resolver este problema, nos presentamos a la programación dinámica .
En este enfoque, modelamos una solución como si la resolviéramos de forma recursiva, pero la resolvemos desde cero, memorizando las soluciones a los subproblemas (pasos) que damos para llegar a la cima.
Por lo tanto, para la secuencia de Fibonacci, primero resolvemos y memorizamos F (1) y F (2), luego calculamos F (3) usando los dos pasos memorizados, y así sucesivamente. Esto significa que el cálculo de cada elemento individual de la secuencia es O (1), porque ya conocemos los dos primeros.
Te puede interesar:La declaración try-with-resources en JavaA la hora de resolver un problema mediante programación dinámica, tenemos que seguir tres pasos:
- Determinar la relación de recurrencia que aplica a dicho problema.
- Inicializar los valores iniciales de la memoria / matriz / matriz
- Asegúrese de que cuando hacemos una «llamada recursiva» (accedemos a la solución memorizada de un subproblema) siempre se resuelve de antemano.
Siguiendo estas reglas, echemos un vistazo a algunos ejemplos de algoritmos que utilizan programación dinámica.
Algoritmo de corte de varilla
Comencemos con algo simple:
Dada una varilla de longitud ny una matriz que contiene precios de todas las piezas de tamaño menor que n. Determine el valor máximo que se puede obtener cortando la varilla y vendiendo las piezas.
Solución ingenua
Este problema está prácticamente hecho a medida para la programación dinámica, pero como este es nuestro primer ejemplo real, veamos cuántos incendios podemos iniciar dejando que se ejecute este código:
public class naiveSolution {
static int getValue(int[] values, int length) {
if (length <= 0)
return 0;
int tmpMax = -1;
for (int i = 0; i < length; i++) {
tmpMax = Math.max(tmpMax, values[i] + getValue(values, length - i - 1));
}
return tmpMax;
}
public static void main(String[] args) {
int[] values = new int[]{3, 7, 1, 3, 9};
int rodLength = values.length;
System.out.println("Max rod value: " + getValue(values, rodLength));
}
}
Salida:
Max rod value: 17
Esta solución, aunque correcta, es muy ineficaz . Las llamadas recursivas no se memorizan, por lo que el código deficiente tiene que resolver el mismo subproblema cada vez que hay una única solución superpuesta.
Enfoque dinámico
Utilizando el mismo principio básico anterior, pero agregando memorización y excluyendo llamadas recursivas, obtenemos la siguiente implementación:
public class dpSolution {
static int getValue(int[] values, int rodLength) {
int[] subSolutions = new int[rodLength + 1];
for (int i = 1; i <= rodLength; i++) {
int tmpMax = -1;
for (int j = 0; j < i; j++)
tmpMax = Math.max(tmpMax, values[j] + subSolutions[i - j - 1]);
subSolutions[i] = tmpMax;
}
return subSolutions[rodLength];
}
public static void main(String[] args) {
int[] values = new int[]{3, 7, 1, 3, 9};
int rodLength = values.length;
System.out.println("Max rod value: " + getValue(values, rodLength));
}
}
Salida:
Max rod value: 17
Como podemos ver, las salidas resultantes son las mismas, solo que con diferente complejidad de tiempo / espacio.
Eliminamos la necesidad de llamadas recursivas resolviendo los subproblemas desde cero, utilizando el hecho de que todos los subproblemas anteriores a un problema dado ya están resueltos.
Mejora del rendimiento
Solo para dar una perspectiva de cuánto más eficiente es el enfoque dinámico, intentemos ejecutar el algoritmo con 30 valores.
La solución Naive tardó ~ 5.2 s en ejecutarse, mientras que la solución dinámica tardó ~ 0.000095 s en ejecutarse.
Te puede interesar:Algoritmos de búsqueda en JavaProblema simplificado de la mochila
El problema de la Mochila Simplificada es un problema de optimización, para el que no existe una solución única. La pregunta para este problema sería: «¿Existe una solución?»:
Dado un conjunto de artículos, cada uno con un peso w1, w2… determine el número de cada artículo para poner en una mochila para que el peso total sea menor o igual a un límite dado K.
Así que demos un paso atrás y descubramos cómo representaremos las soluciones a este problema. Primero, almacenemos los pesos de todos los elementos en una matriz W.
A continuación, digamos que hay nelementos y los enumeraremos con números de 1 to n, por lo que el peso del i-thelemento es W[i].
Formaremos una matriz Mde (n+1)x (K+1)dimensiones. M[x][y]correspondiente a la solución del problema de la mochila, pero solo incluyendo los primeros xelementos del arreglo inicial, y con una capacidad máxima de y.
Ejemplo
Digamos que tenemos 3 elementos, siendo las ponderaciones w1=2kg, w2=3kgy w3=4kg.
Utilizando el método anterior, podemos decir que M[1][2]es una solución válida. Esto significa que estamos intentando llenar una mochila con una capacidad de 2 kg con solo el primer artículo de la matriz de pesos ( w1).
Mientras M[3][5]que estamos tratando de llenar una mochila con una capacidad de 5 kg utilizando los primeros 3elementos de la matriz de peso ( w1,w2,w3). Esta no es una solución válida, ya que la estamos sobreajustando.
Inicialización de matriz
Hay 2 cosas a tener en cuenta al completar la matriz:
¿Existe una solución para el subproblema dado (M [x] [y] .existe) Y la solución dada incluye el último elemento agregado a la matriz (M [x] [y] .incluye).
Por lo tanto, la inicialización de la matriz es bastante fácil, M[0][k].existssiempre false, si k > 0, porque no pusimos ningún artículo en una mochila con kcapacidad.
Por otro lado, M[0][0].exists = trueporque la mochila debe estar vacía para empezar desde k = 0, y por lo tanto no podemos meter nada y esta es una solución válida.
Además, podemos decir eso M[k][0].exists = truepero también M[k][0].includes = falsepara todos k.
Nota : El hecho de que exista una solución para un determinado M[x][y], no significa necesariamente que esa combinación en particular sea la solución. En el caso de M[10][0], existe una solución, sin incluir ninguno de los 10 elementos. Por eso, M[10][0].exists = truepero M[10][0].includes = false.
Principio de algoritmo
A continuación, construyamos la relación de recurrencia para M[i][k]con el siguiente pseudocódigo:
if (M[i-1][k].exists == True):
M[i][k].exists = True
M[i][k].includes = False
elif (k-W[i]>=0):
if(M[i-1][k-W[i]].exists == true):
M[i][k].exists = True
M[i][k].includes = True
else:
M[i][k].exists = False
Entonces, la esencia de la solución es dividir el subproblema en dos casos:
- Cuando existe una solución para los primeros
i-1elementos, para la capacidadk - Cuando existe una solución para los primeros
i-1elementos, pero para la capacidadk-W[i]
El primer caso se explica por sí mismo, ya tenemos una solución al problema.
El segundo caso se refiere a conocer la solución para los primeros i-1elementos, pero la capacidad está con exactamente un i-thelemento antes de estar llena, lo que significa que solo podemos agregar un i-thelemento, ¡y tenemos una nueva solución!
Implementación
En esta implementación, para facilitar las cosas, crearemos la clase Elementpara almacenar elementos:
public class Element {
private boolean exists;
private boolean includes;
public Element(boolean exists, boolean includes) {
this.exists = exists;
this.includes = includes;
}
public Element(boolean exists) {
this.exists = exists;
this.includes = false;
}
public boolean isExists() {
return exists;
}
public void setExists(boolean exists) {
this.exists = exists;
}
public boolean isIncludes() {
return includes;
}
public void setIncludes(boolean includes) {
this.includes = includes;
}
}
Ahora podemos sumergirnos en la clase principal:
public class Knapsack {
public static void main(String[] args) {
Scanner scanner = new Scanner (System.in);
System.out.println("Insert knapsack capacity:");
int k = scanner.nextInt();
System.out.println("Insert number of items:");
int n = scanner.nextInt();
System.out.println("Insert weights: ");
int[] weights = new int[n + 1];
for (int i = 1; i <= n; i++) {
weights[i] = scanner.nextInt();
}
Element[][] elementMatrix = new Element[n + 1][k + 1];
elementMatrix[0][0] = new Element(true);
for (int i = 1; i <= k; i++) {
elementMatrix[0][i] = new Element(false);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
elementMatrix[i][j] = new Element(false);
if (elementMatrix[i - 1][j].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(false);
} else if (j >= weights[i]) {
if (elementMatrix[i - 1][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
}
}
System.out.println(elementMatrix[n][k].isExists());
}
}
Lo único que queda es la reconstrucción de la solución, en la clase anterior, sabemos que EXISTE una solución, sin embargo, no sabemos qué es.
Para la reconstrucción usamos el siguiente código:
List<Integer> solution = new ArrayList<>(n);
if (elementMatrix[n][k].isExists()) {
int i = n;
int j = k;
while (j > 0 && i > 0) {
if (elementMatrix[i][j].isIncludes()) {
solution.add(i);
j = j - weights[i];
}
i = i - 1;
}
}
System.out.println("The elements with the following indexes are in the solution:n" + (solution.toString()));
Salida:
Insert knapsack capacity:
12
Insert number of items:
5
Insert weights:
9 7 4 10 3
true
The elements with the following indexes are in the solution:
[5, 1]
Una simple variación del problema de la mochila es llenar una mochila sin optimización de valor, pero ahora con cantidades ilimitadas de cada artículo individual.
Esta variación se puede resolver haciendo un simple ajuste a nuestro código existente:
// Old code for simplified knapsack problem
else if (j >= weights[i]) {
if (elementMatrix[i - 1][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
// New code, note that we're searching for a solution in the same
// row (i-th row), which means we're looking for a solution that
// already has some number of i-th elements (including 0) in it's solution
else if (j >= weights[i]) {
if (elementMatrix[i][j - weights[i]].isExists()) {
elementMatrix[i][j].setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
El problema de la mochila tradicional
Utilizando las dos variaciones anteriores, echemos un vistazo al problema tradicional de la mochila y veamos en qué se diferencia de la variación simplificada:
Te puede interesar:Desarrollo basado en pruebas para las API de Spring BootDado un conjunto de artículos, cada uno con un peso w1, w2… y un valor v1, v2… determinar el número de cada artículo para incluir en una colección de modo que el peso total sea menor o igual a un límite dado ky el valor total es lo más grande posible.
En la versión simplificada, todas las soluciones eran igualmente buenas. Sin embargo, ahora tenemos un criterio para encontrar una solución óptima (también conocida como el valor más grande posible). Tenga en cuenta que esta vez tenemos un número infinito de cada elemento, por lo que los elementos pueden aparecer varias veces en una solución.
En la implementación usaremos la clase anterior Element, con un campo privado agregado valuepara almacenar el mayor valor posible para un subproblema dado:
public class Element {
private boolean exists;
private boolean includes;
private int value;
// appropriate constructors, getters and setters
}
La implementación es muy similar, con la única diferencia de que ahora tenemos que elegir la solución óptima a juzgar por el valor resultante:
public static void main(String[] args) {
// Same code as before with the addition of the values[] array
System.out.println("Insert values: ");
int[] values = new int[n + 1];
for (int i=1; i <= n; i++) {
values[i] = scanner.nextInt();
}
Element[][] elementMatrix = new Element[n + 1][k + 1];
// A matrix that indicates how many newest objects are used
// in the optimal solution.
// Example: contains[5][10] indicates how many objects with
// the weight of W[5] are contained in the optimal solution
// for a knapsack of capacity K=10
int[][] contains = new int[n + 1][k + 1];
elementMatrix[0][0] = new Element(0);
for (int i = 1; i <= n; i++) {
elementMatrix[i][0] = new Element(0);
contains[i][0] = 0;
}
for (int i = 1; i <= k; i++) {
elementMatrix[0][i] = new Element(0);
contains[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
elementMatrix[i][j] = new Element(elementMatrix[i - 1][j].getValue());
contains[i][j] = 0;
elementMatrix[i][j].setIncludes(false);
elementMatrix[i][j].setValue(M[i - 1][j].getValue());
if (j >= weights[i]) {
if ((elementMatrix[i][j - weights[i]].getValue() > 0 || j == weights[i])) {
if (elementMatrix[i][j - weights[i]].getValue() + values[i] > M[i][j].getValue()) {
elementMatrix[i][j].setIncludes(true);
elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() + values[i]);
contains[i][j] = contains[i][j - weights[i]] + 1;
}
}
}
System.out.print(elementMatrix[i][j].getValue() + "/" + contains[i][j] + " ");
}
System.out.println();
}
System.out.println("Value: " + elementMatrix[n][k].getValue());
}
Salida:
Insert knapsack capacity:
12
Insert number of items:
5
Insert weights:
9 7 4 10 3
Insert values:
1 2 3 4 5
0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 1/1 0/0 0/0 0/0
0/0 0/0 0/0 0/0 0/0 0/0 0/0 2/1 0/0 1/0 0/0 0/0 0/0
0/0 0/0 0/0 0/0 3/1 0/0 0/0 2/0 6/2 1/0 0/0 5/1 9/3
0/0 0/0 0/0 0/0 3/0 0/0 0/0 2/0 6/0 1/0 4/1 5/0 9/0
0/0 0/0 0/0 5/1 3/0 0/0 10/2 8/1 6/0 15/3 13/2 11/1 20/4
Value: 20
Distancia de Levenshtein
Otro muy buen ejemplo del uso de la programación dinámica es Editar distancia o Distancia de Levenshtein.
La distancia de Levenshtein para 2 cadenas Ay Bes el número de operaciones atómicas que necesitamos usar para transformar Aen las Bcuales son:
- Eliminación de caracteres
- Inserción de caracteres
- Sustitución de caracteres (técnicamente es más de una operación, pero en aras de la simplicidad, llamémosla operación atómica)
Este problema se maneja resolviendo metódicamente el problema de las subcadenas de las cadenas iniciales, aumentando gradualmente el tamaño de las subcadenas hasta que sean iguales a las cadenas iniciales.
La relación de recurrencia que usamos para este problema es la siguiente:
$$
lev_ {a, b} (i, j) = minbegin {cases}
lev_ {a, b} (i-1, j) +1 \ lev_ {a, b} (i, j-1) +1 \ lev_ {a, b} (i-1, j-1) + c (a_i, b_j) end {cases}
$$
c(a,b)siendo 0 si a==by 1 si a!=b.
Si está interesado en leer más sobre la distancia de Levenshtein, ya lo hemos cubierto en Python en otro artículo: Distancia de Levenshtein y similitud de texto en Python
Implementación
public class editDistance {
public static void main(String[] args) {
String s1, s2;
Scanner scanner = new Scanner(System.in);
System.out.println("Insert first string:");
s1 = scanner.next();
System.out.println("Insert second string:");
s2 = scanner.next();
int n, m;
n = s1.length();
m = s2.length();
// Matrix of substring edit distances
// example: distance[a][b] is the edit distance
// of the first a letters of s1 and b letters of s2
int[][] distance = new int[n + 1][m + 1];
// Matrix initialization:
// If we want to turn any string into an empty string
// the fastest way no doubt is to just delete
// every letter individually.
// The same principle applies if we have to turn an empty string
// into a non empty string, we just add appropriate letters
// until the strings are equal.
for (int i = 0; i <= n; i++) {
distance[i][0] = i;
}
for (int j = 0; j <= n; j++) {
distance[0][j] = j;
}
// Variables for storing potential values of current edit distance
int e1, e2, e3, min;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
e1 = distance[i - 1][j] + 1;
e2 = distance[i][j - 1] + 1;
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
e3 = distance[i - 1][j - 1];
} else {
e3 = distance[i - 1][j - 1] + 1;
}
min = Math.min(e1, e2);
min = Math.min(min, e3);
distance[i][j] = min;
}
}
System.out.println("Edit distance of s1 and s2 is: " + distance[n][m]);
}
}
Salida :
Te puede interesar:Métodos de objetos de Java: toString ()Insert first string:
man
Insert second string:
machine
Edit distance of s1 and s2 is: 3
Subsecuencia común más larga (LCS)
El problema es el siguiente:
Dadas dos secuencias, encuentre la longitud de la subsecuencia más larga presente en ambas. Una subsecuencia es una secuencia que aparece en el mismo orden relativo, pero no necesariamente contigua.
Aclaración
Si tenemos dos cadenas, s1 = "MICE"y s2 = "MINCE", la subcadena común más larga sería «MI» o «CE», sin embargo, la subsecuencia común más larga sería «MICE» porque los elementos de la subsecuencia resultante no tienen que estar en orden consecutivo.
Relación de recurrencia y lógica general
$$
lcs_ {a, b} (i, j) = minbegin {casos}
lcs_ {a, b} (i-1, j) \ lcs_ {a, b} (i, j-1) \ lcs_ {a, b} (i-1, j-1) + c (a_i, b_j) end {cases}
$$
Como podemos ver, solo hay una pequeña diferencia entre la distancia de Levenshtein y LCS, específicamente, en el costo de los movimientos.
En LCS, no tenemos ningún costo por la inserción y eliminación de caracteres, lo que significa que solo contamos el costo por sustitución de caracteres (movimientos diagonales), que tienen un costo de 1 si los dos caracteres de cadena actuales a[i]y b[j]son iguales.
El costo final de LCS es la longitud de la subsecuencia más larga para las 2 cadenas, que es exactamente lo que necesitábamos.
Usando esta lógica, podemos reducir muchos algoritmos de comparación de cadenas a relaciones de recurrencia simples que utilizan la fórmula base de la distancia de Levenshtein.
Implementación
public class LCS {
public static void main(String[] args) {
String s1 = new String("Hillfinger");
String s2 = new String("Hilfiger");
int n = s1.length();
int m = s2.length();
int[][] solutionMatrix = new int[n+1][m+1];
for (int i = 0; i < n; i++) {
solutionMatrix[i][0] = 0;
}
for (int i = 0; i < m; i++) {
solutionMatrix[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int max1, max2, max3;
max1 = solutionMatrix[i - 1][j];
max2 = solutionMatrix[i][j - 1];
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
max3 = solutionMatrix[i - 1][j - 1] + 1;
} else {
max3 = solutionMatrix[i - 1][j - 1];
}
int tmp = Math.max(max1, max2);
solutionMatrix[i][j] = Math.max(tmp, max3);
}
}
System.out.println("Length of longest continuous subsequence: " + solutionMatrix[n][m]);
}
}
Salida :
Length of longest continuous subsequence: 8
Otros problemas que utilizan la programación dinámica
Hay muchos más problemas que se pueden resolver con la programación dinámica, estos son solo algunos de ellos:
- Problema de partición (próximamente)
- Dado un conjunto de números enteros, averigüe si se puede dividir en dos subconjuntos con sumas iguales
- Problema de suma de subconjuntos (próximamente)
- Dado un conjunto de números enteros positivos y una suma de valores, determine si hay un subconjunto del conjunto dado con una suma igual a la suma dada.
- Problema de cambio de moneda (Número total de formas de obtener la denominación de las monedas, próximamente)
- Dado un suministro ilimitado de monedas de denominaciones determinadas, encuentre el número total de formas distintas de obtener el cambio deseado.
- Total de posibles soluciones a la ecuación lineal de
kvariables (próximamente) - Dada una ecuación lineal de
kvariables, cuente el número total de posibles soluciones de la misma. - Encuentre la probabilidad de que un borracho no se caiga de un acantilado ( niños, no intenten esto en casa )
- Dado un espacio lineal que representa la distancia desde un acantilado, y siempre que conozca la distancia de inicio del borracho desde el acantilado y su tendencia a ir hacia el acantilado
py alejarse del acantilado1-p, calcule la probabilidad de su supervivencia. - Mucho mas…
Conclusión
La programación dinámica es una herramienta que puede ahorrarnos mucho tiempo computacional a cambio de una mayor complejidad espacial, dado que algunos de ellos solo van a la mitad (se necesita una matriz para la memorización, pero se usa una matriz en constante cambio).
Esto depende en gran medida del tipo de sistema en el que esté trabajando, si el tiempo de la CPU es valioso, opta por una solución que consume memoria, por otro lado, si su memoria es limitada, opta por una solución que consume más tiempo para una mejor relación de complejidad tiempo / espacio.
Te puede interesar:Métodos de objetos de Java: igual (Objeto)
