La programación dinámica es un concepto desarrollado por Richard Bellman, matemático y economista.
En aquel momento, Bellman buscaba una forma de resolver problemas complejos de optimización. Los problemas de optimización requieren elegir la mejor solución entre un conjunto de opciones.
Un ejemplo de problema de optimización es el problema del viajante de comercio. El objetivo es encontrar la ruta más corta que permita al vendedor visitar cada ciudad exactamente una vez y regresar a la ciudad de partida.
El planteamiento de Bellman para estos problemas consistía en dividirlos en subproblemas más pequeños y resolver los subproblemas del más pequeño al más grande. Después almacenaba los resultados de los subproblemas y los reutilizaba para resolver subproblemas más grandes. Esta es la idea principal de la programación dinámica.
¿Qué es la programación dinámica?
La programación dinámica resuelve problemas de optimización dividiéndolos en subproblemas más pequeños, resolviendo cada subproblema una vez y almacenando sus soluciones para poder reutilizarlas y combinarlas para resolver el problema más grande. Los problemas se resuelven del más pequeño al más grande, lo que permite reutilizar las soluciones.
¿Cómo funciona la programación dinámica?
La resolución de un problema mediante programación dinámica implica los siguientes pasos:
- Definir los subproblemas: Un problema grande se divide en pequeños subproblemas.
- Resolver los subproblemas: Esto implica resolver el subproblema identificado, lo que puede hacerse utilizando la recursividad o la iteración.
- Almacenar las soluciones: Las soluciones a los subproblemas se almacenan para poder reutilizarlas.
- Construirla solución al problema original: La solución al problema grande se construye a partir de los subproblemas que ya se han calculado.
Para ver esto en acción, calculemos el 6º número de Fibonacci, F(6), siguiendo este proceso.
En primer lugar, defina los subproblemas que hay que resolver.
F(n) = F(n-1) F(n-2) para n > 1
Por lo tanto F(6) = F(5) F(4)
F(5) = F(4) F(3)
F(4) = F(3) F(2)
F(3) = F(2) F(1)
F(2) = F(1) F(0)
F(1) = 1
F(0) = 0
El segundo paso consiste en resolver cada uno de los subproblemas mediante una función recursiva o un proceso iterativo. Resolvemos los subproblemas del más pequeño al más grande, reutilizando los resultados de subproblemas más pequeños. Esto nos da lo siguiente
F(0) = 0
F(1) = 1
F(2) = F(1) F(0) = 1 0 = 1
F(3) = F(2) F(1) = 1 1 = 2
F(4) = F(3) F(2) = 2 1 = 3
F(5) = F(4) F(3) = 3 2 = 5
F(6) = F(5) F(4) = 5 3 = 8
A medida que resolvemos cada uno de los subproblemas, almacenamos las soluciones en una matriz o tabla para poder reutilizarlas en la resolución de subproblemas mayores, de esta forma
| n | F(n) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
Una vez resueltos todos los subproblemas, utilizamos las soluciones para construir la solución del problema original.
En este caso, la solución al problema original es el 6º número de Fibonacci, que se halla sumando los resultados de F(5) y F(4), subproblemas identificados a partir del problema mayor. El resultado nos da 8.
¿Dónde y por qué se utiliza la programación dinámica?
La programación dinámica se utiliza en áreas en las que tenemos problemas que pueden dividirse en subproblemas más pequeños, y sus soluciones se utilizan para resolver problemas más grandes.
Estas áreas incluyen la informática, la economía, las matemáticas y la ingeniería. En informática, se utiliza para resolver problemas que implican secuencias, gráficos y valores enteros y en programación competitiva.
En economía, se utiliza para resolver problemas de optimización en finanzas, producción y asignación de recursos. En matemáticas, la programación dinámica se utiliza en teoría de juegos, estadística y probabilidad, donde se emplea para resolver problemas de optimización.
En ingeniería, se utiliza para resolver problemas de asignación de recursos, programación, fabricación, comunicación y sistemas de control.
Utilizar la programación dinámica para resolver problemas de optimización tiene varias ventajas:
- Eficacia: La programación dinámica puede ser más eficiente que otros algoritmos de optimización, ya que evita volver a calcular problemas similares varias veces.
- Resolución de problemas grandes: La programación dinámica es ideal para grandes problemas de optimización que serían inviables de resolver utilizando otros métodos. Esto se debe a que descompone el problema en problemas más pequeños reduciendo su complejidad.
- Soluciones óptimas: Los algoritmos de programación dinámica pueden encontrar la solución óptima a un problema si los subproblemas y los objetivos se definen correctamente.
- Simplicidad: Los algoritmos de programación dinámica son sencillos de aplicar y comprender, especialmente si el problema puede definirse en un orden específico.
- Extensibilidad: Los algoritmos de programación dinámica pueden ampliarse fácilmente para resolver problemas más complejos añadiendo subproblemas adicionales y modificando los objetivos del problema.
Cuando se trata de resolver problemas de optimización, la programación dinámica es una herramienta muy útil para garantizar la eficacia en las soluciones.
Enfoques utilizados en la programación dinámica
En la programación dinámica se utilizan dos enfoques para resolver los problemas de optimización. Son el enfoque descendente y el enfoque ascendente.
Enfoque descendente
Este enfoque también se conoce como memoización. La memoización es una técnica de optimización utilizada principalmente para hacer que los programas informáticos sean más rápidos almacenando los resultados de las llamadas a funciones en la memoria caché y devolviendo los resultados almacenados la próxima vez que se necesiten en lugar de computarlos de nuevo.
El enfoque descendente implica recursión y almacenamiento en caché. La recursividad implica que una función se llame a sí misma con versiones más simples del problema como argumento. La recursividad se utiliza para descomponer el problema en subproblemas más pequeños y resolver los subproblemas.
Una vez resuelto un subproblema, su resultado se almacena en caché y se reutiliza cada vez que se presenta un problema similar. El método descendente es fácil de entender e implementar y sólo resuelve un subproblema una vez. Sin embargo, su inconveniente es que ocupa mucha memoria debido a la recursividad. Esto puede provocar un error de desbordamiento de pila.
Enfoque ascendente
El enfoque ascendente, también conocido como tabulación, prescinde de la recursividad y la sustituye por la iteración, evitando así los errores de desbordamiento de pila.
En este enfoque, un problema grande se divide en subproblemas más pequeños, y las soluciones de los subproblemas se utilizan para resolver el problema más grande.
Los subproblemas más pequeños se resuelven primero de mayor a menor, y sus resultados se almacenan en una matriz, matriz o tabla, de ahí el nombre de tabulación.
Los resultados almacenados resuelven problemas mayores que dependen de los subproblemas. El resultado del problema original se encuentra entonces resolviendo el subproblema más grande utilizando los valores calculados previamente.
Este enfoque tiene la ventaja de ser eficiente en memoria y tiempo al prescindir de la recursividad.
Ejemplos de problemas que pueden resolverse mediante programación dinámica
Los siguientes son algunos problemas de programación que pueden resolverse mediante programación dinámica:
#1. Problema de la mochila
Una mochila es una bolsa hecha de lona, nailon o cuero que se suele atar a la espalda y que utilizan los soldados y los excursionistas para transportar provisiones.
En el problema de la mochila, se le presenta una mochila y, dada su capacidad de carga, se le pide que elija objetos, cada uno con su valor. Su selección debe ser tal que obtenga el máximo valor total de los artículos elegidos y que el peso de los artículos sea menor o igual que la capacidad de la mochila.
A continuación se da un ejemplo del problema de la mochila:
Imagine que se va de excursión y tiene una mochila con una capacidad de 15 kilogramos. Tiene una lista de artículos que puede llevar consigo, junto con sus valores y pesos, como se muestra en la tabla siguiente:
| Artículo | Valor | Peso |
|---|---|---|
| Tienda de campaña | 200 | 3 |
| Saco de dormir | 150 | 2 |
| Estufa | 50 | 1 |
| Comida | 100 | 2 |
| Botella de agua | 10 | 0.5 |
| Botiquín de primeros auxilios | 25 | 1 |
Elija un subconjunto de los artículos a llevar tal que el valor total de los artículos se maximice mientras que el peso total es menor o igual que la capacidad de la mochila, que es de 15 kilogramos.
Las aplicaciones del problema de la mochila en el mundo real implican seleccionar valores para añadir a una cartera con el fin de minimizar el riesgo y maximizar el beneficio y encontrar las formas menos derrochadoras de cortar materias primas.
#2. Problema de programación
Un problema de programación es un problema de optimización en el que el objetivo es asignar de forma óptima tareas a un conjunto de recursos. Los recursos pueden ser máquinas, personal u otros recursos utilizados para completar las tareas.
A continuación se ofrece un ejemplo de un problema de programación:
Imagine que es usted un director de proyecto responsable de programar un conjunto de tareas que deben ser completadas por un equipo de empleados. Cada tarea tiene una hora de inicio, una hora de finalización y una lista de empleados cualificados para completarla.
He aquí una tabla que describe las tareas y sus características:
| Tarea | Hora de inicio | Hora de finalización | Empleados cualificados |
|---|---|---|---|
| T1 | 9 | 11 | A, B, C |
| T2 | 10 | 12 | A, C |
| T3 | 11 | 13 | B, C |
| T4 | 12 | 14 | A, B |
Asigne cada tarea a un empleado para minimizar el tiempo total de realización.
El problema de programación puede encontrarse en la industria manufacturera cuando se intenta optimizar la asignación de recursos como máquinas, materiales, herramientas y mano de obra.
También puede encontrarse en la sanidad cuando se optimiza el uso de camas, personal y suministros médicos. Otras industrias en las que puede darse este problema son la gestión de proyectos, la gestión de la cadena de suministro y la educación.
#3. Problema del viajante de comercio
Este es uno de los problemas de optimización más estudiados que puede resolverse mediante programación dinámica.
El problema del viajante de comercio proporciona una lista de ciudades y las distancias entre cada par de ciudades. Se trata de encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y vuelva a la ciudad de origen.
A continuación se da un ejemplo de un problema del viajante de comercio:
Imagine que es usted un vendedor que necesita visitar un conjunto de ciudades en el menor tiempo posible. Tiene una lista de las ciudades que debe visitar y las distancias entre cada par de ciudades, como se muestra en la tabla siguiente:
| Ciudad | A | B | C | D | E |
|---|---|---|---|---|---|
| A | 0 | 10 | 15 | 20 | 30 |
| B | 10 | 0 | 35 | 25 | 15 |
| C | 15 | 35 | 0 | 30 | 20 |
| D | 20 | 25 | 30 | 0 | 10 |
| E | 30 | 15 | 20 | 10 | 0 |
El problema del viajante de comercio puede encontrarse en la industria del ocio cuando se trata de planificar rutas para turistas, en la logística cuando se planifica el envío de mercancías, en el transporte cuando se planifican rutas de autobuses y en la industria de ventas, entre otros.
Está claro que la programación dinámica tiene muchas aplicaciones en el mundo real, lo que ayuda a aprender más sobre ella.
Considere los siguientes recursos para ampliar sus conocimientos sobre la programación dinámica.
Recursos
Programación dinámica de Richard Bellman
Programación dinámica es un libro de Richard Bellman, quien ideó la programación dinámica y la desarrolló en sus primeras etapas.
| Preview | Product | Rating | |
|---|---|---|---|
|
Dynamic Programming (Dover Books on Computer Science) | Buy on Amazon |
El libro está escrito de una forma fácil de entender que sólo requiere conocimientos básicos de matemáticas y cálculo para comprender el texto. En el libro, Bellman introduce la teoría matemática del proceso de decisión en varias etapas, que es clave en la programación dinámica.
A continuación, el libro examina los problemas de cuello de botella en los procesos de producción multietapa, los teoremas de existencia y unicidad y la ecuación del inventario óptimo.
Lo mejor del libro es que Bellman ofrece ejemplos de muchos problemas complejos en campos como la logística, la teoría de la programación, la teoría de la comunicación, la economía matemática y los procesos de control, y muestra cómo la programación dinámica puede resolver los problemas.
El libro está disponible en versiones Kindle, tapa dura y rústica.
Curso magistral de algoritmos de programación dinámica
Este Curso Magistral de Algoritmos de Programación Dinámica de Udemy es ofrecido por Apaar Kamal, ingeniero de software de Google, y Prateek Narang, que también trabajó con Google.
El curso está optimizado para ayudar a los alumnos a sobresalir en competiciones de programación que presentan muchos problemas que requieren programación dinámica.
Aparte de los competidores de programación, el curso es ideal para programadores que buscan mejorar su comprensión de los algoritmos y personas que se preparan para entrevistas de programación y rondas de codificación en línea.
El curso, de más de 40 horas de duración, cubre la programación dinámica en profundidad. En primer lugar, el curso ofrece un repaso de conceptos como la recursividad y el backtracking.
A continuación, cubre la programación dinámica en teoría de juegos, cadenas, árboles y grafos, exponenciación matricial, máscaras de bits, combinatoria y subsecuencias, problemas de partición y programación dinámica multidimensional, entre otros muchos conceptos.
Fundamentos de la programación competitiva, Domine los algoritmos
Udemy ofrece un curso de Fundamentos de la programación competitiva impartido por Prateek Narang y Amal Kamaar que abarca la programación dinámica, las matemáticas, la teoría de números y las estructuras de datos y algoritmos avanzados de forma útil y relevante para los programadores competitivos.
El curso ofrece un repaso de las estructuras de datos y los algoritmos antes de sumergirse en algoritmos y técnicas más complejos que resultan útiles en la programación competitiva.
El curso abarca la programación dinámica, las matemáticas, la teoría de juegos, la concordancia de patrones, el enmascaramiento de bits y una miríada de algoritmos avanzados utilizados y probados en competiciones de programación.
El curso Udemy está dividido en 10 módulos y 42 secciones y proporciona un montón de preguntas de práctica después de cada sección. Este curso superventas es imprescindible para cualquier persona interesada en la programación competitiva.
Palabras finales
La programación dinámica es una habilidad beneficiosa que cualquier programador debe aprender para mejorar su resolución de problemas del mundo real. Por lo tanto, los programadores deberían considerar la posibilidad de revisar los recursos sugeridos para añadir esta herramienta crucial a su caja de herramientas.
A continuación, puede consultar los lenguajes de programación que se utilizan en la ciencia de datos.