Breaking

Post Top Ad

Your Ad Spot

viernes, 14 de junio de 2019

Programación dinámica en Java

Introducción

La programación dinámica se utiliza normalmente para optimizar los 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 usamos.
Para entender los conceptos de la programación dinámica necesitamos conocer algunos temas:

¿Qué es la programación dinámica?

La programación dinámica es un principio de programación donde un problema muy complejo puede resolverse dividiéndolo en subproblemas más pequeños. Este principio es muy similar a la recursión, pero con una diferencia clave, cada subproblema distinto debe resolverse solo una vez .
Para entender lo que esto significa, primero tenemos que entender el problema de resolver relaciones de recurrencia. Cada problema complejo se puede dividir 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 :
Fyosegundoonorteunadodoyo(norte)=Fyosegundoonorteunadodoyo(norte-1)+Fyosegundoonorteunadodoyo(norte-2)
Nota: Una relación de recurrencia es una ecuación que define recursivamente 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 saber los dos números que preceden al n-thde 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) :
secuencia Fibonacci
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), que a su vez nos obliga a calcular F (2) y F (1) para obtener F (3), y así en.
Esto lleva 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 fuéramos a resolverla recursivamente, pero la resolvemos desde el principio, memorizando las soluciones a los subproblemas (pasos) que tomamos 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.
Al resolver un problema utilizando la programación dinámica, tenemos que seguir tres pasos:
  • Determinar la relación de recurrencia que se aplica a dicho problema.
  • Inicializa los valores iniciales de la memoria / matriz / matriz.
  • Asegúrese de que cuando hacemos una "llamada recursiva" (acceda a la solución memorizada de un subproblema) siempre se resuelva de antemano
Siguiendo estas reglas, echemos un vistazo a algunos ejemplos de algoritmos que utilizan la programación dinámica.

Algoritmo de corte de varilla

Comencemos con algo simple:
Dada una vara de longitud ny una matriz que contiene precios de todas las piezas de tamaño más pequeño nDetermine el valor máximo que se puede obtener cortando la barra y vendiendo las piezas.

Solución ingenua

Este problema está prácticamente hecho a la medida para la programación dinámica, pero como este es nuestro primer ejemplo real, veamos cuántos disparos podemos comenzar al ejecutar 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 altamente ineficiente . Las llamadas recursivas no se memorizan, por lo que el código deficiente tiene que resolver el mismo subproblema cada vez que hay una sola solución superpuesta.

Enfoque dinámico

Utilizando el mismo principio básico de arriba, pero agregando memoria 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, los resultados resultantes son los mismos, solo que con diferente complejidad de tiempo / espacio.
Eliminamos la necesidad de llamadas recursivas resolviendo los subproblemas desde el principio, utilizando el hecho de que todos los subproblemas anteriores a un problema dado ya están resueltos.

Aumento 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 ingenua tomó ~ 5.2s para ejecutarse mientras que la solución dinámica tomó ~ 0.000095s para ejecutarse.

Problema de mochila simplificado

El problema de la mochila simplificada es un problema de optimización, para el cual no hay unasolución única . La pregunta para este problema sería: "¿Existe alguna solución?":
Dado un conjunto de artículos, cada uno con un peso w1w2... determine el número de cada artículo para colocar en una mochila de modo que el peso total sea menor o igual a un límite dado K.
Entonces, demos un paso atrás y averigüemos cómo vamos a representar 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 1 to n, por lo que el peso del i-thelemento es W[i].
Formaremos una matriz Mde (n+1)(K+1)dimensiones. M[x][y]correspondiente a la solución del problema de la mochila, pero solo incluye los primeros xelementos de la matriz inicial y con una capacidad máxima de y.

Ejemplo

Supongamos que tenemos 3 elementos, siendo las ponderaciones w1=2kgw2=3kgw3=4kg.
Utilizando el método anterior, podemos decir que M[1][2]es una solución válida. Esto significa que estamos tratando de llenar una mochila con una capacidad de 2 kg con solo el primer elemento de la matriz de peso ( 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 adaptando.

Inicialización de la matriz

Hay dos cosas a tener en cuenta al rellenar 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] .includes).
Por lo tanto, la inicialización de la matriz es bastante fácil, M[0][k].existses siempre false, si k > 0, porque no pusimos ningún artículo en una mochila con kcapacidad.
Por otro lado, M[0][0].exists = truedebido a que la mochila debe estar vacía para empezar desde entonces k = 0, y por lo tanto no podemos poner 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 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, vamos a construir 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
Así que la esencia de la solución es dividir el subproblema en dos casos:
  1. Cuando existe una solución para los primeros i-1elementos, para la capacidad.k
  2. Cuando existe una solución para los primeros i-1elementos, pero para la capacidad.k-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 es exactamente con un i-thelemento menos que estar lleno, 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 una solución EXISTE , sin embargo, no sabemos lo que es.
