En este tutorial, aprenderá qué es la programación dinámica. Además, encontrará la comparación entre la programación dinámica y los algoritmos codiciosos para resolver problemas.
La programación dinámica es una técnica en programación de computadoras que ayuda a resolver de manera eficiente una clase de problemas que tienen subproblemas superpuestos y una propiedad de subestructura óptima.
Tales problemas implican calcular repetidamente el valor de los mismos subproblemas para encontrar la solución óptima.
Ejemplo de programación dinámica
Tomemos el caso de generar la secuencia de fibonacci.
Si la secuencia es F (1) F (2) F (3)… F (50), sigue la regla F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Observe cómo hay subproblemas superpuestos, necesitamos calcular F (48) para calcular F (50) y F (49). Este es exactamente el tipo de algoritmo en el que destaca la programación dinámica.
Cómo funciona la programación dinámica
La programación dinámica funciona almacenando el resultado de los subproblemas para que cuando se requieran sus soluciones, estén a mano y no necesitemos recalcularlos.
Esta técnica de almacenar el valor de los subproblemas se llama memorización. Al guardar los valores en la matriz, ahorramos tiempo para los cálculos de los subproblemas con los que ya nos hemos encontrado.
var m = map (0 → 0, 1 → 1) función fib (n) si la clave n no está en el mapa mm (n) = fib (n - 1) + fib (n - 2) return m (n)
La programación dinámica por memorización es un enfoque de arriba hacia abajo para la programación dinámica. Al invertir la dirección en la que funciona el algoritmo, es decir, partiendo del caso base y trabajando hacia la solución, también podemos implementar la programación dinámica de abajo hacia arriba.
function fib (n) si n = 0 return 0 else var prevFib = 0, currFib = 1 repetir n - 1 veces var newFib = prevFib + currFib prevFib = currFib currFib = newFib return currentFib
Recurrencia vs programación dinámica
La programación dinámica se aplica principalmente a algoritmos recursivos. Esto no es una coincidencia, la mayoría de los problemas de optimización requieren recursividad y la programación dinámica se utiliza para la optimización.
Pero no todos los problemas que utilizan la recursividad pueden utilizar la programación dinámica. A menos que exista la presencia de subproblemas superpuestos como en el problema de la secuencia de fibonacci, una recursividad solo puede llegar a la solución utilizando un enfoque de divide y vencerás.
Esa es la razón por la que un algoritmo recursivo como Merge Sort no puede usar la Programación dinámica, porque los subproblemas no se superponen de ninguna manera.
Algoritmos codiciosos frente a programación dinámica
Los algoritmos codiciosos son similares a la programación dinámica en el sentido de que ambos son herramientas de optimización.
Sin embargo, los algoritmos codiciosos buscan soluciones óptimas a nivel local o, en otras palabras, una elección codiciosa, con la esperanza de encontrar un óptimo global. Por lo tanto, los algoritmos codiciosos pueden hacer una suposición que parece óptima en ese momento, pero se vuelve costosa en el futuro y no garantiza un óptimo global.
La programación dinámica, por otro lado, encuentra la solución óptima a los subproblemas y luego toma una decisión informada para combinar los resultados de esos subproblemas para encontrar la solución más óptima.
