Introducción a los algoritmos: programación dinámica

Suponga que está haciendo algún cálculo usando una serie apropiada de entrada. Se realizan algunos cálculos en cada instancia para obtener algún resultado. No sabe que ha encontrado la misma salida cuando ha proporcionado la misma entrada . Es como si estuvieras haciendo un recálculo de un resultado que se logró previamente mediante una entrada específica para su salida respectiva.

¿Pero cuál es el problema aquí? La cosa es que su precioso tiempo está perdido. Aquí puede resolver fácilmente el problema manteniendo registros que mapeen los resultados calculados previamente. Como utilizar la estructura de datos adecuada. Por ejemplo, puede almacenar la entrada como clave y la salida como un valor (parte del mapeo).

Aquellos que no pueden recordar el pasado están condenados a repetirlo. ~ Programación dinámica

Ahora, analizando el problema, almacene su entrada si es nueva (o no está en la estructura de datos) con su salida respectiva. De lo contrario, verifique esa clave de entrada y obtenga la salida resultante de su valor. De esa manera, cuando haga algunos cálculos y verifique si esa entrada existía en esa estructura de datos, puede obtener el resultado directamente. Por tanto, podemos relacionar este enfoque con las técnicas de programación dinámica.

Bucear en la programación dinámica

En pocas palabras, podemos decir que la programación dinámica se usa principalmente para optimizar problemas, donde deseamos encontrar la "mejor" forma de hacer algo.

Cierto escenario es como si hubiera subproblemas recurrentes que a su vez tienen sus propios subproblemas más pequeños. En lugar de intentar resolver esos subproblemas que reaparecen, una y otra vez, la programación dinámica sugiere resolver cada uno de los subproblemas más pequeños solo una vez. Luego, registra los resultados en una tabla a partir de la cual se puede obtener una solución al problema original.

Por ejemplo, los números de Fibonacci 0,1,1,2,3,5,8,13,…tienen una descripción simple en la que cada término está relacionado con los dos términos anteriores. Si F(n)es el ntérmino de esta serie, entonces tenemos F(n) = F(n-1) + F(n-2). Esto se llama fórmula recursiva o relación de recurrencia. Es necesario que se hayan calculado términos anteriores para calcular un término posterior.

La mayoría de los problemas de programación dinámica se pueden clasificar en dos tipos:

  1. Problemas de optimización.
  2. Problemas combinatorios.

Los problemas de optimización esperan que seleccione una solución factible para minimizar o maximizar el valor de la función requerida. Los problemas combinatorios esperan que averigües la cantidad de formas de hacer algo o la probabilidad de que suceda algún evento.

Un enfoque para resolver: de arriba hacia abajo vs de abajo hacia arriba

Existen las siguientes dos formas principales de resolver el problema:

De arriba hacia abajo: comienza desde arriba, resolviendo el problema desglosándolo. Si ve que el problema ya se ha resuelto, devuelva la respuesta guardada. Esto se conoce como memorización.

De abajo hacia arriba: directamente comienza a resolver los subproblemas más pequeños y se abre camino hacia la cima para obtener la solución final de ese gran problema. En este proceso, se garantiza que los subproblemas se resuelven antes de resolver el problema. Esto se puede llamar tabulación ( algoritmo de llenado de tablas ).

En referencia a la iteración frente a la recursividad, de abajo hacia arriba usa la iteración y de arriba hacia abajo usa la recursividad.

Aquí hay una comparación entre un enfoque ingenuo y un enfoque de DP. Puedes ver la diferencia por la complejidad temporal de ambos.

Memorización: no olvides

Jeff Erickson describe en sus notas, para los números de Fibonacci:

La razón obvia de la falta de velocidad del algoritmo recursivo es que calcula los mismos números de Fibonacci una y otra vez.

Podemos acelerar nuestro algoritmo recursivo considerablemente simplemente escribiendo los resultados de nuestras llamadas recursivas. Luego, podemos buscarlos nuevamente si los necesitamos más tarde.

La memorización se refiere a la técnica de almacenamiento en caché y reutilización de resultados calculados previamente.

Si usa la memorización para resolver el problema, lo hace manteniendo un mapa de subproblemas ya resueltos (como hablamos anteriormente sobre el mapeo de clave y valor). Lo hace "de arriba hacia abajo " en el sentido de que primero resuelve el problema "de arriba" (que normalmente se repite hacia abajo para resolver los subproblemas).

Pseudocódigo para memorización :

Entonces, usando la recursividad, realizamos esto con memoria adicional adicional (es decir, aquí la búsqueda) para almacenar los resultados. Si hay un valor almacenado en la búsqueda, lo devolvemos directamente o lo agregamos para buscar ese índice específico.

Recuerde que existe una compensación de gastos generales adicionales con respecto al método de tabulación.

Sin embargo, si desea más visualizaciones para la memorización, le sugiero que mire este video.

Tabulación: llenado en forma tabular

Pero una vez que vemos cómo se llena la matriz (solución memorizada), podemos reemplazar la recursividad con un bucle simple que llena intencionalmente la matriz en orden, en lugar de depender de la complicada recursividad para que lo haga por nosotros 'accidentalmente'.

La tabulación lo hace "de abajo hacia arriba" . Es más sencillo, calcula todos los valores. Requiere menos gastos generales ya que no tiene que mantener el mapeo y almacena datos en forma tabular para cada valor. También puede calcular valores innecesarios. Esto se puede usar si todo lo que desea es calcular todos los valores para su problema.

Pseudocódigo para tabulación:

Como puede ver el pseudocódigo (lado derecho) en una imagen, realiza una iteración (es decir, se repite hasta el final de una matriz). Simplemente comienza con fib (0), fib (1), fib (2),… Entonces, con el enfoque de tabulación, podemos eliminar la necesidad de recursividad y simplemente devolver el resultado con elementos en bucle.

Mirando hacia atrás en la historia

Richard bellman fue el hombre detrás de este concepto. Se le ocurrió esto cuando trabajaba para RAND Corporation a mediados de la década de 1950. La razón por la que eligió este nombre "programación dinámica" fue para ocultar el trabajo matemático que hizo para esta investigación. Temía que sus jefes se opusieran o no les gustara cualquier tipo de investigación matemática.

Bien, entonces la palabra 'programación' es solo una referencia para aclarar que esta era una forma anticuada de planificar o programar, típicamente llenando una tabla (de manera dinámica en lugar de lineal) a lo largo del tiempo en lugar de de repente.

Terminando

Eso es. Esta es la parte 2 de la serie de algoritmos que comencé el año pasado. En mi publicación anterior, discutimos sobre qué son los algoritmos de búsqueda y clasificación. Disculpas que no pude entregar esto en menos tiempo. Pero estoy dispuesto a acelerar las cosas en los próximos meses.

Espero que les haya gustado y pronto estaré buscando agregar un tercero en la serie pronto. ¡Feliz codificación!

Recursos:

Introducción a la programación dinámica 1 Tutoriales y notas | Algoritmos | HackerEarth

La imagen de arriba dice mucho sobre la programación dinámica. Entonces, está repitiendo las cosas para las que ya tienes la… Comunidad www.hackerearth.com - Programación competitiva - Tutoriales de programación competitiva - Programación dinámica: Desde…

Comunidad - Programación competitiva - Tutoriales de programación competitiva - Programación dinámica: de principiante a avanzado www.topcoder.com

//www.geeksforgeeks.org/overlapping-subproblems-property-in-dynamic-programming-dp-1/

Apoyos especiales para Jeff Erickson y sus notas para el algoritmo - //jeffe.cs.illinois.edu/