Diferencia entre dividir y conquistar Algo y programación dinámica

¿Cuál es la diferencia entre los algoritmos de división y conquista y los algoritmos de programación dinámica? ¿Cómo son los dos términos diferentes? No entiendo la diferencia entre ellos.

Tome un ejemplo simple para explicar cualquier diferencia entre los dos y en qué base parecen ser similares.

Divide y conquistaras

Dividir y conquistar funciona dividiendo el problema en subproblemas, conquistar cada subproblema de forma recursiva y combinar estas soluciones.

Programación dinámica

La programación dinámica es una técnica para resolver problemas con subproblemas superpuestos. Cada subproblema se resuelve solo una vez y el resultado de cada subproblema se almacena en una tabla (generalmente implementada como una matriz o una tabla hash) para futuras referencias. Estas sub-soluciones pueden usarse para obtener la solución original y la técnica de almacenamiento de las soluciones de subproblemas se conoce como memorización.

Puedes pensar en DP = recursion + re-use

Un ejemplo clásico para comprender la diferencia sería ver ambos enfoques para obtener el enésimo número de fibonacci. Revise este material del MIT.

Enfoque de dividir y conquistar

Enfoque de programación dinámica

La otra diferencia entre divide y vencerás y la programación dinámica podría ser:

Divide y conquistaras:

1. Trabaja más en los subproblemas y, por lo tanto, consume más tiempo.
2. En divide y vencerás los subproblemas son independientes entre sí.

Programación dinámica:

1. Resuelve los subproblemas solo una vez y luego los almacena en la tabla.
2. En la programación dinámica, el subproblema no es independiente.

a veces, cuando se programa de forma recursiva, se llama a la función con los mismos parámetros varias veces, lo cual es innecesario.

El famoso ejemplo de los números de Fibonacci:

           index: 1,2,3,4,5,6...
Fibonacci number: 1,1,2,3,5,8...

function F(n) {
    if (n < 3)
        return 1
    else
        return F(n-1) + F(n-2)
}

Ejecutemos F (5):

F(5) = F(4) + F(3)
     = {F(3)+F(2)} + {F(2)+F(1)}
     = {[F(2)+F(1)]+1} + {1+1}
     = 1+1+1+1+1

Entonces hemos llamado: 1 veces F (4) 2 veces F (3) 3 veces F (2) 2 veces F (1)

Enfoque de programación dinámica: si llama a una función con el mismo parámetro más de una vez, guarde el resultado en una variable para acceder directamente a ella la próxima vez. La forma iterativa:

if (n==1 || n==2)
    return 1
else
    f1=1, f2=1
    for i=3 to n
         f = f1 + f2
         f1 = f2
         f2 = f

Llamemos a F (5) nuevamente:

fibo1 = 1
fibo2 = 1 
fibo3 = (fibo1 + fibo2) = 1 + 1 = 2
fibo4 = (fibo2 + fibo3) = 1 + 2 = 3
fibo5 = (fibo3 + fibo4) = 2 + 3 = 5

Como puede ver, cada vez que necesita la llamada múltiple solo tiene que acceder a la variable correspondiente para obtener el valor en lugar de volver a calcularlo.

Por cierto, la programación dinámica no significa convertir un código recursivo en un código iterativo. También puede guardar los resultados secundarios en una variable si desea un código recursivo. En este caso, la técnica se llama memorización. Para nuestro ejemplo, se ve así:

// declare and initialize a dictionary
var dict = new Dictionary<int,int>();
for i=1 to n
    dict[i] = -1

function F(n) {
    if (n < 3)
        return 1
    else
    {
        if (dict[n] == -1)
            dict[n] = F(n-1) + F(n-2)

        return dict[n]                
    }
}

Entonces, la relación con Divide and Conquer es que los algoritmos D&D dependen de la recursividad. Y algunas versiones de ellos tienen esta "llamada de función múltiple con el mismo problema de parámetros". Busque "multiplicación de la cadena de la matriz" y "subsecuencia común más larga" para ver ejemplos en los que se necesita DP para mejorar la T (n) de D&D.

Programación dinámica y similitudes de divide y vencerás

Como lo veo por ahora, puedo decir que la programación dinámica es una extensión del paradigma de divide y vencerás .

No los trataría como algo completamente diferente. Debido a que ambos funcionan dividiendo recursivamente un problema en dos o más subproblemas del mismo tipo o relacionados, hasta que estos se vuelven lo suficientemente simples como para ser resueltos directamente. Las soluciones a los subproblemas se combinan para dar una solución al problema original.

Entonces, ¿por qué todavía tenemos diferentes nombres de paradigma y por qué llamé a la programación dinámica una extensión? Esto se debe a que el enfoque de programación dinámica puede aplicarse al problema solo si el problema tiene ciertas restricciones o requisitos previos . Y después de eso, la programación dinámica extiende el enfoque de divide y vencerás con la técnica de memorización o tabulación .

Vamos paso a paso ...

Prerrequisitos / restricciones de programación dinámica

Como acabamos de descubrir, hay dos atributos clave que deben dividir y vencer el problema para que la programación dinámica sea aplicable:

• Subestructura  óptima: la solución óptima se puede construir a partir de soluciones óptimas de sus subproblemas

• Subproblemas superpuestos  : el problema se puede dividir en subproblemas que se reutilizan varias veces o un algoritmo recursivo para el problema resuelve el mismo subproblema una y otra vez en lugar de generar siempre nuevos subproblemas

Una vez que se cumplan estas dos condiciones, podemos decir que este problema de divide y vencerás puede resolverse usando un enfoque de programación dinámica.

Extensión de programación dinámica para dividir y conquistar

