Comprender la programación dinámica para poder utilizarla de forma eficaz

Este artículo no está relacionado con el desarrollo de producción, pero sí con la programación. Analizaré la programación dinámica (DP) y cómo utilizar la experiencia informática previa de forma eficaz. Espero que les resulte interesante.

Introducción a la programación dinámica

El término programación dinámica fue utilizado por primera vez por el famoso matemático estadounidense, uno de los principales especialistas en tecnología informática, Richard Bellman, allá por los años cincuenta. La programación dinámica (DP) es un método para resolver tareas complejas dividiéndolas en subproblemas más pequeños.

El tipo de problemas que DP puede resolver debe cumplir dos criterios:

1. Subestructura óptima . La programación dinámica significa que la solución de subproblemas más pequeños se puede utilizar para resolver el inicial. La subestructura óptima es la característica principal del paradigma de “divide y vencerás”.

Un ejemplo clásico de implementación es el algoritmo de clasificación por fusión, en el que descomponemos recursivamente el problema en los subproblemas más simples (matrices de tamaño 1), después de lo cual hacemos cálculos basados en cada uno de ellos. Los resultados se utilizan para resolver la siguiente capa (subproblemas más grandes) hasta alcanzar la capa inicial.

2. Subproblemas superpuestos . En informática, se dice que un problema tiene subproblemas superpuestos si el problema se puede dividir en subproblemas que se reutilizan varias veces. En otras palabras, ejecutar el mismo código con los mismos datos de entrada y los mismos resultados. Un ejemplo clásico de este problema es el cálculo de un enésimo elemento en una secuencia de Fibonacci, que veremos a continuación.

Se podría decir que DP es un caso especial del uso del paradigma Divide y Conquistarás, o una versión más compleja del mismo. El patrón es muy adecuado para resolver tareas que involucran combinatoria, donde se calcula una gran cantidad de combinaciones diferentes, pero la cantidad N de elementos es frecuentemente monótona e idéntica.

En los problemas de subestructura óptima y subproblemas de superposición, tenemos numerosos cálculos y operaciones repetidas, si aplicamos un enfoque de fuerza bruta. DP nos ayuda a optimizar la solución y evitar la duplicación del cálculo mediante el uso de dos enfoques principales: memorización y tabulación:

1. La memorización (enfoque de arriba hacia abajo) se implementa mediante recursividad. Una tarea se divide en subproblemas más pequeños, sus resultados se guardan en una memoria y se combinan para resolver el problema original mediante el uso repetido.

• Desventajas: este enfoque utiliza memoria de pila mediante llamadas a métodos recursivos
• Ventajas: Flexibilidad hacia las tareas del PD.

2. La tabulación (enfoque ascendente) se implementa mediante un método iterativo. Los subproblemas desde el más pequeño hasta el inicial se calculan sucesivamente, de forma iterativa.

• Contras: rango de aplicación limitado. Este enfoque requiere una comprensión inicial de toda la secuencia de subproblemas. Pero en algunos problemas esto no es factible.
• Ventajas: uso eficiente de la memoria, ya que todo se ejecuta dentro de una única función.

La teoría puede parecer tediosa e incomprensible; veamos algunos ejemplos.

Problema: secuencia de Fibonacci

Un ejemplo clásico de DP es calcular un enésimo elemento en una secuencia de Fibonacci, donde cada elemento es la suma de los dos anteriores, y el primer y segundo elemento son iguales a 0 y 1.

Por hipótesis, inicialmente nos centramos en la naturaleza de la subestructura óptima, ya que, para calcular un valor, necesitamos encontrar el anterior. Para calcular el valor anterior, necesitamos encontrar el anterior, y así sucesivamente. La naturaleza de las subtareas superpuestas se ilustra en el siguiente diagrama.

Para esta tarea, veremos tres casos:

1. Enfoque sencillo: ¿cuáles son las desventajas?
2. Una solución optimizada que utiliza la memorización
3. Una solución optimizada mediante tabulación

Enfoque sencillo/de fuerza bruta

Lo primero que se le ocurrirá es introducir la recursividad, sumar los dos elementos anteriores y dar su resultado.

 /** * Straightforward(Brute force) approach */ fun fibBruteForce(n: Int): Int { return when (n) { 1 -> 0 2 -> 1 else -> fibBruteForce(n - 1) + fibBruteForce(n - 2) } }

En la pantalla siguiente, puede ver una pila de llamadas a funciones para calcular el quinto elemento de la secuencia.

Tenga en cuenta que la función fib(1) se llama cinco veces y fib(2) tres veces. Las funciones con una firma, con los mismos parámetros, se ejecutan repetidamente y hacen lo mismo. Cuando se aumenta el número N, el árbol aumenta, no linealmente, sino exponencialmente, lo que conduce a una colosal duplicación de cálculos.

Análisis matemático:

Complejidad del tiempo: O (2n),

Complejidad espacial: O(n) -> proporcional a la profundidad máxima del árbol recursivo, ya que este es el número máximo de elementos que pueden estar presentes en la pila de llamadas a funciones implícitas.

