algorithm
Aplicaciones de Programación Dinámica.
Buscar..
Introducción
La idea básica detrás de la programación dinámica es dividir un problema complejo en varios problemas pequeños y simples que se repiten. Si puede identificar un subproblema simple que se calcula repetidamente, es probable que exista un enfoque de programación dinámico para el problema.
Como este tema se titula Aplicaciones de programación dinámica , se centrará más en las aplicaciones que en el proceso de creación de algoritmos de programación dinámica.
Observaciones
Definiciones
Memorización : una técnica de optimización utilizada principalmente para acelerar los programas informáticos al almacenar los resultados de llamadas a funciones costosas y devolver el resultado almacenado en caché cuando vuelven a ocurrir las mismas entradas.
Programación dinámica : 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.
Números de Fibonacci
Los números de Fibonacci son un tema primordial para la programación dinámica, ya que el enfoque recursivo tradicional realiza muchos cálculos repetidos. En estos ejemplos usaré el caso base de f(0) = f(1) = 1 .
Aquí hay un ejemplo de árbol recursivo para fibonacci(4) , note los cálculos repetidos: 
Programación no dinámica O(2^n) Complejidad en tiempo de ejecución, O(n) Complejidad de pila
def fibonacci(n):
if n < 2:
return 1
return fibonacci(n-1) + fibonacci(n-2)
Esta es la forma más intuitiva de escribir el problema. A lo sumo, el espacio de la pila será O(n) medida que descienda la primera rama recursiva haciendo llamadas a fibonacci(n-1) hasta que llegue al caso base n < 2 .
La O(2^n) prueba de complejidad en tiempo de ejecución que se puede ver aquí: Complejidad computacional de la secuencia de Fibonacci . El punto principal a tener en cuenta es que el tiempo de ejecución es exponencial, lo que significa que el tiempo de ejecución para esto se duplicará para cada término subsiguiente, fibonacci(15) tomará el doble de tiempo que fibonacci(14) .
Memoized O(n) Complejidad de tiempo de ejecución, O(n) Complejidad de espacio, O(n) Complejidad de pila
memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1
def fibonacci(n):
if len(memo) > n:
return memo[n]
result = fibonacci(n-1) + fibonacci(n-2)
memo.append(result) # f(n) = f(n-1) + f(n-2)
return result
Con el enfoque memorizado, introducimos una matriz que puede considerarse como todas las llamadas de función anteriores. La memo[n] ubicación memo[n] es el resultado de la función llamada fibonacci(n) . Esto nos permite intercambiar la complejidad de espacio de O(n) por un tiempo de ejecución O(n) ya que ya no necesitamos calcular llamadas de función duplicadas.
Programación dinámica iterativa O(n) Complejidad en tiempo de ejecución, O(n) Complejidad de espacio, No pila recursiva
def fibonacci(n):
memo = [1,1] # f(0) = 1, f(1) = 1
for i in range(2, n+1):
memo.append(memo[i-1] + memo[i-2])
return memo[n]
Si dividimos el problema en sus elementos centrales, notará que para calcular fibonacci(n) necesitamos fibonacci(n-1) y fibonacci(n-2) . También podemos notar que nuestro caso base aparecerá al final de ese árbol recursivo como se ve arriba.
Con esta información, ahora tiene sentido calcular la solución hacia atrás, comenzando en los casos base y trabajando hacia arriba. Ahora, para calcular la fibonacci(n) , primero calculamos todos los números de fibonacci hasta n .
Este beneficio principal aquí es que ahora hemos eliminado la pila recursiva mientras mantenemos el tiempo de ejecución O(n) . Desafortunadamente, todavía tenemos una complejidad de espacio O(n) , pero eso también se puede cambiar.
Programación dinámica iterativa avanzada O(n) Complejidad en tiempo de ejecución, O(1) Complejidad de espacio, No pila recursiva
def fibonacci(n):
memo = [1,1] # f(1) = 1, f(2) = 1
for i in range (2, n):
memo[i%2] = memo[0] + memo[1]
return memo[n%2]
Como se señaló anteriormente, el enfoque de programación dinámica iterativa comienza desde los casos base y funciona hasta el resultado final. La observación clave a realizar para llegar a la complejidad del espacio a O(1) (constante) es la misma observación que hicimos para la pila recursiva: solo necesitamos fibonacci(n-1) y fibonacci(n-2) para construir fibonacci(n) . Esto significa que solo necesitamos guardar los resultados de fibonacci(n-1) y fibonacci(n-2) en cualquier punto de nuestra iteración.
Para almacenar estos últimos 2 resultados, utilizo una matriz de tamaño 2 y simplemente invierto el índice al que estoy asignando utilizando i % 2 que alternará así: 0, 1, 0, 1, 0, 1, ..., i % 2 .
Agrego ambos índices de la matriz juntos porque sabemos que la adición es conmutativa ( 5 + 6 = 11 y 6 + 5 == 11 ). El resultado se asigna al más antiguo de los dos puntos (indicado por i % 2 ). El resultado final se almacena en la posición n%2
Notas
- Es importante tener en cuenta que a veces puede ser mejor encontrar una solución memorizada iterativa para funciones que realizan cálculos grandes repetidamente, ya que acumulará un caché de la respuesta a las llamadas de función y las llamadas subsiguientes pueden ser
O(1)si ya ha sido computado