Introducción a la programación dinámica: subproblemas superpuestos y subestructura óptima

Publicado: 2021-02-08

Tabla de contenido

Introducción

Supongamos que tenemos una pregunta para resolver el cuadrado de 25. Si nos enfrentamos a esta pregunta por primera vez, entonces podemos resolverla a mano o usando una calculadora. Pero si ya hemos visto esta pregunta antes o la hemos resuelto antes, entonces existe la posibilidad de que podamos responderla rápidamente al memorizarla.

Esto nos lleva a la conclusión de que, si podemos recordarlo, podemos omitirlo la próxima vez. La programación dinámica funciona con un concepto similar, la idea es recordar el resultado de un cálculo y usarlo en el futuro si es necesario.

Este procedimiento simple de programación dinámica lo convierte en un arma poderosa para que un programador conquiste la batalla del código eficiente.

Por ejemplo, supongamos que tenemos una pregunta compleja y siempre pensamos en una solución que divide la pregunta en subproblemas. Pero podemos quedar atrapados en una situación en la que calcularemos un subproblema varias veces. Allí usamos programación dinámica para una solución óptima.

La programación dinámica tiene dos conceptos:

  1. Subproblemas superpuestos
  2. Subestructura óptima

Subproblemas superpuestos

Un ejemplo clásico de comprensión del concepto de subproblema superpuesto es un programa para imprimir la serie de Fibonacci.

La lógica de la serie de Fibonacci viene dada por “fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”. Y la ejecución de esta función sin problemas se puede hacer usando una solución recursiva, con un caso base de fibonacci(0)=0 y fibonacci(1)=1.

public static int fibonacci(int n){
 si (n== 0 || n== 1 )
 devolver n;
 volver fibonacci(n -1 )+fibonacci(n -2 );
 }
 public static void main(String[] args){
 System.out.print( “El cuarto número de Fibonacci es “ +Fibonacci( 4 ));
 }

Digamos que necesitamos imprimir el cuarto dígito de Fibonacci, luego el árbol de recurrencia va como

fibonacci(4)

/ \

fibonacci(3) + fibonacci(2)

/ \ / \

fibonacci(2) + fibonacci(1) fibonacci(1) + fibonacci(0)

/ \

fibonacci(1) + fibonacci(0)

Tenga en cuenta que fibonacci(4) es el quinto dígito de la serie de fibonacci porque comenzamos con fibonacci(0). En el árbol de recursión anterior, podemos ver que fibonacci(2) se repite dos veces. Hemos observado duplicación en un árbol de recursividad de altura 4, ahora imagina que tenemos una llamada recursiva de un número enorme y, posteriormente, habrá un árbol de recursión con una gran altura. Y habrá muchos de estos cálculos duplicados, que se conocen como subproblemas superpuestos.

Tenemos dos métodos para tratar con esta (i) tabulación, (ii) memorización

Vamos a entenderlos recorriendo sus implementaciones.

Memoización

Resolver el problema de Fibonacci utilizando el método de memorización se puede hacer como se muestra a continuación

nota estática int[];
public static int fibonacci(int n){
si(nota[n]!=-1)
devolver memo[n];
si(n==0 || n==1){
nota[n]=n;
devolver n;
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
devolver memo[n];
}
public static void main(String[] args){
memo=nuevo int[5];
para(int i=0;i<=4;i++)
nota[i]=-1;
System.out.println(“El cuarto número de fibonacci es “+fibonacci(4));
}

En el código anterior, estamos creando y manteniendo un archivo de registro o manteniendo una tabla de búsqueda y almacenando los valores de los resultados calculados. Dado que hemos memorizado todos los valores calculados, podemos usarlos en el futuro si es necesario, evitando así cálculos duplicados y subproblemas superpuestos.

Toda la lógica es similar a la solución recursiva, pero la única diferencia que hicimos es que los anotamos en la matriz de notas antes de devolver el valor al método principal. La única restricción de este algoritmo es que necesitamos un espacio extra de tamaño O(n), pero estamos optimizando la solución recursiva anterior.

Tabulación

Este método es un poco diferente a la solución anterior. La memorización sigue la misma solución recursiva. Pero en la tabulación, seguimos una solución iterativa. También se le llama el enfoque de abajo hacia arriba. Veamos la implementación del enfoque de abajo hacia arriba.

public static int fibonacci(int n){
 int tabla[]=nuevo int[n+ 1 ];
 para (int i= 0 ;i<=n;i++){
 si (i== 0 || i== 1 )
 tabla[i]=i;
 más {
 tabla[i]=tabla[i -1 ]+tabla[i -2 ];
 }
 }
 tabla de retorno [n];
 }
 public static void main(String[] args){
 System.out.println( “El cuarto número de Fibonacci es “ +Fibonacci( 4 ));
 }

Como sabemos que fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), en la memorización empezamos con la llamada a la función fibonacci(4), y luego nos dimos cuenta de que no habíamos calculado su valor, así que He calculado sus valores y luego los he almacenado.

