Programación dinámica

La programación dinámica en teoría de control y teoría de sistemas informáticos es una forma de resolver problemas complejos dividiéndolos en subtareas más simples. Es aplicable a problemas con subestructura óptima, que parecen un conjunto de subproblemas superpuestos, cuya complejidad es ligeramente menor que la original. En este caso, el tiempo de cálculo, en comparación con los métodos "ingenuos", se puede reducir significativamente.

La idea clave en la programación dinámica es bastante simple. Como regla general, para resolver el problema, se requiere resolver partes separadas del problema (subproblema) y luego combinar las soluciones de las subtareas en una solución común. A menudo, muchas de estas subtareas son las mismas. El enfoque de programación dinámica consiste en resolver cada subproblema una sola vez, lo que reduce el número de cálculos. Esto es especialmente útil en casos donde el número de subtareas recurrentes es exponencialmente grande.

El método de programación dinámica desde arriba es una simple memorización de los resultados de resolver aquellos subproblemas que pueden surgir nuevamente en el futuro. La programación dinámica desde abajo implica reformular un problema complejo como una secuencia recursiva de subproblemas más simples.

Historia

La frase "programación dinámica" fue utilizada por primera vez en la década de 1940 por Richard Bellman para describir el proceso de encontrar una solución a un problema, donde la respuesta a un problema solo se puede obtener después de resolver el problema "precedente". En 1953, refinó esta definición a la moderna. El campo se fundó originalmente como análisis e ingeniería de sistemas, que fue reconocido por el IEEE . La contribución de Bellman a la programación dinámica ha sido inmortalizada en el nombre de la ecuación de Bellman , un resultado central de la teoría de la programación dinámica que reformula un problema de optimización en forma recursiva .

La palabra "programación" en la frase "programación dinámica" en realidad no tiene casi nada que ver con la programación "tradicional" (escribir código) y tiene sentido como en la frase " programación matemática ", que es sinónimo de la palabra "optimización". Por lo tanto, la palabra "programa" en este contexto significa más bien la secuencia óptima de acciones para obtener una solución al problema. Por ejemplo, un programa específico de eventos en una exposición a veces se denomina programa. El programa en este caso se entiende como una secuencia válida de eventos.

La idea de la programación dinámica

Una subestructura óptima en programación dinámica significa que se puede usar una solución óptima a subproblemas más pequeños para resolver el problema original. Por ejemplo, el camino más corto en un gráfico desde un vértice (denotado por s) a otro (denotado por t) se puede encontrar de la siguiente manera: primero, consideramos el camino más corto desde todos los vértices adyacentes a s hasta t, y luego, tomando teniendo en cuenta los pesos de las aristas que conectan s con vértices adyacentes, elegimos el mejor camino hacia t (por qué vértice es mejor pasar). En el caso general, podemos resolver un problema que tiene una subestructura óptima siguiendo los siguientes tres pasos.

Dividir una tarea en subtareas más pequeñas.
Encontrar la solución óptima a subproblemas recursivamente, haciendo el mismo algoritmo de tres pasos .
Usar la solución obtenida de las subtareas para construir una solución al problema original.

Los subproblemas se resuelven dividiéndolos en subproblemas aún más pequeños, y así sucesivamente, hasta llegar al caso trivial de un problema que se puede resolver en tiempo constante (la respuesta se puede decir inmediatamente). Por ejemplo, si necesitamos encontrar n!, entonces 1! = 1 (o 0!=1).

Los subproblemas superpuestos en programación dinámica significan subproblemas que se utilizan para resolver una serie de problemas (no solo uno) de mayor tamaño (es decir, hacemos lo mismo varias veces). Un ejemplo sorprendente es el cálculo de la sucesión de Fibonacci e , incluso en un caso tan trivial, ya hemos contado dos veces los cálculos de solo dos números de Fibonacci . Si continúa más y cuenta , se contará dos veces más, ya que nuevamente y será necesario para el cálculo . Resulta lo siguiente: un enfoque recursivo simple dedicará tiempo a calcular una solución para problemas que ya ha resuelto. $F_{3}=F_{2}+F_{1}$ $F_{4}=F_{3}+F_{2}$ $F_{2}$ $F_{5}$ $F_{2}$ $F_{5}$ $F_{3}$ $F_{4}$

Para evitar tal curso de eventos, guardaremos las soluciones de los subproblemas que ya hemos resuelto, y cuando nuevamente necesitemos la solución del subproblema, en lugar de recalcularla, simplemente la sacaremos de la memoria. Este enfoque se llama memorización . También puede realizar optimizaciones adicionales; por ejemplo, si estamos seguros de que ya no necesitamos resolver una subtarea, podemos eliminarla de la memoria y liberarla para otras necesidades, o si el procesador está inactivo y sabemos que la solución de algunas subtareas que aún no han sido calculadas, necesitamos en el futuro, podemos resolverlas con anticipación.

Resumiendo lo anterior, podemos decir que la programación dinámica utiliza las siguientes propiedades del problema:

subtareas superpuestas;
subestructura óptima;
la capacidad de memorizar la solución de subtareas frecuentes.

