algorithm - Diferencia entre Dividir y Conquistar Algo y Programación Dinámica

dynamic-programming divide-and-conquer

Question

¿Cuál es la diferencia entre Divide and Conquer Algorithms y Dynamic Programming Algorithms ? ¿Cómo son los dos términos diferentes? No entiendo la diferencia entre ellos.

Por favor, tome un ejemplo simple para explicar cualquier diferencia entre los dos y sobre qué base parecen ser similares.

Answer 1

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

Divide y conquistaras:

1. Funciona más en los sub-problemas y, por lo tanto, tiene un mayor consumo de tiempo.
2. En divide y vencerás, los sub-problemas son independientes el uno del otro.

Programación dinámica:

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

Answer 2

Pienso en Divide & Conquer como un enfoque recursivo y Dynamic Programming como relleno de tablas.

Por ejemplo, Merge Sort es un algoritmo Divide & Conquer , ya que en cada paso, divide la matriz en dos mitades, recursivamente llama a Merge Sort sobre las dos mitades y luego las fusiona.

Knapsack es un algoritmo de Dynamic Programming , ya que está llenando una tabla que representa las soluciones óptimas para los 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.

Answer 3

Supongo que ya ha 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é mi granito de arena sobre 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 para fib (n) resolviendo primero para fib (n-1). Para resolver el problema original, resuelve un problema diferente .

Divide y conquistaras

Estos algoritmos normalmente resuelven piezas similares del problema y luego las reúnen 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 ser (teóricamente) arbitraria, y no importa cómo la segmente, todavía se está fusionando y clasificando. Se debe hacer la misma cantidad de trabajo para fusionar la matriz, sin importar cómo la divida. La resolución de fib (52) requiere más pasos que resolver para fib (2).

Answer 4

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

El famoso ejemplo de 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)
}

Corramos 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

Así que 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 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 necesite la llamada múltiple, simplemente acceda 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 subresultados 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 de D & D se basan en la recursión. Y algunas versiones de ellos tienen esta "llamada de función múltiple con el mismo problema de parámetro". Busque "multiplicación de cadenas de matrices" y "subsecuencias comunes más largas" para ejemplos tales donde se necesita DP para mejorar el T (n) de algo de D & D.

Answer 5

Divide y conquistaras

Dividir y vencer funciona dividiendo el problema en subproblemas, conquista cada sub-problema recursivamente y combina estas soluciones.

Programación dinámica

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

Puede pensar en DP = recursion + re-use

Un ejemplo clásico para entender la diferencia sería ver ambos enfoques para obtener el n ° número de fibonacci. Verifique este material de MIT.

EDITAR

Enfoque Divide y Vence

Enfoque de programación dinámica