f# - F# 中的动态编程

Question

实现解决problems with overlapping subproblems的动态规划算法的最优雅的方法是什么？ ?在命令式编程中，通常会创建一个按问题大小索引的数组(至少在一维中)，然后算法将从最简单的问题开始，并使用已经计算的结果处理更复杂的问题。

我能想到的最简单的例子是计算第 N 个斐波那契数:

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

一种对动态编程非常有用的技术称为记忆化。有关详细信息，请参阅示例 blog post by Don Syme或 introduction by Matthew Podwysocki .

这个想法是您编写(一个幼稚的)递归函数，然后添加存储先前结果的缓存。这使您可以以通常的函数样式编写函数，但获得使用动态编程实现的算法的性能。

例如，用于计算斐波那契数的简单(低效)函数如下所示:

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)))

请注意，这是一个递归值 - 函数体调用 memoized fibs功能。