Programowanie dynamiczne w języku F #

Question

Jaki jest najbardziej elegancki sposób implementacji algorytmów programowania dynamicznego, które rozwiązują problems with overlapping subproblems? W programowaniu imperatywnym zwykle tworzy się tablicę indeksowaną (przynajmniej w jednym wymiarze) przez rozmiar problemu, a następnie algorytm zaczynałby od najprostszych problemów i pracował na rzecz bardziej skomplikowanego razu, korzystając z już wyliczonych wyników.

Najprostszym przykładem mogę myśleć jest obliczanie liczby Pn Fibonacciego:

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]; 
} 

wiem można zaimplementować samo w F #, ale szukam ładnej rozwiązania funkcjonalnego (co jest O (N) oczywiście również).

Answer 1

Jedna technika, która jest całkiem przydatna w programowaniu dynamicznym, nazywa się z pamięcią nr. Aby uzyskać więcej informacji, zobacz na przykład blog post by Don Syme lub introduction by Matthew Podwysocki.

Chodzi o to, że piszesz (naiwną) funkcję rekursywną, a następnie dodajesz pamięć podręczną przechowującą poprzednie wyniki. Dzięki temu można napisać funkcję w zwykłym stylu funkcjonalnym, ale uzyskać wydajność algorytmu zaimplementowanego za pomocą programowania dynamicznego.

Na przykład, naiwny (nieskuteczny) funkcja obliczania liczby Fibonacciego wygląda następująco:

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

To jest nieefektywne, ponieważ podczas rozmowy fibs 3, to zadzwoń fibs 1 trzy razy (i wiele więcej razy, jeśli zadzwonisz, na przykład, fibs 6). Pomysł zapamiętywania polega na tym, że zapisujemy pamięć podręczną, która przechowuje wynik fib 1 i fib 2 itd., Więc powtarzające się połączenia będą po prostu wybierać wstępnie obliczoną wartość z pamięci podręcznej.

rodzajowy funkcja, która robi memoization można zapisać tak:

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) 

Aby napisać bardziej wydajną funkcję Fibonacciego, możemy teraz nazwać memoize i nadać mu funkcję, która wykonuje obliczenia jako argument:

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

Należy zauważyć, że jest to wartość rekursywna - treść funkcji wywołuje funkcję pamiętaną fibs.

Answer 2

Odpowiedź Tomasa jest dobrym ogólnym podejściem. W bardziej konkretnych okolicznościach mogą istnieć inne techniki, które działają dobrze - na przykład w przypadku Fibonacciego naprawdę potrzebujesz tylko skończonej ilości stanów (poprzednie 2 cyfry), a nie wszystkich wcześniej obliczonych wartości. W związku z tym można zrobić coś takiego:

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

Można również zrobić to bardziej bezpośrednio (bez użycia 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