Programación dinámica en F #

Question

¿Cuál es la forma más elegante de implementar algoritmos de programación dinámica que resuelvan problems with overlapping subproblems? En la programación imperativa uno normalmente crea una matriz indexada (al menos en una dimensión) por el tamaño del problema, y ​​luego el algoritmo comienza desde los problemas más simples y trabaja hacia una más complicada una vez, usando los resultados ya calculados.

El ejemplo más simple que puedo pensar es el calcular el número enésimo de Fibonacci:

int Fibonacci(int N) 
{ 
    var F = new int[N+1]; 
    F[0]=1; 
    F[1]=1; 
    for(int i=2; i<=N; i++) 
    { 
     F[i]=F[i-1]+F[i-2]; 
    } 
    return F[N]; 
} 

Sé que usted puede aplicar lo mismo en C#, pero estoy en busca de una solución funcional agradable (que es O (N) también obviamente).

Answer 1

Una técnica que es bastante útil para la programación dinámica se llama memoria. Para obtener más información, consulte, por ejemplo, blog post by Don Syme o introduction by Matthew Podwysocki.

La idea es que escriba (ingenua) la función recursiva y luego agregue el caché que almacena los resultados anteriores. Esto le permite escribir la función en un estilo funcional habitual, pero obtener el rendimiento del algoritmo implementado mediante programación dinámica.

Por ejemplo, una función ingenua (ineficaz) para el cálculo del número de Fibonacci es así:

let rec fibs n = 
    if n < 1 then 1 else 
    (fibs (n - 1)) + (fibs (n - 2)) 

Esto es ineficiente, porque cuando se llama a fibs 3, se llamará fibs 1 tres veces (y muchas veces más si llame, por ejemplo, fibs 6). La idea detrás de la memorización es que escribimos un caché que almacena el resultado de fib 1 y fib 2, y así sucesivamente, por lo que las llamadas repetidas simplemente seleccionarán el valor precalculado de la caché.

una función genérica que hace el memoization se puede escribir así:

open System.Collections.Generic 

let memoize(f) =  
    // Create (mutable) cache that is used for storing results of 
    // for function arguments that were already calculated. 
    let cache = new Dictionary<_, _>() 
    (fun x -> 
     // The returned function first performs a cache lookup 
     let succ, v = cache.TryGetValue(x) 
     if succ then v else 
     // If value was not found, calculate & cache it 
     let v = f(x) 
     cache.Add(x, v) 
     v) 

Para escribir la función de Fibonacci más eficiente, ahora podemos llamar memoize y darle la función que realiza el cálculo como un argumento:

let rec fibs = memoize (fun n -> 
    if n < 1 then 1 else 
    (fibs (n - 1)) + (fibs (n - 2))) 

Tenga en cuenta que este es un valor recursivo: el cuerpo de la función llama a la función fibs memorizada.

Answer 2

La respuesta de Tomás es un buen enfoque general. En circunstancias más específicas, puede haber otras técnicas que funcionen bien; por ejemplo, en su caso de Fibonacci, realmente solo necesita una cantidad de estado finita (los 2 números anteriores), no todos los valores previamente calculados. Por lo tanto se puede hacer algo como esto:

let fibs = Seq.unfold (fun (i,j) -> Some(i,(j,i+j))) (1,1) 
let fib n = Seq.nth n fibs 

También podría hacer esto de manera más directa (sin usar Seq.unfold):

let fib = 
    let rec loop i j = function 
    | 0 -> i 
    | n -> loop j (i+j) (n-1) 
    loop 1 1 

Answer 3

let fibs = 
    (1I,1I) 
    |> Seq.unfold (fun (n0, n1) -> Some (n0 , (n1, n0 + n1))) 
    |> Seq.cache