Resultado: este enfoque es extremadamente ineficiente. Por ejemplo, se necesitan 1.073.741.824 operaciones para calcular el elemento número 30.

Memorización (enfoque de arriba hacia abajo)

En este enfoque, la implementación no es tan diferente de la solución de “fuerza bruta” anterior, excepto la asignación de memoria. Sea la variable memo, en la que recopilamos los resultados de los cálculos de cualquier función fib() completada en nuestra pila.

Cabe señalar que habría sido suficiente tener una serie de números enteros y hacer referencia a ellos por índice, pero, en aras de la claridad conceptual, se creó un mapa hash.

 /** * Memoization(Top-down) approach */ val memo = HashMap<Int, Int>().apply { this[1] = 0 this[2] = 1 } fun fibMemo(n: Int): Int { if (!memo.containsKey(n)) { val result = fibMemo(n - 1) + fibMemo(n - 2) memo[n] = result } return memo[n]!! }

Centrémonos nuevamente en la pila de llamadas a funciones:

• La primera función completada que escribe el resultado en la nota es la fib(2) resaltada. Devuelve el control al fib(3) resaltado.
• El fib(3) resaltado encuentra su valor después de resumir los resultados de las llamadas fib(2) y fib(1) , ingresa su solución en la nota y devuelve el control a fib(4) .
• Hemos llegado a la etapa de reutilizar experiencias anteriores: cuando el control vuelve a fib(4) , la llamada a fib(2) espera su turno en él. fib(2) a su vez, en lugar de llamar ( fib(1) + fib(0) ), utiliza toda la solución terminada del memo y la devuelve inmediatamente.
• fib(4) se calcula y devuelve el control a fib(5) , que solo tiene que iniciar fib(3) . En la última analogía, fib(3) devuelve inmediatamente un valor del memo sin cálculos.

Podemos observar una reducción en el número de llamadas a funciones y cálculos. Además, cuando N aumenta, habrá exponencialmente menos reducciones.

Análisis matemático:

Complejidad del tiempo: O(n)

Complejidad espacial: O (n)

Resultado: existe una clara diferencia en la complejidad asintótica. Este enfoque la ha reducido a ser lineal en el tiempo, en comparación con la solución primitiva, y no la ha aumentado en memoria.

Tabulación (enfoque ascendente)

Como se mencionó anteriormente, este enfoque implica un cálculo iterativo desde un subproblema más pequeño a uno más grande. En el caso de Fibonacci, los “subproblemas” más pequeños son el primer y segundo elemento de la secuencia, 0 y 1, respectivamente.

Sabemos muy bien cómo se relacionan los elementos entre sí, lo que se expresa en la fórmula: fib(n) = fib(n-1) + fib(n-2) . Como conocemos los elementos anteriores, podemos calcular fácilmente el siguiente, el siguiente, y así sucesivamente.

