Programacion Dinamica y Algoritmos Voraces.

Ahora es turno de describir otra estrategia para resolver problemas, vimos que para los ordenamientos utilizamos el paradigma de divide y vencerás, sin embargo cuando podemos descomponer un problema en varios sub-problemas y estos a su vez tienen otros problemas superpuestos es decir  estos sub-problemas pueden necesitar repetirse varias veces mientras resolvemos el problema inicial, entonces es un indicio de que podemos resolver el problema usando Programación Dinámica, la cual es una estrategia de programación usada cuando se desea evitar el calculo repetido de sub-problemas  guardando el calculo de la solución para el problema que se repite y evitando la repetición del calculo para este mismo, es también buena idea usar programación dinámica cuando notamos que nuestro problema tiene una sub estructura optima, esto es cuando para hallar la solución optima del problema inicial tenemos que también hallar una solución optima para los sub-problemas en los que dividimos el problema inicial, en otras palabras nos ayuda para resolver problemas de optimización. Una buena manera de saber si podríamos necesitar programación dinámica es pensar en una solución para el problema, si dicha solución "inocente" tiene una complejidad cuadrática entonces es posible que necesitemos usar programación dinámica. Para desarrollar un algoritmo usando programación dinámica necesitaremos una secuencia de 4 pasos que serán, primero la caracterización de la solución, es decir, describir la estructura de nuestra solución optima, visualizar la solución optima de nuestro problema para posteriormente aplicar el segundo paso, la recursión, que sera definir el valor de esta solución optima de manera recursiva, construyendo el algoritmo recursivo, lo siguiente es el tercer paso la memorización donde calcularemos el valor optimo y veremos donde guardar nuestros valores previos para poder utilizarlos posteriormente, finalmente el ultimo paso es la construcción de la solución optima esta es dada por la información que ya calculamos anteriormente. Cabe mencionar que también se puede utilizar la programación dinámica utilizando la tabulacion que es la técnica de resolver iterativamente desde el sub-problema mas pequeño hasta el sub-problema principal construyendo una tabla con los resultados y haciendo uso de la misma durante la resolución de los problemas. Como siempre se deja un video de apoyo para comprender de mejor manera el tema con ejemplos para una mayor claridad de la mano del canal ChioCode:

 

 

Algunos ejemplos populares de problemas que pueden ser resueltos con programación dinámica son encontrar la subsecuencia común mas larga o la multiplicación de una secuencia de matrices, particularmente encontrar la subsecuencia común mas larga es interesante por que puede ser extendida al reconocimiento de patrones lo cual es útil cuando hablamos de inteligencia artificial y lo que refiere al análisis y comparación de datos, a continuación se dejan 2 videos de apoyo que ilustran la solución de ambos problemas de manera amplia utilizando programación dinámica:

 Algoritmo para encontrar la subsecuencia común mas larga de la mano del canal de youtube Xavier Ochoa:

 

 Algoritmo para la multiplicación de una secuencia de matrices de la mano del canal de youtube Preparación Estudiantil de 10:

 

De la mano con la programación dinámica vienen también los algoritmos voraces o greedy algorithms que son usados cuando se nos presentan problemas que tienen sub-problemas cuyas posibles soluciones son demasiadas, estos algoritmos tienen como principio que si se topan con varias opciones se elija la que parece mas adecuada en ese momento, este puede en un principio no dar la solución optima a todos los problemas pero puede dar una solución suficiente para los mismos, el principio de elegir la opción mas optima en lugar de calcular todas las posibles soluciones y de entre ellas elegir la mas optima puede resultar mas intuitivo y sencillo, entonces hay que saber, ¿como podemos ver si con un algoritmo voraz es suficiente para resolver el problema y no tener que quebrarnos la cabeza con la solución de programación dinámica?, pues lo cierto es que al ir de la mano ambos conceptos para cada solución que utiliza un algoritmo voraz, generalmente existe otra solución al problema usando programación dinámica pero esta solución suele ser mas complicada, entonces para ver si nuestro problema puede ser resuelto con un algoritmo voraz necesitamos prestar atención a 2 propiedades la sub-estructura optima y la selección greedy, la sub-estructura optima es como mencionamos antes, dado un problema principal, si la solución optima de este problema necesita la solución optima de los sub-problemas que vallamos generando, esto indica que tenemos una sub-estructura optima, la segunda y mas importante es la selección greedy la cual consta de saber que podemos construir la solución optima global  usando la elección de las opciones locales sin tener en cuenta los resultados de otros sub-problemas, es decir, tenemos que poder realizar esta elección sin depender de los resultados de los otros sub-problemas, tenemos ademas que probar que esta elección que realizamos en el algoritmo lleve a la solución optima global, esto se hace examinando alguna solución optima global que tenga algunos sub-problemas, suponemos que nuestro algoritmo greedy no da la solución optima con la selección que tenemos, entonces usamos una selección alternativa a la que toma nuestro algoritmo y eventualmente si la selección alternativa da una solución  menos optima llegaremos a una contradicción por que se supone que nuestro algoritmo greedy no da la solución optima, con esta contradicción exhibida podemos decir que la contradicción viene de suponer que nuestro algoritmo greedy no era optimo y por ende para que no exista contradicción entonces nuestro algoritmo greedy es en efecto optimo, lo complicado para estos casos es entonces demostrar que nuestro algoritmo voraz da la solución optima siempre. A continuación se deja un video de apoyo sobre el tema de la mano del canal de youtube ChioCode en el que muestra también algunos ejemplos, ademas se anexan otros 2 videos de ejemplos concretos con problemas solucionados con algoritmos voraces:

 

Algoritmos voraces:

 

 

 

Algoritmo para maximizar el numero de programas que cabe en un disco de la mano del canal de youtube Facultad de Informática - Universidad Complutense de Madrid:

 

 Algoritmo para resolver el problema de a mochila fraccionada de la mano del canal de youtube courEZ programacion: