F#中的动态编程

Question

实现动态编程算法以解决重叠子问题的问题最优雅的方法是什么？在命令性编程一个通常会产生由该问题的大小索引(至少在一个维度上)的阵列,然后算法将从最简单的问题开始并朝着更复杂一次工作,使用已经计算出的结果.

我能想到的最简单的例子是计算Nth 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)).

Answer 1

一种对动态编程非常有用的技术称为memoization.有关更多详细信息,请参阅Don Syme的博客文章或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).背后记忆化的想法是,我们写存储结果的缓存fib 1和fib 2,等等,如此反复调用将只挑选从缓存中预先计算的值.

执行memoization的通用函数可以这样写:

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)

为了编写更高效的Fibonacci函数,我们现在可以调用memoize并赋予它作为参数执行计算的函数:

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

请注意,这是一个递归值 - 函数体调用memoized fibs函数.

Answer 2

托马斯的答案是一个很好的一般方法.在更具体的情况下,可能还有其他技术可以正常工作 - 例如,在您的斐波纳契案例中,您实际上只需要有限数量的状态(前2个数字),而不是所有先前计算的值.因此你可以这样做:

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

Answer 3

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