Programación dinámica

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

La programación dinámica es un modelo de algoritmo que resuelve un problema complejo dividiéndolo en subproblemas, almacenando los resultados para evitar tener que volver a calcularlos.

Esta programación se utiliza cuando se tienen problemas que se pueden dividir en subproblemas similares, de modo que sus resultados puedan reutilizarse. En su gran mayoría, esta programación se utiliza para la optimización.

Antes de resolver el subproblema disponible, el algoritmo dinámico intentará examinar los resultados de los subproblemas previamente resueltos. Las soluciones de los subproblemas se combinan para lograr la mejor solución.

En lugar de calcular el mismo subproblema una y otra vez, se podrá almacenar su solución en alguna memoria, al encontrarse por primera vez con este subproblema. Cuando aparezca nuevamente durante la solución de otro subproblema, se tomará la solución ya almacenada en la memoria.

Esta es una idea maravillosa para subsanar el tiempo con memoria, donde al utilizar espacio adicional se puede mejorar el tiempo requerido para encontrar una solución.

Características de la programación dinámica

– Subproblemas superpuestos. El problema original puede dividirse en subproblemas que se repiten varias veces.

– Estructura óptima. La solución óptima del problema global se construye a partir de soluciones óptimas de subproblemas. Esto significa que, si resolvemos correctamente las partes pequeñas, podemos construir la solución total.

– Almacenamiento de resultados. La programación dinámica guarda resultados ya calculados para no repetir operaciones. Esto se hace mediante la memoización (guardar resultados durante la recursión) y la tabulación (construir soluciones desde abajo usando tablas).

– Reduce el tiempo de ejecución. Evita cálculos redundantes, por lo que suele transformar algoritmos exponenciales en polinomiales.

– Uso de memoria adicional. A cambio de mejorar velocidad, utiliza más memoria para almacenar resultados parciales. Existe un equilibrio: más memoria, menos tiempo de cálculo.

– Puede implementarse de dos formas. a) Top-Down (Memoización), usa recursión y guarda resultados ya obtenidos. b) Bottom-Up (Tabulación), usa iteración y construye soluciones desde los casos más pequeños.

– Idea fundamental. “No resolver dos veces el mismo problema”.

Ejemplo de programación dinámica

Pasos mínimos para llegar a 1

Para cualquier número entero positivo “e” se puede realizar cualquiera de los tres pasos siguientes.

– Restar 1 del número. (e=e-1).

– Si es divisible por 2, se divide entre 2 (si e%2==0, entonces e= e/2).

– Si es divisible por 3, se divide entre 3 (si e%3==0, entonces e= e/3).

Basado en los pasos anteriores, se debe encontrar la cantidad mínima de estos pasos para llevar e a 1. Por ejemplo:

– Si e= 1, resultado: 0.

– Si e= 4, resultado: 2 (4/2= 2/2= 1).

– Cuando e= 7, resultado: 3 (7-1= 6/3= 2/2= 1).

Enfoque

Se podría pensar en elegir siempre el paso que haga que n sea lo más bajo posible y continuar así, hasta que llegue a 1. Sin embargo, se puede observar que esta estrategia no funciona aquí.

Por ejemplo, si e= 10, los pasos serían: 10/2= 5-1= 4/2= 2/2= 1 (4 pasos). Sin embargo, la forma óptima es: 10-1= 9/3= 3/3 = 1 (3 pasos). Por tanto, se deben probar todos los pasos posibles que puedan hacerse para cada valor que se encuentre de n, eligiendo la cantidad mínima de estas posibilidades.

Todo comienza con la recursividad: F(e)= 1 + min{F(e-1), F(e/2), F(e/3)} si e>1, tomando como caso base: F(1)= 0. Teniendo la ecuación de recurrencia, se puede comenzar a codificar la recursión.

Sin embargo, se puede observar que tiene subproblemas sobrepuestos. Además, la solución óptima para una entrada dada depende de la solución óptima de sus subproblemas.

Como en la memorización, donde las soluciones de los subproblemas que se resuelven se van almacenando para usarlos posteriormente. O como en la programación dinámica, se comienza desde abajo, avanzando hasta el e dado. A continuación, ambos códigos:

Memoización

Programación dinámica de abajo hacia arriba

Ventajas y desventajas de la programación dinámica

Ventajas

• Reduce el tiempo de ejecución. Evita repetir cálculos innecesarios, haciendo los algoritmos mucho más rápidos. Ejemplo: Un problema que tardaría tiempo exponencial puede resolverse en tiempo polinomial.
• Optimiza problemas complejos. Es muy útil en problemas de optimización, rutas mínimas, planificación, combinatoria.
• Reutiliza resultados. Los resultados parciales se almacenan y pueden reutilizarse varias veces. Esto mejora mucho la eficiencia.
• Permite resolver problemas grandes. Problemas difíciles pueden dividirse en partes pequeñas más fáciles de manejar.
• Mejora la eficiencia de algoritmos recursivos. Muchos algoritmos recursivos lentos se vuelven prácticos usando memoización.

Desventajas

• Mayor consumo de memoria. Necesita almacenar resultados intermedios en tablas o arreglos. A veces esto puede ocupar mucha memoria.
• Diseño más complejo. Tiene que Identificar subproblemas, estados y transiciones. Puede ser difícil.
• No todos los problemas sirven. Solo funciona bien cuando existen subproblemas superpuestos y estructura óptima.
• Puede ser difícil de implementar. Algunos algoritmos requieren mucha lógica y planificación antes de programarse.
• Riesgo de usar más recursos de los necesarios. En problemas pequeños, la programación dinámica puede ser innecesaria y más lenta por el manejo extra de memoria.

Aplicaciones de la programación dinámica

La programación dinámica es un método eficaz para resolver problemas que de otro modo podrían parecer extremadamente difíciles de resolver en un tiempo razonable.

Los algoritmos basados ​​en el paradigma de programación dinámica se utilizan en muchas áreas de las ciencias, incluyendo muchos ejemplos en inteligencia artificial, desde la resolución de problemas de planificación hasta el reconocimiento de voz.

• Algoritmos basados en programación dinámica. La programación dinámica es bastante efectiva y sirve muy bien para una amplia gama de problemas. Muchos algoritmos se pueden ver como aplicaciones de algoritmos voraces, como:
  • Serie de números de Fibonacci.
  • Torres de Hanoi.
  • Todos los pares de rutas más cortas por Floyd-Warshall.
  • Problema de la mochila.
  • Programación de proyectos.
  • El camino más corto por Dijkstra.
  • Control de vuelo y control de robótica.
  • Problemas de optimización matemática.
  • Tiempo compartido: programar el trabajo para maximizar el uso de la CPU.
• Serie de números de Fibonacci. Los números de Fibonacci son los números que se encuentran en la secuencia siguiente: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc. En la terminología matemática, la sucesión Fn de los números de Fibonacci está definida por la fórmula de recurrencia: F(n)= F(n -1) + F(n -2), donde F(0)= 0 y F(1)= 1.
• Enfoque de arriba hacia abajo. En este ejemplo, se inicializa con -1 una matriz de búsqueda con todos los valores iniciales. Siempre que se necesite la solución a un subproblema, primero se buscará en esta matriz de búsqueda. Si allí está el valor calculado, entonces se retornará ese valor. En caso contrario, se calculará el resultado para almacenarlo en la matriz de búsqueda y así poderlo reutilizar más adelante.

• Enfoque ascendente. En este caso, para la misma serie de Fibonacci, se calcula primero f(0), luego f(1), f(2), f(3), y así sucesivamente. Así, se estarán construyendo las soluciones de los subproblemas de abajo hacia arriba.

Referencias

1. Introduction to Dynamic Programming. Developer Insider. Recuperado de developerinsider.co.
2. Dynamic Programming in C++. C Programming. Recuperado de cprogramming.com.
3. Idea of Dynamic Programming. Recuperado de afteracademy.com.
4. Tutorial For Dynamic Programming. Recuperado de codechef.com.
5. Dynamic Programming. Recuperado de programiz.com.