Para la reconstrucción utilizamos 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 ajuste simple 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 ambas variaciones anteriores, ahora echemos un vistazo al problema de la mochila tradicional y veamos en qué se diferencia de la variación simplificada:
Dado un conjunto de elementos, cada uno con un peso w1w2... y un valor v1v2... determina el número de cada artículo que se 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, cada solución individual era igual de buena. Sin embargo, ahora tenemos un criterio para encontrar una solución óptima (también conocido como el mayor valor 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 utilizaremos 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  

Levenshtein Distancia

Otro muy buen ejemplo del uso de la programación dinámica es Editar distancia o la Distancia Levenshtein .
La distancia de Levenshtein para 2 cadenas ABes el número de operaciones atómicas que necesitamos usar para transformarnos Aen las Bque son:
  1. Eliminación de caracteres
  2. Inserción de personajes
  3. Sustitución de caracteres (técnicamente es más de una operación, pero para simplificar, llamémosla operación atómica)
Este problema se maneja resolviendo metódicamente el problema para 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 utilizamos para este problema es la siguiente:
lmivuna,segundo(yo,j)=metroyonorte{lmivuna,segundo(yo-1,j)+1lmivuna,segundo(yo,j-1)+1lmivuna,segundo(yo-1,j-1)+do(unayo,segundoj)
c(a,b)siendo 0 si a==b, y 1 si a!=b.
Si está interesado en leer más sobre Levenshtein Distance, ya lo tenemos cubierto en Python en otro artículo: Levenshtein Distance y Text Similarity in 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 :
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, encuentra 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"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

ldosuna,segundo(yo,j)=metroyonorte{ldosuna,segundo(yo-1,j)ldosuna,segundo(yo,j-1)ldosuna,segundo(yo-1,j-1)+do(unayo,segundoj)
Como podemos ver, solo hay una ligera diferencia entre la distancia Levenshtein y la LCS, específicamente, en el costo de los movimientos.
En LCS, no tenemos ningún coste para la inserción y el borrado de caracteres carácter, lo que significa que solo cuenta el costo de la sustitución de caracteres (movimientos diagonales), que tienen un coste de 1 si los dos caracteres de cadenas de caracteres a[i]b[j]son los mismos.
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 una gran cantidad de algoritmos de comparación de cadenas a relaciones de recurrencia simples que utilizan la fórmula base de la distancia 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 enteros, averigüe si se puede dividir en dos subconjuntos con sumas iguales
  • Subconjunto del problema de suma ( próximamente )
    • Dado un conjunto de enteros positivos y una suma de valores, determine si hay un subconjunto del conjunto dado con suma igual a la suma dada.
  • Problema de cambio de moneda (número total de formas de obtener la denominación de monedas, próximamente )
    • Dado un suministro ilimitado de monedas de denominaciones dadas, encuentre el número total de formas distintas para obtener el cambio deseado.
  • Total de soluciones posibles para 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.
  • Encuentra la probabilidad de que un borracho no se caiga de un precipicio ( Niños, no intentes esto en casa )
    • Dado un espacio lineal que representa la distancia desde un acantilado, y siempre que sepa la distancia de inicio del borracho desde el acantilado, y su tendencia a ir hacia el acantilado py alejarse del acantilado 1-p, calcule la probabilidad de su supervivencia.
  • Mucho mas...

Conclusión

La programación dinámica es una herramienta que nos puede ahorrar una gran cantidad de tiempo de cómputo a cambio de una mayor complejidad de espacio , ya que algunos de ellos solo van a la mitad (se necesita una matriz para la memorización, pero se utiliza una matriz en constante cambio).
Esto depende en gran medida del tipo de sistema en el que esté trabajando; si el tiempo de CPU es valioso, opta por una solución que consuma memoria; por otra parte, si su memoria es limitada, opta por una solución más lenta para una mejor relación tiempo / espacio de complejidad.

No hay comentarios.:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Post Top Ad

Your Ad Spot

Páginas