Materia: #técnicas_y_diseños_de_algoritmos

Tags:

Programación dinámica

La programación dinámica mas que un algoritmo es un enfoque que podemos utilizar a la hora de resolver un problema. De hecho, la mayoría de algoritmos se pueden implementar de manera dinámica, o incluso necesitan una implementación estrictamente dinámica.

La idea es bastante sencilla: utilicemos la memoria. Podemos ir guardando soluciones parciales, o previamente calculadas, y reservarles un espacio en memoria. De ese modo, si a posteriori se quiere calcular uno de los valores que tenemos guardados, simplemente accedemos a ese valor. Es decir, la complejidad se ve reducida a un simple problema de búsqueda, lo cual depende de como decidamos estructurar la información. Es un enfoque similar al de dividir y conquistar, ya que tenemos que separar el problema inicial en subproblemas mas pequeños.

Este enfoque es tremendamente útil si sabemos que a la hora de implementar nuestro algoritmo puede llegar a haber superposición de estados. Es decir, que el árbol de llamadas (generalmente recursivas) tiene muchos nodos que son iguales, o sea que consisten en los mismos parámetros de entrada.

Los algoritmos que utilizan programación dinámica suelen separarse en dos esquemas: top-down y bottom-up.

Enfoque top-down

Esta metodología consiste en una implementación recursiva del algoritmo, en la que se genera una estructura de datos que se va a ir completando a medida que sucedan los llamados. Si en algún momento de la ejecución, un llamado toma por parámetros un valor que ya se encuentra en la estructura de guardado, entonces automáticamente devuelve lo que se encuentre en dicha estructura.

Una forma de visualizar esto es con el árbol de llamados. Si tenemos una función $f(n,k)$, definida como $f(n,k)=f(n-1,k)+f(n,k-1)\text{, con }k<n$, podríamos representar el pensamiento top-down de la siguiente forma:

graph TD;
id1("f(n, k)")
id2("f(n-1, k)")
id3("f(n, k-1)")
id4("f(n-2, k)")
id5("f(n-1, k-1)")
id6("f(n-1, k-1)")
id7("f(n, k-2)")

id1 --> id2
id1 --> id3
id2 --> id4
id2 --> id5
id3 --> id6
id3 --> id7

Como pueden ver, solo nos llevo 3 niveles del árbol para llegar a valores repetidos. Por ejemplo, es fácil notar que $f(n-1,k)$ aparece dos veces, por lo que al calcularlo una vez ya nos bastaría para obtener el otro.

Enfoque bottom-up

Por otro lado, el esquema bottom-up empieza por los subproblemas mas pequeños, y guarda (generalmente en una tabla) los resultados calculados.

Acá, a diferencia del anterior, partimos desde las bases del problema. Si tomamos el ejemplo de antes, tenemos que $f(n,k)=f(n-1,k)+f(n,k-1)\text{, con }k<n$, y ahora supongamos que sus casos bases son $f(0,k)=1$ y $f(n,n)=1$. Podríamos representar las posibles respuestas de la función según la siguiente tabla:

Esta tabla es la que vamos a tener guardar en la memoria. Lo que hacemos al llamar a la función, es ubicarnos en la tabla usando los parámetros de entrada como índices. Si la celda se encuentra vacía, vamos desde los valores conocidos de la tabla formando los necesarios para el valor pedido. Si, por otro lado, la celda tenia un valor escrito, significa que fue previamente calculado.