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中的动态编程＃

回答

相关问题