El enfoque de programación dinámica extiende el enfoque de divide y vencerás con dos técnicas ( memorización y tabulación ) que tienen el propósito de almacenar y reutilizar soluciones de subproblemas que pueden mejorar drásticamente el rendimiento. Por ejemplo, la implementación recursiva ingenua de la función Fibonacci tiene una complejidad de tiempo O(2^n)en la que la solución DP hace lo mismo con solo O(n)tiempo.

La memorización (relleno de caché de arriba hacia abajo) se refiere a la técnica de almacenamiento en caché y reutilización de resultados previamente calculados. La fibfunción memorizada se vería así:

memFib(n) {
    if (mem[n] is undefined)
        if (n < 2) result = n
        else result = memFib(n-2) + memFib(n-1)

        mem[n] = result
    return mem[n]
}

La tabulación (relleno de caché de abajo hacia arriba) es similar, pero se centra en llenar las entradas de la caché. Calcular los valores en el caché es más fácil de hacer de forma iterativa. La versión de tabulación de fibse vería así:

tabFib(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

Puede leer más sobre la comparación de memorización y tabulación aquí .

La idea principal que debe comprender aquí es que debido a que nuestro problema de dividir y conquistar tiene subproblemas superpuestos, el almacenamiento en caché de las soluciones de subproblemas se hace posible y, por lo tanto, la memorización / tabulación pasa a la escena.

Entonces, ¿cuál es la diferencia entre DP y DC después de todo

Como ahora estamos familiarizados con los requisitos previos de DP y sus metodologías, estamos listos para poner todo lo que se mencionó anteriormente en una sola imagen.

Si desea ver ejemplos de código, puede echar un vistazo a una explicación más detallada aquí, donde encontrará dos ejemplos de algoritmos: Búsqueda binaria y Distancia mínima de edición (Distancia de Levenshtein) que ilustran la diferencia entre DP y DC.

Supongo que ya has leído Wikipedia y otros recursos académicos sobre esto, así que no reciclaré ninguna de esa información. También debo advertir que no soy un experto en informática de ninguna manera, pero compartiré mis dos centavos en mi comprensión de estos temas ...

Programación dinámica

Descompone el problema en subproblemas discretos. El algoritmo recursivo para la secuencia de Fibonacci es un ejemplo de programación dinámica, porque resuelve fib (n) resolviendo primero fib (n-1). Para resolver el problema original, resuelve un problema diferente .

Divide y conquistaras

Estos algoritmos generalmente resuelven partes similares del problema y luego las unen al final. Mergesort es un ejemplo clásico de divide y vencerás. La principal diferencia entre este ejemplo y el ejemplo de Fibonacci es que en un mergesort, la división puede (teóricamente) ser arbitraria, y no importa cómo se divida, todavía se está fusionando y ordenando. Se debe hacer la misma cantidad de trabajo para fusionar la matriz, sin importar cómo se divida. Resolver para fib (52) requiere más pasos que resolver para fib (2).

Pienso Divide & Conqueren un enfoque recursivo y Dynamic Programmingcomo un relleno de mesa.

Por ejemplo, Merge Sortes un Divide & Conqueralgoritmo, ya que en cada paso, divide la matriz en dos mitades, recurre recursivamente Merge Sorta las dos mitades y luego las fusiona.

Knapsackes un Dynamic Programmingalgoritmo ya que está llenando una tabla que representa soluciones óptimas para subproblemas de la mochila en general. Cada entrada en la tabla corresponde al valor máximo que puede llevar en una bolsa de peso con los artículos 1-j.

Divide y vencerás implica tres pasos en cada nivel de recursión:

1. Divide el problema en subproblemas.
2. Conquista los subproblemas resolviéndolos recursivamente.
3. Combine la solución para subproblemas en la solución para el problema original.
   
   • Es un enfoque de arriba hacia abajo .
     
   • Hace más trabajo en subproblemas y, por lo tanto, consume más tiempo.
   • p.ej. El enésimo término de la serie de Fibonacci se puede calcular en O (2 ^ n) complejidad de tiempo.
     
     

La programación dinámica implica los siguientes cuatro pasos:

1. Caracterizar la estructura de soluciones óptimas.
2. Definir recursivamente los valores de soluciones óptimas.
3. Calcule el valor de las soluciones óptimas.
4. Construya una solución óptima a partir de la información calculada .

• Es un enfoque de abajo hacia arriba .
• Menos consumo de tiempo que dividir y conquistar ya que utilizamos los valores calculados anteriormente, en lugar de volver a calcular.
• p.ej. El enésimo término de la serie de Fibonacci se puede calcular en O (n) complejidad de tiempo.
  
  

Para una comprensión más fácil, veamos dividir y conquistar como una solución de fuerza bruta y su optimización como programación dinámica.

Nota: los algoritmos de división y conquista con subproblemas superpuestos solo se pueden optimizar con dp.

• Divide y conquistaras
  • Se dividieron en subproblemas no superpuestos
  • Ejemplo: números factoriales, es decir, hecho (n) = n * hecho (n-1)

fact(5) = 5* fact(4) = 5 * (4 * fact(3))= 5 * 4 * (3 *fact(2))= 5 * 4 * 3 * 2 * (fact(1))

Como podemos ver arriba, ningún hecho (x) se repite, por lo que factorial no tiene problemas superpuestos.

• Programación dinámica
  • Se rompieron en subproblemas superpuestos
  • Ejemplo: números de Fibonacci, es decir, fib (n) = fib (n-1) + fib (n-2)

fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1))

Como podemos ver arriba, fib (4) y fib (3) usan fib (2). de manera similar, se repite mucha fib (x). Es por eso que Fibonacci tiene subproblemas superpuestos.

• Como resultado de la repetición del subproblema en DP, podemos guardar dichos resultados en una tabla y ahorrar esfuerzo de cálculo. esto se llama memoria