La Programación Dinámica

La técnica de la programación dinámica es una técnica que se utiliza en programación y que utiliza resultados parciales que se van produciendo durante la resolución de los problemas para llegar al resultado final.

Esta forma de resolver problemas, cómo ya hemos dicho anteriormente, va resolviendo el problema registrando los resultados parciales que va obteniendo y que posteriormente utiliza para obtener la solución final, lo que le permite reducir el coste computacional mejorando así su eficencia.

Por tanto podemos afirmar que la programación dinámica es una técnica con la que podemos reducir el coste de ejecución de un algoritmo memorizando las soluciones parciales que vamos obteniendo para así llegar a la solución final del problema. Algunos problemas en los que es aplicable esta técnica se pueden resolver con la técnica de divide y vencerás que vimos en una entrada anterior. 

Por regla general los resultados que se van obteniendo al aplicar los algoritmos con esta técnica se van almacenando en una tabla de la que posteriormente se van tomando cuando el algoritmo los vuelve a necesitar. Los primeros datos corresponden a los subproblemas más sencillos y a partir de ellos se van construyendo de forma incremental las soluciones a los subproblemas mayores hasta llegar a la resolución del problema completo.

La reducción del coste computacional de la que hablabamos antes tiene un precio y ese precio es el incremento del coste espacial ya que el almacenamiento de las soluciones parciales que vamos obteniendo requiere incrementar el espacio dedicado a los datos que usará nuestro algoritmo.

La forma en la que se aplica esta técnica es muy dependiente del problema que tratemos y la estructura de datos que se utilice para su resolución pero cómo regla general podemos establecer la siguiente secuencia para resolver un problema utilizando la programación dinámica. Primeramente hay que establecer las ecuaciones que representan el problema que tenemos que resolver, seguidamente tenemos que identificar cuales son los resultados parciales que vamos a ir obteniendo y cómo estos nos van a permitir llegar a la solución final. Tras estos pasos tenemos que construir la tabla de resultados parciales que nos llevará a la solución final. Primeramente la inicializaríamos con los casos base de nuestro problema, después la iríamos llenando de forma que se vayan introduciendo primero los resultados parciales que no requieren pasos anteriores para después llenarla con los resultados que necesitan de esos resultados parciales que ya hemos obtenido en los pasos anteriores para así llegar al resultado final.

Esta forma de programación dinámica se utiliza en muchos problemas cómo por ejemplo en los coeficientes binomiales, problemas de devolución de cambio, la multiplicación asociativa de matrices, la mochila, etc.

La programación dinámica nos abre un mundo lleno de posibilidades a la hora de resolver problemas y de utilizar algoritmos de una forma más eficiente como hemos dicho anteriormente.

Si queréis que profundicemos más sobre esta técnica no dudéis en ponerlo en los comentarios.

;)