La programación dinámica generalmente sigue dos enfoques para la resolución de problemas:

Programación dinámica de arriba hacia abajo: el problema se divide en subproblemas más pequeños, se resuelven y luego se combinan para resolver el problema original. La memorización se utiliza para resolver subtareas ya resueltas.
Programación dinámica de abajo hacia arriba: todas las subtareas que se necesitan posteriormente para resolver el problema original se calculan de antemano y luego se utilizan para construir una solución al problema original. Esta forma es mejor que la programación de arriba hacia abajo en términos del tamaño de la pila requerida y la cantidad de llamadas a funciones, pero a veces no es fácil determinar de antemano qué subproblemas debemos resolver en el futuro.

Los lenguajes de programación pueden recordar el resultado de una llamada de función con un determinado conjunto de argumentos ( memoización ) para acelerar el "cálculo por nombre". Algunos lenguajes tienen esta capacidad incorporada (por ejemplo , Scheme , Common Lisp , Clojure , Perl , D ), mientras que otros requieren extensiones adicionales ( C++ ).

Se conocen la programación dinámica serial, que se incluye en todos los libros de texto sobre investigación de operaciones , y la programación dinámica no serial (NSDP), que actualmente es poco conocida, aunque fue descubierta en la década de 1960.

La programación dinámica convencional es un caso especial de programación dinámica no serial, donde el gráfico de relación variable es solo una ruta. NSDP, al ser un método natural y general para tener en cuenta la estructura de un problema de optimización, considera un conjunto de restricciones y/o una función objetivo como una función recursivamente computable. Esto permite encontrar una solución paso a paso, en cada etapa utilizando la información obtenida en las etapas anteriores, y la eficiencia de este algoritmo depende directamente de la estructura del gráfico de relación de variables. Si este gráfico es lo suficientemente disperso, la cantidad de cálculo en cada etapa se puede mantener dentro de límites razonables.

Una de las principales propiedades de los problemas resueltos mediante programación dinámica es la aditividad . Los problemas no aditivos se resuelven por otros métodos. Por ejemplo, muchas tareas de optimización de las inversiones de una empresa no son aditivas y se resuelven comparando el valor de la empresa con y sin inversiones.

Problemas clásicos de programación dinámica

Problema de la subsecuencia común más larga : dadas dos secuencias, debe encontrar la subsecuencia común más larga.
La tarea de encontrar la subsecuencia creciente más grande : dada una secuencia, se requiere encontrar la subsecuencia creciente más larga.
Problema de distancia de edición (distancia de Levenshtein) : dadas dos cadenas, se requiere encontrar el número mínimo de borrados, reemplazos y adiciones de caracteres que transforman una cadena en otra.
El problema de calcular los números de Fibonacci
El problema del orden de multiplicación de matrices : matrices dadas , …, , se requiere minimizar el número de operaciones escalares para su multiplicación. $A_{1}$ $Un}$
El problema de elegir una trayectoria.
Problema de decisión secuencial
El problema del uso de la mano de obra
Desafío de gestión de inventario
El problema de la mochila : de un conjunto ilimitado de artículos con las propiedades "costo" y "peso", se requiere seleccionar un cierto número de artículos de tal manera que se obtenga el máximo costo total con un peso total limitado.
Algoritmo de Floyd-Warshall : encuentre las distancias más cortas entre todos los vértices de un gráfico dirigido ponderado.
Algoritmo de Bellman-Ford : encuentra el camino más corto en un gráfico ponderado entre dos vértices dados.
Máximo conjunto independiente de vértices en un árbol : dado un árbol, encuentra el máximo conjunto de vértices de los cuales dos no están conectados por un borde.
La tarea de programar el transportador : hay dos transportadores, cada uno con trabajos. Se dan los tiempos de trabajo en cada transportador, su colocación y retirada, así como el tiempo de traslado a un lugar vecino. Desea determinar la forma más rápida de ensamblar una pieza utilizando ambos transportadores. $norte$

Literatura

Bellman R. Programación dinámica. - M .: Editorial de literatura extranjera , 1960.
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, C. Capítulo 15. Programación dinámica // Algoritmos: construcción y análisis = Introducción a los algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. algoritmos _ - McGraw-Hill Ciencias/Ingeniería/Matemáticas, 2006. - 336 p. — ISBN 0073523402 .
Akulich I. L. Capítulo 4. Problemas de programación dinámica // Programación matemática en ejemplos y problemas. - M. : Escuela superior , 1986. - 319 p. — ISBN 5-06-002663-9 .
Bertele U., Brioshi F. Programación dinámica no serial. - NY: Academic Press, 1972. - 235 págs.
Gabasov R. , Kirillova F. M. Fundamentos de la programación dinámica. -Mn. : Editorial BSU, 1975. - 262 p.

Enlaces

Video conferencias sobre programación dinámica
Teoría, tareas, sistema de pruebas .

diccionarios y enciclopedias

En catálogos bibliográficos
BNE : XX543843 BNF : 11978098s TIERRA : 4125677-3 J9U : 987007567971605171 LCCN : sh85040313 NDL : 00571739