algorithm - sencillos - recursividad en programacion pdf

¿Cuál es la diferencia entre recursividad, memorización y programación dinámica?

Question

Posible duplicado:
Programación dinámica y memorización: enfoques descendentes vs. ascendentes

He revisado muchos artículos sobre esto, pero parece que no tiene sentido. A veces, la recursividad y la programación dinámica se ven igual y, en otros, la memorización y la programación dinámica se parecen. ¿Alguien me puede explicar cuál es la diferencia?

PD: También será útil si me puede indicar algún código usando los tres enfoques sobre el mismo problema. (por ejemplo, el problema de la serie de Fibonacci, creo que cada artículo que leí usó la recursión pero se refirió a ella como programación dinámica)

Answer 1

Bueno, la recursividad + memorización es precisamente un "sabor" específico de la programación dinámica: programación dinámica de acuerdo con el enfoque descendente .

Más precisamente, no hay requisito para usar la recursividad específicamente. Cualquier solución de divide y vencer combinada con la memorización es la programación dinámica de arriba hacia abajo. (La recursión es el sabor LIFO de divide y vencerás, mientras que también puedes usar FIFO dividir y conquistar o cualquier otro tipo de división y conquista).

Entonces es más correcto decir que

divide & conquer + memoization == top-down dynamic programming

Además, desde un punto de vista muy formal, si implementa una solución de divide y vencerás para un problema que no genera soluciones parciales repetitivas (lo que significa que no hay beneficio en la memorización), entonces puede afirmar que esta solución de divide y vencer es ejemplo degenerado de "programación dinámica".

Sin embargo, la programación dinámica es un concepto más general. La programación dinámica puede usar un enfoque ascendente, que es diferente de dividir y conquistar + memorización.

Answer 2

Considere calcular la secuencia de fibonacci:

Recursión pura:

int fib(int x)
{
    if (x < 2)
        return 1;

    return fib(x-1) + fib(x-2);
}

da como resultado un número exponencial de llamadas.

Recursión con memoria / DP:

void fib(int x)
{
    static vector<int> cache(N, -1);

    int& result = cache[x];

    if (result == -1)
    {
        if (x < 2)
            result = 1;
        else
            result = fib(x-1) + fib(x-2);
    }

    return result;
}

Ahora tenemos un número lineal de llamadas la primera vez, y constante a partir de entonces.

El método anterior se llama "perezoso". Calculamos los términos anteriores la primera vez que se solicitan.

Lo siguiente también se considerará DP, pero sin recurrencia:

int fibresult[N];

void setup_fib()
{
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < N; i++)
       fibresult[i] = fibresult[i-1] + fibresult[i-2];
}

int fib(int x) { return fibresult[x]; }

De esta manera se puede describir como "ansioso", "precaching" o "iterativo". Es más rápido en general, pero tenemos que calcular manualmente el orden en el que se deben calcular los subproblemas. Esto es fácil para Fibonacci, pero para problemas de DP más complejos se hace más difícil, por lo que recurrimos al método recursivo lazy si es rápido. suficiente.

Además, lo siguiente no es recursividad ni DP:

int fib(int x)
{
    int a = 1;
    int b = 1;
    for (int i = 2; i < x; i++)
    {
        a = a + b;
        swap(a,b);
    }
    return b;
}

Utiliza espacio constante y tiempo lineal.

También mencionaré, en aras de la exhaustividad, que existe una forma cerrada para fibonacci que usa recurrencia inferior o DP que nos permite calcular en tiempo constante el término fibonacci usando una fórmula matemática basada en la proporción áurea:

http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/

Answer 3

Estoy seguro de que puedes encontrar una definición detallada a través de internet. Aquí está mi intento de simplificar las cosas.

La recursión se está llamando de nuevo.

La Programación Dinámica es una forma de resolver problemas que exhiben una estructura específica (subestructura óptima) donde un problema puede dividirse en sub problemas que son similares al problema original. Claramente, uno puede invocar la recursión para resolver un DP. Pero no es necesario. Uno puede resolver un DP sin recursión.

La memorización es una forma de optimizar los algoritmos DP que se basan en la recursión. El punto es no resolver nuevamente el problema secundario que ya ha sido resuelto. Puede verlo como un caché de soluciones para problemas secundarios.

Answer 4

La recursividad no tiene absolutamente nada que ver con la memorización y la programación dinámica; es un concepto completamente separado.

De lo contrario, esta es una pregunta duplicada de: Programación dinámica y memorización: enfoques ascendentes vs. descendentes

Answer 5

Son conceptos diferentes. Se superponen bastante a menudo, pero son diferentes.

La recursión ocurre cuando una función se llama a sí misma, directa o indirectamente. Esto es todo.

Ejemplo:

a -> call a
a -> call b, b -> call c, c -> call a

La programación dinámica es cuando utiliza soluciones a subproblemas más pequeños para resolver un problema mayor. Esto es más fácil de implementar de manera recursiva porque generalmente piensas en tales soluciones en términos de una función recursiva. Sin embargo, generalmente se prefiere una implementación iterativa porque requiere menos tiempo y memoria.

La memorización se usa para evitar que la implementación recursiva de DP tome mucho más tiempo de lo necesario. La mayoría de las veces, un algoritmo DP usará el mismo subproblema para resolver problemas múltiples grandes. En una implementación recursiva, esto significa que volveremos a calcular lo mismo varias veces. La memorización implica guardar los resultados de estos subproblemas en una tabla. Al ingresar una llamada recursiva, verificamos si su resultado existe en la tabla: en caso afirmativo, la devolvemos; de lo contrario, la calculamos, la guardamos en la tabla y luego la devolvemos.