La programación dinámica es un concepto desarrollado por Richard Bellman, matemático y economista.
En ese momento, Bellman estaba buscando una forma de resolver problemas de optimización complejos. Los problemas de optimización requieren que elija la mejor solución de un conjunto de opciones.
Un ejemplo de un problema de optimización es el problema del viajante de comercio. El objetivo es encontrar la ruta más corta que le permita al vendedor visitar cada ciudad exactamente una vez y regresar a la ciudad de partida.
El enfoque de Bellman para estos problemas era dividirlos en subproblemas más pequeños y resolver los subproblemas del más pequeño al más grande. Luego almacenó los resultados de los subproblemas y los reutilizó para resolver subproblemas más grandes. Esta es la idea principal detrás de la programación dinámica.
Tabla de contenido
¿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 que puedan reutilizarse y combinarse para resolver el problema más grande. Los problemas se resuelven desde el más pequeño hasta el más grande, lo que permite reutilizar las soluciones.
¿Cómo funciona la programación dinámica?
Resolver un problema usando programación dinámica involucra los siguientes pasos:
Para ver esto en acción, calculamos el sexto número de Fibonacci, F(6), usando este proceso.
Primero, defina los subproblemas que necesitan ser resueltos.
F(n) = F(n-1) + F(n-2) para n > 1
Por 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 subproblema utilizando una función recursiva o un proceso iterativo. Resolvemos los subproblemas desde el más pequeño hasta el más grande, reutilizando los resultados de los 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 que puedan reutilizarse para resolver subproblemas más grandes como este:
Una vez que se han resuelto todos los subproblemas, usamos las soluciones para construir la solución al problema original.
En este caso, la solución al problema original es el sexto número de Fibonacci, que se encuentra sumando los resultados de F(5) y F(4), subproblemas identificados a partir del problema más grande. El resultado nos da 8.
¿Dónde y por qué se utiliza la programación dinámica?
La programación dinámica se usa en áreas donde tenemos problemas que se pueden dividir en subproblemas más pequeños, y sus soluciones se usan para resolver problemas más grandes.
Estas áreas incluyen informática, economía, matemáticas e ingeniería. En informática, se usa para resolver problemas que involucran 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 usa en teoría de juegos, estadística y probabilidad, donde se usa 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.
Existen varias ventajas en el uso de la programación dinámica para resolver problemas de optimización:
Cuando se trata de resolver problemas de optimización, la programación dinámica es una herramienta muy útil para asegurar la eficiencia en las soluciones.
Enfoques utilizados en la programación dinámica
En la programación dinámica, se utilizan dos enfoques para resolver problemas de optimización. Estos son el enfoque de arriba hacia abajo y el enfoque de abajo hacia arriba.
Enfoque de arriba hacia abajo
Este enfoque también se conoce como memorización. La memorización es una técnica de optimización utilizada principalmente para hacer que los programas informáticos sean más rápidos al almacenar los resultados de las llamadas a funciones en la memoria caché y devolver los resultados almacenados en la memoria caché la próxima vez que se necesiten en lugar de volver a calcularlos.
El enfoque de arriba hacia abajo implica la recursividad y el almacenamiento en caché. La recursividad involucra una función que se llama a sí misma con versiones más simples del problema como argumento. La recursividad se utiliza para dividir el problema en subproblemas más pequeños y resolver los subproblemas.
Una vez que se resuelve un subproblema, su resultado se almacena en caché y se reutiliza cada vez que ocurre un problema similar. El top-down es fácil de entender e implementar y solo resuelve un subproblema una vez. Sin embargo, una desventaja es que ocupa mucha memoria debido a la recursividad. Esto puede conducir a un error de desbordamiento de pila.
Enfoque de abajo hacia arriba
El enfoque de abajo hacia arriba, también conocido como tabulación, elimina la recursividad, reemplazándola con iteración, evitando así 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 más grandes que dependen de los subproblemas. Luego, se encuentra el resultado del problema original resolviendo el subproblema más grande utilizando valores calculados previamente.
Este enfoque tiene la ventaja de ser eficiente en memoria y tiempo al eliminar la recursividad.
Ejemplos de problemas que pueden resolverse mediante programación dinámica
Los siguientes son algunos problemas de programación que se pueden resolver usando programación dinámica:
#1. Problema de mochila
Fuente: Wikipedia
Una mochila es una bolsa hecha de lona, nailon o cuero que normalmente se ata a la espalda y que usan los soldados y los excursionistas para llevar suministros.
En el problema de la mochila, se le presenta una mochila y, dada su capacidad de carga, debe elegir artículos, cada uno con su valor. Su selección debe ser tal que obtenga el valor total máximo de los artículos recogidos y el peso de los artículos sea menor o igual a la capacidad de la mochila.
A continuación se muestra un ejemplo del problema de la mochila:
Imagina que vas de excursión y tienes una mochila con una capacidad de 15 kilogramos. Tienes una lista de artículos que puedes llevar contigo, junto con sus valores y pesos, como se muestra en la siguiente tabla:
ArtículoValorPesoTienda2003Saco de dormir1502Estufa501Comida1002Botella de agua100.5Botiquín de primeros auxilios251
Elija un subconjunto de los artículos para llevar de modo que el valor total de los artículos se maximice mientras que el peso total sea menor o igual a la capacidad de la mochila, que es de 15 kilogramos.
Las aplicaciones del mundo real del problema de la mochila implican seleccionar valores para agregar a una cartera para minimizar el riesgo y maximizar las ganancias y encontrar las formas menos derrochadoras de reducir las 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 tareas de manera óptima a un conjunto de recursos. Los recursos pueden ser máquinas, personal u otros recursos utilizados para completar las tareas.
A continuación se muestra un ejemplo de un problema de programación:
Imagine que es un gerente 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 que están calificados para completarla.
A continuación se muestra una tabla que describe las tareas y sus características:
Tarea Hora de inicio Hora de finalización Empleados calificados T1911A, B, CT21012A, CT31113B, CT41214A, B
Asigne cada tarea a un empleado para minimizar el tiempo total de finalización.
El problema de programación se puede encontrar en la industria manufacturera cuando se trata de optimizar la asignación de recursos como máquinas, materiales, herramientas y mano de obra.
También se puede encontrar en el cuidado de la salud al optimizar el uso de camas, personal y suministros médicos. Otras industrias en las que puede ocurrir este problema son la gestión de proyectos, la gestión de la cadena de suministro y la educación.
#3. Problema del vendedor ambulante
Fuente: Wikipedia
Este es uno de los problemas de optimización más estudiados que se pueden resolver mediante programación dinámica.
El problema del viajante de comercio proporciona una lista de ciudades y las distancias entre cada par de ciudades. Debe encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese a la ciudad de origen.
A continuación se muestra un ejemplo de un problema de viajante de comercio:
Imagina que eres un vendedor que necesita visitar un conjunto de ciudades en el menor tiempo posible. Tienes una lista de las ciudades que necesitas visitar y las distancias entre cada par de ciudades, como se muestra en la siguiente tabla:
CiudadABCDEA010152030B100352515C153503020D202530010E301520100
El problema del viajante de comercio se puede encontrar en la industria del ocio cuando se trata de planificar rutas para turistas, la logística cuando se planifica el envío de mercancías, el transporte cuando se planifican rutas de autobuses y en la industria de ventas, entre otras.
Claramente, 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 exponer su conocimiento de la programación dinámica.
Recursos
Programación Dinámica por 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.
El libro está escrito de una manera fácil de entender que solo requiere conocimientos básicos de matemáticas y cálculo para comprender el texto. En el libro, Bellman presenta la teoría matemática de un proceso de decisión de múltiples etapas que es clave en la programación dinámica.
Luego, el libro examina los problemas de cuello de botella en los procesos de producción de múltiples etapas, los teoremas de existencia y unicidad, y la ecuación de inventario óptima.
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, de tapa dura y de bolsillo.
Máster en Algoritmos de Programación Dinámica
Este curso maestro de algoritmos de programación dinámica de Udemy es ofrecido por Apaar Kamal, un 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 la competencia de programación que presenta muchos problemas que requieren una programación dinámica.
Además 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, que tiene una duración de más de 40 horas, cubre la programación dinámica en profundidad. El curso primero ofrece un repaso de conceptos como la recursividad y el retroceso.
Luego cubre la programación dinámica en teoría de juegos, cadenas, árboles y gráficos, exponenciación de matrices, máscaras de bits, combinatoria y subsecuencias, problemas de partición y programación dinámica multidimensional, entre muchos otros conceptos.
Fundamentos de la programación competitiva, algoritmos maestros
Udemy ofrece un curso básico de programación competitiva de Prateek Narang y Amal Kamaar que cubre programación dinámica, matemáticas, teoría de números y estructuras de datos y algoritmos avanzados de una manera que es útil y relevante para los programadores competitivos.
El curso ofrece un repaso de estructuras de datos y algoritmos antes de sumergirse en algoritmos y técnicas más complejos que son útiles en la programación competitiva.
El curso cubre programación dinámica, matemáticas, teoría de juegos, coincidencia de patrones, enmascaramiento de bits y una miríada de algoritmos avanzados utilizados y probados en competencias de programación.
El curso de Udemy se divide en 10 módulos y 42 secciones y proporciona muchas preguntas de práctica después de cada sección. Este curso superventas es imprescindible para cualquier persona interesada en la programación competitiva.
Ultimas palabras
La programación dinámica es una habilidad beneficiosa para que cualquier programador aprenda a mejorar su resolución de problemas del mundo real. Por lo tanto, los programadores deben considerar revisar los recursos sugeridos para agregar esta herramienta crucial a su caja de herramientas.
A continuación, puede consultar los lenguajes de programación para usar en la ciencia de datos.