Resumiendo los valores que conocemos, podemos encontrar el siguiente elemento. Implementamos esta operación cíclicamente hasta encontrar el valor deseado.

 /** * Tabulation(Bottom-up) approach fun fibTab(n: Int): Int { var element = 0 var nextElement = 1 for (i in 2 until n) { val newNext = element + nextElement element = nextElement nextElement = newNext } return nextElement }

Análisis matemático:

Complejidad del tiempo: O(n)

Complejidad espacial: O(1)

Resultado: este enfoque es tan efectivo como la memorización en términos de velocidad, pero consume una cantidad constante de memoria.

Problema: árboles binarios únicos

Veamos un problema más complejo: necesitamos encontrar el número de todos los árboles binarios estructuralmente únicos que se pueden crear a partir de N nodos.

Un árbol binario es una estructura de datos jerárquica, en la que cada nodo tiene no más de dos descendientes. Como regla general, el primero se denomina nodo padre y tiene dos hijos: el hijo izquierdo y el hijo derecho.

Supongamos que necesitamos encontrar una solución para N = 3. Hay 5 árboles estructuralmente únicos para los tres nodos. Podemos contarlas mentalmente, pero si se aumenta la N, las variaciones aumentarían enormemente y visualizarlas en nuestra cabeza sería imposible.

Esta tarea podría atribuirse a la combinatoria. Averigüemos qué combinaciones se pueden formar y cómo podemos encontrar un patrón para su formación.

1. Cada árbol comienza desde el nodo superior (Vértice del Árbol). Luego, el árbol se expande en profundidad.
2. Cada nodo es el comienzo de un nuevo árbol hijo (subárbol), como se muestra en la pantalla. El subárbol izquierdo es de color verde y el derecho, rojo. Cada uno tiene su propio vértice.

Veamos un ejemplo de una tarea, donde N = 6 a nivel conceptual. Llamaremos a nuestra función de cálculo numOfUniqueTrees(n: Int) .

En nuestro ejemplo, se dan 6 nodos, uno de los cuales, según el principio mencionado anteriormente, forma el vértice del árbol y los otros 5, el resto.

A partir de ahora interactuamos con los nodos restantes. Esto se puede hacer de varias maneras. Por ejemplo, utilizando los cinco nodos para formar el subárbol izquierdo o enviando los cinco al subárbol derecho. O dividiendo los nodos en dos: 2 a la izquierda y 3 a la derecha (ver pantalla a continuación), tenemos un número limitado de variantes de este tipo.

Para lograr el resultado numOfUniqueTrees(6) , debemos considerar todas las variantes para distribuir nuestros nodos. Se muestran en la tabla:

La tabla muestra 6 distribuciones diferentes de los nodos. Si encontramos cuántos árboles únicos se pueden generar para cada distribución y los sumamos, lograremos nuestro resultado final.

¿Cómo encontrar la cantidad de árboles únicos para su distribución?

Tenemos dos parámetros: Nodos izquierdos y Nodos derechos (columnas izquierda y derecha en la tabla).

El resultado será igual a: numOfUniqueTrees(leftNodes) * numOfUniqueTrees(rightNodes) .

¿Por qué? A la izquierda tendremos X árboles únicos y para cada uno podremos poner Y variaciones únicas de árboles a la derecha. Los multiplicamos para obtener el resultado.

Entonces, descubramos las variaciones para la primera distribución (5 a la izquierda, 0 a la derecha)

numOfUniqueTrees(5) * numOfUniqueTrees(0) , ya que no tenemos nodos a la derecha. El resultado es numOfUniqueTrees(5) : el número de subárboles únicos a la izquierda con una derecha constante.

Calculando numOfUniqueTrees(5) .

Ahora tenemos el subproblema más pequeño. Operaremos con él como lo hicimos con el más grande. En esta etapa, las características de las tareas del PD son claras: subestructura óptima y comportamiento recursivo.

Un nodo (el nodo verde) se envía al vértice. Distribuimos los (cuatro) nodos restantes de una manera análoga a la experiencia anterior (4:0), (3:1), (2:2), (1:3), (0:4).

Calculamos la primera distribución (4:0). Es igual a numOfUniqueTrees(4) * numOfUniqueTrees(0) -> numOfUniqueTrees(4) por analogía anterior.

Calculando numOfUniqueTrees(4) . Si asignamos un nodo al vértice, nos quedan 3.

Distribuciones (3:0), (2:1), (1:2), (0:3).

Para 2 nodos sólo hay dos árboles binarios únicos, para 1: uno. Anteriormente ya mencionamos que existen 5 variaciones de árboles binarios únicos para tres nodos.

Como resultado, las distribuciones (3:0), (0:3) son iguales a 5, (2:1), (1:2) — 2. Si sumamos 5 + 2 + 2 + 5, obtenemos 14 numOfUniqueTrees(4) = 14.

Ingresemos el resultado del cálculo en la nota variable según la experiencia de memorización. Siempre que necesitemos encontrar variaciones para cuatro nodos, no las calcularemos nuevamente, sino que reutilizaremos la experiencia anterior.

Volvamos al cálculo (5:0), que es igual a la suma de las distribuciones (4:0), (3:1), (2:2), (1:3), (0:4). Sabemos que (4:0) = 14. Pasemos a la nota, (3:1) = 5, (2:2) = 4 (2 variaciones a la izquierda * 2 a la derecha), (1:3) = 5, (0:4) = 14. Si los sumamos, obtenemos 42, numOfUniqueTrees(5) = 42.

Volvamos al cálculo de numOfUniqueTrees(6) , que es igual a la suma de las distribuciones.

(5:0) = 42, (4:1) = 14, (3:2) =10 (5 izquierda * 2 derecha), (2:3) = 10, (1:4) = 14, (0: 5) = 42. Si los sumamos, obtenemos 132, numOfUniqueTrees(5) = 132 .

¡Tarea resuelta!

Resultado: observemos los subproblemas superpuestos en la solución donde N = 6. En la solución sencilla, numOfUniqueTrees(3) se llamaría 18 veces (pantalla a continuación). Al aumentar N, las repeticiones del mismo cálculo serían mucho mayores.

Destaco que la cantidad de árboles únicos para (5 izquierda, 0 derecha) y (0 izquierda, 5 derecha) será la misma. Sólo en un caso serán de izquierda y en el otro de derecha. Esto también funciona para (4 izquierda, 1 derecha) y (1 izquierda, 4 derecha).

La memorización, como enfoque de programación dinámica, nos ha permitido optimizar la solución para una tarea tan compleja.

Implementación

 class Solution { fun calculateTees(n: Int, memo:Array<Int?>): Int { var treesNum = 0 if(n < 1) return 0 if(n == 2) return 2 if(n == 1) return 1 if(memo[n]!=null) return memo[n]!! for (i in 1..n){ val leftSubTrees = calculateTees( i - 1, memo) val rightSubTrees = calculateTees(n - i, memo) treesNum += if(leftSubTrees>0 && rightSubTrees>0){ leftSubTrees*rightSubTrees } else leftSubTrees+leftSubTrees } memo[n] = treesNum return treesNum } } 

Conclusión

En algunos casos, resolver tareas mediante Programación Dinámica puede ahorrar una gran cantidad de tiempo y hacer que el algoritmo funcione con la máxima eficiencia.

Gracias por leer este artículo hasta el final. Estaré encantado de responder a tus preguntas.