Clase de Programación Dinámica de Matemáticas
Introducción
La programación dinámica es una técnica de optimización que se utiliza para abordar problemas en los que hay una función objetivo, frente a la cual hay limitaciones o restricciones. Esta clase explica elfundamento de la programación dinámica y cuales son sus beneficios, junto con una serie de técnicas que pueden ser aplicadas para ayudar a resolver problemas de optimización de manera eficiente.
Teoría
La programación dinámica no es más que una serie de pasos que hay que seguir para conseguir una solución a un problema. Se basa en crear una estructura de datos de forma recursiva que almacena resultados parciales, para no tener que empezar siempre el proceso desde el principio. Esta estructura se diseña en función del problema que queremos resolver y sobre la base de esta estructura se calculan los resultados. Esto permite escalar a problemas de mayor complejidad de manera eficiente.
Los problemas admiten en la mayoría de los casos soluciones óptimas, es decir, un resultado que se aproxima lo máximo posible a la solución óptima. Esto se consigue gracias a que los pasos según los cuales se realiza la programación dinámica están diseñados para acercarse a la solución óptima, obteniendo resultados cada vez más precisos.
Ejemplos prácticos
Ejemplo 1: Resolviendo el problema del viajante
El problema del viajante consiste en encontrar el camino más corto posible desde un punto de origen hasta un punto de destino, recorriendo todos los puntos intermedios. Esto se puede modelar como un grafo, con los puntos de origen y destino como vértices, y todos los puntos intermedios como arcos. La solución óptima será el camino que menor culminación tenga de todos.
La solución óptima se puede encontrar mediante una programación dinámica con la siguiente fórmula:
F(x, y)min = min (F(x – 1, y) + Distancia(x, y), F(x, y – 1) + Distancia(x, y)) , donde:
- F(x, y): Distancia óptima desde el punto de origen hasta el de destino.
- Distancia(x, y): Distancia entre los puntos x e y.
Ejemplo 2: El problema del cambio
El problema del cambio consiste en encontrar la forma más económica de devolver el cambio, utilizando un conjunto de monedas. La monedas deben ser las menos posibles para alcanzar el monto requerido.
La solución óptima se puede encontrar mediante una programación dinámica con la siguiente fórmula:
F(x) = min {F(x – a1) + 1, F(x – a2) + 1, …, F(x – an) + 1} , donde:
- F(x): Número óptimo de monedas para devolver el cambio de x unidades.
- ai: Valor de cada tipo de moneda.
Ejemplo 3: El problema del laberinto
El problema del laberinto consiste en encontrar un camino desde un punto de origen hasta un destino dentro de un laberinto. El camino debe ser el más corto posible. Esto se puede modelar como un grafo con los puntos de origen y destino como vértices, y todos los pasos intermedios como arcos.
La solución óptima se puede encontrar mediante una programación dinámica con la siguiente fórmula:
F(x, y)min = min (F(x – 1, y) + Distancia(x, y), F(x, y – 1) + Distancia(x, y)), donde:
- F(x, y): Longitud del camino óptimo desde el punto de origen hasta el de destino.
- Distancia(x, y): Distancia entre los puntos x e y.