Estructuras de datos: programación dinámica
El enfoque de programación dinámica es similar a dividir y conquistar al dividir el problema en subproblemas más pequeños y aún más pequeños. Pero a diferencia de divide y vencerás, estos subproblemas no se resuelven de forma independiente. Más bien, los resultados de estos subproblemas más pequeños se recuerdan y se utilizan para subproblemas similares o superpuestos.
La programación dinámica se utiliza cuando tenemos problemas, que se pueden dividir en subproblemas similares, de modo que sus resultados se puedan reutilizar. En su mayoría, estos algoritmos se utilizan para la optimización. Antes de resolver el subproblema en cuestión, el algoritmo dinámico intentará examinar los resultados de los subproblemas previamente resueltos. Las soluciones de subproblemas se combinan con el fin de lograr la mejor solución.
Entonces podemos decir que -
El problema debería poder dividirse en subproblemas superpuestos más pequeños.
Se puede lograr una solución óptima utilizando una solución óptima de subproblemas más pequeños.
Los algoritmos dinámicos utilizan Memoization.
Comparación
A diferencia de los algoritmos codiciosos, donde se aborda la optimización local, los algoritmos dinámicos están motivados para una optimización general del problema.
A diferencia de los algoritmos de dividir y conquistar, donde las soluciones se combinan para lograr una solución general, los algoritmos dinámicos utilizan la salida de un subproblema más pequeño y luego intentan optimizar un subproblema mayor. Los algoritmos dinámicos utilizan la memorización para recordar el resultado de subproblemas ya resueltos.
Ejemplo
Los siguientes problemas informáticos se pueden resolver utilizando un enfoque de programación dinámica:
- Serie de números de Fibonacci
- Problema de la mochila
- Torre de Hanoi
- Todos emparejan el camino más corto de Floyd-Warshall
- El camino más corto por Dijkstra
- Programación de proyectos
La programación dinámica se puede utilizar tanto de arriba hacia abajo como de abajo hacia arriba. Y, por supuesto, la mayoría de las veces, hacer referencia a la salida de la solución anterior es más barato que volver a calcular en términos de ciclos de CPU.