Introducción a la Programación Dinámica
La programación dinámica es un método para resolver un problema complejo dividiéndolo en una colección de subproblemas más simples, resolviendo cada uno de esos subproblemas solo una vez y almacenando sus soluciones utilizando una estructura de datos basada en memoria (array, mapa, etc.). Cada solución de subproblema se indexa de alguna manera, generalmente en función de los valores de sus parámetros de entrada, para facilitar su búsqueda. Entonces, la próxima vez que ocurra el mismo subproblema, en lugar de volver a calcular su solución, uno busca la solución previamente calculada, ahorrando así tiempo de cálculo. Esta técnica de almacenar soluciones a subproblemas en lugar de volver a calcularlos se llama memorización.
Aquí hay una explicación brillante para explicar el concepto detrás de la programación dinámica a un niño.
*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper*
"What's that equal to?"
*counting* "Eight!"
*writes down another "1+" on the left*
"What about that?"
*quickly* "Nine!"
"How'd you know it was nine so fast?"
"You just added one more."
"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"Hay dos atributos clave que debe tener un problema para que la programación dinámica sea aplicable: subestructura óptima y subproblemas superpuestos.
1. Subestructura óptima
La programación dinámica simplifica un problema complicado al dividirlo en subproblemas más simples de manera recursivamente. Se dice que un problema que se puede resolver de manera óptima dividiéndolo en subproblemas y luego recursivamentemente encontrando las soluciones óptimas a los subproblemas tiene una subestructura óptima. En otras palabras, la solución a un problema de optimización dado puede obtenerse mediante la combinación de soluciones óptimas a sus subproblemas.
Por ejemplo, el camino más corto p desde un vértice u a un vértice v en un dado graph exhibe una subestructura óptima: tome cualquier vértice intermedio w en este camino más corto p. Si p es realmente el camino más corto, entonces se puede dividir en subcaminos p1 de u a w y p2 de w a v tales que estos, a su vez, son de hecho los caminos más cortos entre los vértices correspondientes.
2. Subproblemas superpuestos
Se dice que un problema tiene subproblemas superpuestos si el problema se puede dividir en subproblemas y cada subproblema se repite varias veces, o si un algoritmo recursivo para el problema resuelve el mismo subproblema repetidamente en lugar de generar siempre nuevos subproblemas.
Por ejemplo, el problema de calcular la secuencia de Fibonacci presenta subproblemas superpuestos. El problema de calcular el n'th número de Fibonacci F(n) se puede dividir en los subproblemas de computación F(n-1) y F(n-2), y luego sumando los dos. El subproblema de la computación F(n-1) se puede descomponer en un subproblema que implica calcular F(n-2). Por lo tanto, el cálculo de F(n-2) se reutiliza y, por lo tanto, la sucesión de Fibonacci presenta subproblemas superpuestos. La programación dinámica tiene en cuenta este hecho y resuelve cada subproblema una sola vez. Esto se puede lograr de dos maneras:
- Enfoque de arriba hacia abajo (memoización): Esta es la consecuencia directa de la formulación recursivamente de cualquier problema. Si la solución a cualquier problema se puede formular recursivamentemente usando la solución a sus subproblemas, y si sus subproblemas se superponen, uno puede memorizar o almacenar fácilmente las soluciones a los subproblemas en una tabla. Siempre que intentemos resolver un nuevo subproblema, primero revise la tabla para ver si ya está resuelto. Si el subproblema ya está resuelto, utilice su solución directamente; de lo contrario, resuelve el subproblema y agrega su solución a la tabla.
- Enfoque ascendente (tabulación): Una vez que formulamos la solución a un problema recursivamentemente en términos de sus subproblemas, podemos intentar reformular el problema de forma ascendente: intente resolver los subproblemas primero y use sus soluciones para desarrollar y llegar a soluciones a subproblemas más grandes. Esto también se suele hacer en forma tabular mediante la generación iterativa de soluciones para subproblemas cada vez más grandes mediante el uso de soluciones para subproblemas pequeños. Por ejemplo, si ya conocemos los valores de
F(i-1)yF(i-2), podemos calcular directamente el valor deF(i).
Si un problema se puede resolver combinando soluciones óptimas a subproblemas que no se superponen, la estrategia se llama Divide y Vencerás en cambio. Esta es la razón por ordenar por fusión y Ordenación rápida no se clasifican como problemas de programación dinámica.
Consideremos una implementación ingenua de una función que encuentra el n'th miembro de la sucesión de Fibonacci:
|
1 2 3 4 5 6 7 8 9 |
// Función para encontrar el n'ésimo número de Fibonacci int fib(int n) { if (n <= 1) { return n; } return fib(n - 1) + fib(n - 2); } |
Note que si llamamos, digamos, fib(5), producimos un árbol de llamadas que llama a la función en el mismo valor muchas veces:
En particular, fib(3) se calculó dos veces y fib(2) se calculó tres veces desde cero. En ejemplos más grandes, se recalculan muchos más subproblemas, lo que lleva a un algoritmo de tiempo exponencial.
Ahora, supongamos que tenemos un objeto de mapa simple, lookup, que mapea cada valor de fib que ya ha sido calculado a su resultado, y modificamos nuestra función para usarlo y actualizarlo. La función resultante se ejecuta en O(n) tiempo en lugar de tiempo exponencial (pero requiere O(n) espacio):
A continuación se muestra la implementación de la programación dinámica en C++, Java y Python basada en la idea anterior:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <unordered_map> using namespace std; // Función para encontrar el n'ésimo número de Fibonacci int fib(int n, auto &lookup) { if (n <= 1) { return n; } // si el subproblema se ve por primera vez if (lookup.find(n) == lookup.end()) { lookup[n] = fib(n - 1, lookup) + fib(n - 2, lookup); } return lookup[n]; } int main() { unordered_map<int, int> lookup; cout << fib(8, lookup); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.HashMap; import java.util.Map; class Main { // Función para encontrar el n-ésimo número de Fibonacci public static int fib(int n, Map<Integer, Integer> lookup) { if (n <= 1) { return n; } // si el subproblema se ve por primera vez if (!lookup.containsKey(n)) { int val = fib(n - 1, lookup) + fib(n - 2, lookup); lookup.put(n, val); } return lookup.get(n); } public static void main(String[] args) { int n = 8; Map<Integer, Integer> lookup = new HashMap<>(); System.out.println(fib(n, lookup)); } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# Función para encontrar el n-ésimo número de Fibonacci def fib(n, lookup): if n <= 1: return n # si el subproblema se ve por primera vez if n not in lookup: val = fib(n - 1, lookup) + fib(n - 2, lookup) lookup[n] = val return lookup[n] if __name__ == '__main__': n = 8 lookup = {} print(fib(n, lookup)) |
Tenga en cuenta que también podemos usar una array en lugar de un mapa. Comprobar la implementación aquí.
Como ya se discutió, esta técnica de guardar valores que ya han sido calculados se llama memoización; este es el enfoque de arriba hacia abajo ya que primero dividimos el problema en subproblemas y luego calculamos y almacenamos valores.
En el enfoque ascendente, calculamos los valores más pequeños de fib primero, luego construya valores más grandes a partir de ellos. Este método también utiliza O(n) tiempo ya que contiene un bucle que se repite n-1 veces, pero solo se necesita constante O(1) espacio, en contraste con el enfoque de arriba hacia abajo, que requiere O(n) espacio para almacenar el mapa.
El siguiente es el programa C++, Java y Python que lo demuestra:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <unordered_map> using namespace std; // Función para encontrar el n'ésimo número de Fibonacci int fib(int n) { if (n <= 1) { return n; } int previousFib = 0, currentFib = 1; for (int i = 0; i < n - 1; i++) { int newFib = previousFib + currentFib; previousFib = currentFib; currentFib = newFib; } return currentFib; } int main() { cout << fib(8); return 0; } |
Resultado:
21
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Main { // Función para encontrar el n'ésimo número de Fibonacci public static int fib(int n) { if (n <= 1) { return n; } int previousFib = 0, currentFib = 1; for (int i = 0; i < n - 1; i++) { int newFib = previousFib + currentFib; previousFib = currentFib; currentFib = newFib; } return currentFib; } public static void main(String[] args) { System.out.print(fib(8)); } } |
Resultado:
21
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# Función para encontrar el n'ésimo número de Fibonacci def fib(n): if n <= 1: return n previousFib = 0 currentFib = 1 for i in range(n - 1): newFib = previousFib + currentFib previousFib = currentFib currentFib = newFib return currentFib if __name__ == '__main__': print(fib(8)) |
Resultado:
21
En ambos ejemplos, sólo calculamos fib(2) una vez y luego utilícelo para calcular ambos fib(4) y fib(3), en lugar de calcularlo cada vez que se evalúa cualquiera de ellos.
Fuente: https://en.wikipedia.org/wiki/Dynamic_programming
Ver también:
Programación Dinámica – Preguntas de Entrevista y Problemas de Práctica