Programación dinámica para niños

En informática, la programación dinámica es una forma inteligente de resolver problemas complejos. Imagina que tienes un gran rompecabezas. En lugar de intentar resolverlo todo de golpe, la programación dinámica te ayuda a dividirlo en piezas más pequeñas. Lo especial es que algunas de esas piezas se repiten, y si ya resolviste una, ¡no necesitas resolverla de nuevo! Simplemente guardas la solución y la usas cuando la necesites.

El matemático Richard Bellman inventó esta idea en 1953. La programación dinámica se usa para encontrar la mejor solución a problemas que se pueden dividir en pasos y que tienen partes que se repiten.

¿Qué es la Programación Dinámica?

La programación dinámica se basa en dos ideas principales para hacer los programas más rápidos y eficientes:

Subestructuras Óptimas: Resolver el Rompecabezas por Partes

Una "subestructura óptima" significa que si encuentras la mejor solución para una parte pequeña de un problema, esa solución te ayudará a encontrar la mejor solución para el problema completo.

Por ejemplo, piensa en encontrar el camino más corto entre dos puntos en un mapa. Si sabes cuál es el camino más corto desde tu punto de partida hasta cada una de las ciudades cercanas, puedes usar esa información para elegir el mejor camino general.

Para resolver problemas con subestructuras óptimas, se siguen estos pasos:

• Divide el problema grande en partes más pequeñas.
• Resuelve cada una de esas partes de la mejor manera posible.
• Usa las soluciones de las partes pequeñas para construir la mejor solución para el problema original.

Las partes más pequeñas se siguen dividiendo hasta que llegas a un punto donde la solución es muy sencilla.

Subproblemas Superpuestos: No Repitas el Trabajo

Decir que un problema tiene "subproblemas superpuestos" significa que la misma parte pequeña del problema se usa varias veces para resolver diferentes partes más grandes.

Un ejemplo clásico es la sucesión de Fibonacci. Para calcular un número de Fibonacci, necesitas sumar los dos números anteriores. Por ejemplo, para calcular el número 5 de Fibonacci (F₅), necesitas F₄ y F₃. A su vez, para F₄ necesitas F₃ y F₂, y para F₃ necesitas F₂ y F₁. ¡Fíjate que F₂ se necesita varias veces!

Si no eres cuidadoso, tu programa podría calcular F₂ una y otra vez, lo que gasta tiempo y energía. La programación dinámica evita esto.

Memoización: Guardar las Soluciones

Para no repetir cálculos, la programación dinámica usa una técnica llamada "memoización". Esto significa que, cada vez que resuelves una parte pequeña del problema, guardas su solución. Si más tarde necesitas resolver esa misma parte de nuevo, simplemente buscas la solución que ya tienes guardada en lugar de calcularla otra vez.

Es como tener una lista de respuestas a preguntas que ya has contestado. Si alguien te hace la misma pregunta, no tienes que pensar de nuevo, solo miras tu lista.

En resumen, la programación dinámica usa:

• Subproblemas superpuestos: Partes del problema que se repiten.
• Subestructuras óptimas: Las soluciones de las partes pequeñas ayudan a resolver el problema grande.
• Memoización: Guardar las soluciones para reutilizarlas.

¿Cómo se Aplica la Programación Dinámica?

Hay dos formas principales de aplicar la programación dinámica:

• Top-down (De arriba hacia abajo): Empiezas con el problema grande y lo divides en subproblemas. Resuelves estos subproblemas y guardas sus soluciones (memoización). Si un subproblema ya está resuelto, usas la solución guardada. Es una combinación de memoización y recursión (cuando una función se llama a sí misma).
• Bottom-up (De abajo hacia arriba): Empiezas resolviendo los problemas más pequeños y sencillos primero. Luego, usas esas soluciones para construir las soluciones de problemas un poco más grandes, y así sucesivamente, hasta que resuelves el problema original. Este método a veces es más eficiente en el uso de memoria.

Origen de la Programación Dinámica

El término "programación dinámica" fue creado por Richard Bellman en la década de 1950. Él trabajaba en la corporación RAND y buscaba formas de optimizar procesos. Bellman eligió la palabra "dinámica" porque quería analizar cómo las variables de los problemas cambiaban con el tiempo.

La idea de Bellman era descomponer un problema grande en subproblemas más fáciles de manejar. Las soluciones de un subproblema se usan como punto de partida para el siguiente, hasta que el problema completo está resuelto. Bellman también desarrolló el "Principio de Optimalidad", que dice que las decisiones futuras no dependen de cómo llegaste al estado actual, solo del estado actual en sí.

Características Clave

La programación dinámica se usa cuando un problema tiene estas características:

• Se puede dividir en etapas, y cada etapa requiere una decisión.
• Cada etapa tiene diferentes "estados" posibles, que son las condiciones en las que se encuentra el sistema.
• La decisión en una etapa cambia el estado actual a un nuevo estado para la siguiente etapa.
• El objetivo es encontrar la mejor secuencia de decisiones para todas las etapas.
• La mejor decisión en una etapa solo depende del estado actual, no de cómo se llegó a ese estado (Principio de Optimalidad).
• Existe una forma de relacionar la mejor solución de una etapa con la mejor solución de la etapa siguiente.
• Para resolverlo, a menudo se empieza desde el final y se trabaja hacia atrás, etapa por etapa, hasta encontrar la mejor solución desde el principio.

Ejemplo: La Sucesión de Fibonacci

Vamos a ver cómo la programación dinámica ayuda con la sucesión de Fibonacci. Esta sucesión se define así:

• Fib(0) = 0
• Fib(1) = 1
• Fib(n) = Fib(n-1) + Fib(n-2) para n mayor que 1

Si intentamos calcular Fib(5) sin programación dinámica, el programa haría muchos cálculos repetidos:

• fib(5)
• fib(4) + fib(3)
• (fib(3) + fib(2)) + (fib(2) + fib(1))
• ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
• (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Como puedes ver, fib(2) se calcula varias veces. Esto es ineficiente.

Con la programación dinámica (usando el enfoque Bottom-up y memoización), podemos guardar los resultados en una tabla:

FUNC Fibonacci (↓n: NATURAL): NATURAL VARIABLES tabla: ARRAY [0..n] DE NATURALES i: NATURAL INICIO tabla[0] := 0 tabla[1] := 1 PARA i = 2 HASTA n HACER tabla[i] := tabla[i-1] + tabla[i-2] FIN PARA DEVOLVER tabla[n] FIN

Este programa calcula cada número de Fibonacci una sola vez y guarda el resultado. Así, cuando necesita un número que ya calculó, simplemente lo busca en la tabla. Esto hace que el cálculo sea mucho más rápido y eficiente.

Ejercicios Resueltos con Programación Dinámica

Aquí tienes algunos problemas que se pueden resolver usando programación dinámica:

• Ejecución de n tareas en tiempo mínimo en un sistema de dos procesadores A y B
• Programas en disco
• Problema de los sellos con programación dinámica
• Problema de la mochila
• Problema del producto de una secuencia de matrices con programación dinámica
• Problema de las monedas con programación dinámica
• Camino de coste mínimo entre dos nodos de un grafo dirigido
• Problema de la división de peso
• Problema de las vacas con programación dinámica
• Problema del Cambio de Palabra Programación Dinámica en JAVA
• Problema de buscar la subsecuencia común más larga entre dos cadenas

Véase también

En inglés: Dynamic programming Facts for Kids