Programación dinámica
Método para resolver problemas complejos dividiéndolos en subproblemas más pequeños, guardando sus soluciones para no tener que recalcularlas.
- Año
- 1953
- Protagonistas
- Richard Bellman
- Sección
- Informática
Historia
La programación dinámica es un método para resolver problemas complejos que se pueden descomponer en partes más sencillas. Su idea central es que, si conocemos la mejor solución de cada parte, podemos combinarlas para obtener la mejor solución del conjunto. Se usa tanto en matemáticas aplicadas y economía como en informática, donde permite que muchos algoritmos sean mucho más rápidos.
Antes de que existiera este nombre, los problemas de optimización se abordaban caso por caso, sin un marco común. El matemático estadounidense Richard Bellman, que trabajaba en la RAND Corporation, desarrolló el método en la década de 1950 con el objetivo de optimizar procesos que evolucionan con el tiempo, como decisiones de inversión o de control de sistemas. Según el texto de referencia, el término se fijó hacia 1953, aunque la fecha exacta de su formulación es algo imprecisa en las fuentes. Bellman eligió la palabra «dinámica» para subrayar que las variables del problema cambian con el tiempo, y reconoció después que el nombre sonaba bien ante sus superiores.
La clave del método es el principio de optimalidad, formulado por Bellman, que dice que, en una secuencia óptima de decisiones, cualquier tramo final también debe ser óptimo por sí mismo. Gracias a él se puede resolver el problema por etapas, calculando primero la mejor decisión en la última etapa y retrocediendo hasta la inicial. Para que el método sea aplicable, un problema debe tener dos propiedades: subestructura óptima, es decir, que su solución se construya a partir de soluciones óptimas de sus subproblemas, y subproblemas superpuestos, es decir, que los mismos subproblemas aparezcan una y otra vez.
Un ejemplo clásico es la sucesión de Fibonacci. Si calculamos cada término de forma recursiva, volvemos a calcular los mismos valores anteriores una y otra vez, lo que desperdicia mucho tiempo. La solución consiste en guardar cada resultado la primera vez que se obtiene, una técnica llamada memoización, y reutilizarlo cuando haga falta. Existen dos enfoques habituales: el descendente (top-down), que combina recursión y memoización, y el ascendente (bottom-up), que resuelve de antemano todos los subproblemas necesarios, con un consumo de espacio algo menor pero a veces más difícil de planificar.
El método se distingue también entre determinístico, cuando los datos se conocen con certeza, y probabilístico, cuando dependen de distribuciones de probabilidad. Por otro lado, algoritmos como Bellman-Ford o Floyd-Warshall, que buscan caminos más cortos en grafos, se basan en esta misma lógica.
Hoy la programación dinámica está presente en campos muy diversos: en la planificación de rutas y redes, en la bioinformática para comparar secuencias de ADN, en el control de sistemas técnicos y en la toma de decisiones económicas. Su valor práctico es que convierte problemas que serían inabordables por fuerza bruta en cálculos manejables.
Cronología
- 1950Bellman desarrolla el método en la década de 1950 durante su trabajo en la RAND Corporation.
- 1953Richard Bellman introduce el término programación dinámica, según la fecha aproximada de la ficha.
- Bellman formula el principio de optimalidad, base de los cálculos recursivos del método.
- Los algoritmos de Bellman-Ford y Floyd-Warshall aplican la misma lógica para hallar caminos más cortos en grafos.
Curiosidades y anécdotas
Un nombre elegido con cautela
Bellman contó que eligió la palabra «dinámica» en parte para que sus superiores no vieran con recelo sus investigaciones matemáticas.