F中的動態編程＃

實現動態編程算法的最優雅的方法是什麼？解決problems with overlapping subproblems？在命令式編程中，通常會根據問題的大小創建索引（至少在一維中）的數組，然後算法將從最簡單的問題開始，並使用已經計算的結果進行一次更復雜的工作。F中的動態編程＃

我能想到的是計算的第N個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]; 
}

我知道你可以實現在F＃同樣的事情，但我要尋找一個很好的功能性解決方案（這是O（ N）以及顯然）。

來源

2011-11-02 Grzenio

一種對動態編程非常有用的技術叫做記憶。有關更多詳細信息，請參閱例如blog post by Don Syme或introduction by Matthew Podwysocki。

這個想法是，你寫（一個天真的）遞歸函數，然後添加緩存，存儲以前的結果。這使您可以使用通常的函數式編寫函數，但可以使用動態編程實現算法的性能。

例如，對於計算Fibonacci數天真的（低效率）的功能如下：

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

這是低效的，因爲當你調用fibs 3，它會調用fibs 1三次（和許多倍，如果你打電話，例如，fibs 6）。 memoization背後的想法是我們編寫一個緩存，其中存儲fib 1和fib 2的結果等，因此重複調用將從緩存中選擇預先計算的值。

一個通用的函數，它的記憶化可以這樣寫：

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)

編寫更有效的斐波那契的功能，我們就可以調用memoize，並給它執行計算作爲參數的函數：

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

請注意，這是一個遞歸值 - 該函數的主體調用memnalized fibs函數。

來源

2011-11-02 18:53:08

這往往是一個更容易閱讀memoized（遞歸）動態程序設計問題與程序化程序設計問題相比，但是可能更容易推斷程序版本的運行時間。 – gradbot

托馬斯的答案是一個很好的通用方法。在更具體的情況下，可能有其他技術可以很好地工作 - 例如，在斐波那契情況下，您實際上只需要有限的狀態（前兩個數字），而不是以前計算的所有值。因此，你可以做這樣的事情：

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

你也可以這樣做更直接（不使用Seq.unfold）：

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

來源

2011-11-02 19:17:29 kvb

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

來源

2011-11-02 21:48:09 BLUEPIXY

F中的動態編程＃

回答

相關問題