Una situación similar se enfrentará con más llamadas recursivas como fibonacci(3), fibonacci(2). Ahora, eso hace que muchas llamadas recursivas esperen en la pila de recursividad, pero de todos modos nos estamos saltando la duplicación de los subproblemas superpuestos.

También tenemos una forma de calcular fibonacci desde 0 hasta el elemento n de forma iterativa y luego devolver el elemento fibonacci n. Esto es lo que hemos implementado en el código anterior. Este código también tiene el mismo requisito de espacio O(n).

Checkout: Habilidades para convertirse en un desarrollador de pila completa

Subestructura óptima

En este concepto, podemos obtener una solución óptima a un problema solo si hemos resuelto de manera óptima sus subproblemas correspondientes.

Y un ejemplo clásico de este concepto es considerar un recorrido entre nodos en un gráfico.

Supongamos que tenemos múltiples raíces desde Telangana hasta Delhi. Y si tenemos la ruta más corta la cual pasa por Nagpur y Gwalior. Luego, la ruta más corta de Nagpur a Delhi Delhi debe pasar por Gwalior. Ahora podemos dividir nuestro problema en subproblemas que son Telangana a Nagpur, Nagpur a Gwalior, Gwalior a Delhi.

Y un ejemplo clásico de esta propiedad es la subsecuencia común más larga en ambas cadenas. Una subsecuencia es diferente de una subcadena. En una subsecuencia, los caracteres no necesitan ser consecuentes en la cadena original.

Entonces la idea es resolverlo resolviendo sus subproblemas de manera óptima. Sea n la longitud de la subsecuencia común más larga.

Si n=LCS(papa, tatuaje), entonces n=LCS(papa, tatuaje)+1 (si los últimos caracteres son iguales), si no, n=máximo(LCS(papa, tatuaje), LCS(papa, tatuaje).

estático int lcs(String s1, String s2, int m, int n ){
 int dp[][] = new int[m+ 1 ][n+ 1 ];
 para (int i= 0 ; i<=m; i++){
 para (int j= 0 ; j<=n; j++){
 si (yo == 0 || j == 0 )
 pd[i][j] = 0 ;
 si no ( s1.charAt (i -1 ) == s2.charAt(j -1 ))
 dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
 demás
 dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 volver dp[m][n];
 }
 public static void main(String[] args){
 System.out.println( “la longitud de la subsecuencia común más larga es “ +lcs( “papa” , “tatuaje” , 6 , 6 ));
 }

En el código anterior, implementamos nuestra lógica usando el método de tabulación y calculamos la longitud de la subsecuencia común más larga presente en ambas cadenas.

Lea también: Salario de desarrollador de pila completa en India

Aprenda cursos de desarrollo de software en línea de las mejores universidades del mundo. Obtenga programas Executive PG, programas de certificados avanzados o programas de maestría para acelerar su carrera.

Conclusión

Ahora que conoce el uso de una de las poderosas técnicas para conquistar la batalla del código eficiente, intente implementar la programación dinámica para otros problemas y comience a fortalecer su capacidad para codificar una pregunta utilizando la programación dinámica.

Para concluir, los cursos de Full Stack Developers son expertos altamente calificados que pueden manejar todo lo relacionado con el desarrollo web. Estas habilidades de Desarrollador Full Stack son lo que los distingue de los Desarrolladores Frontend y Backend.

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

Un programa de computadora contiene mucho código repetitivo. Esto es ineficiente y puede afectar su rendimiento. En este caso, se utiliza la programación dinámica. La programación dinámica es un método para resolver un problema complejo dividiéndolo en subproblemas más simples, resolviendo cada uno de estos subproblemas solo una vez y almacenando sus soluciones usando tablas, que luego se consultan cada vez que ocurre un subproblema similar más adelante. la solución del problema complejo. Los algoritmos de programación dinámica se utilizan para resolver varios tipos de problemas de optimización en los campos de la investigación operativa, la estimación estadística, el reconocimiento de patrones, la inteligencia artificial, el aprendizaje automático, la biología computacional y otros campos.

¿Qué es el subproblema superpuesto en la programación dinámica?

El subproblema superpuesto es un concepto que se usa cuando los subproblemas tienen soluciones que también se usan en otros subproblemas. Esta superposición hace que la misma subtarea se resuelva más de una vez. El problema es encontrar una manera de resolver la subtarea solo una vez y usar esa solución para obtener las soluciones de otros subproblemas. Los algoritmos de programación dinámica resuelven este problema mediante la memorización. La memorización es una técnica en la que almacenamos soluciones a subproblemas para que no tengamos que resolverlos nuevamente.

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

La subestructura óptima implica que la solución óptima a un problema está relacionada con una solución óptima a un problema más pequeño dentro de la misma definición de problema. La subestructura óptima es un requisito adicional necesario para resolver problemas o para demostrar que no hay solución. Con una subestructura óptima, podemos probar muchos problemas NP-hard. Un enfoque general para resolver problemas de DP es utilizar una matriz de programación dinámica para almacenar la solución óptima de los subproblemas. La matriz de programación dinámica se puede utilizar para resolver cualquier problema de DP de subestructura óptima distinto de cero.