F＃中的动态编程 [英] Dynamic programming in F#

问题描述

实现动态编程算法的最优雅的方式是什么，可以解决重叠子问题的问题？在命令式编程中，通常会根据问题的大小创建一个索引（至少在一维中）的数组，然后该算法将从最简单的问题开始，并使用已计算的结果进行更复杂的处理。 >

我能想到的最简单的例子是计算第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））。

解决方案

一种对动态编程非常有用的技术被称为 memoization 。有关更多详细信息，请参阅 Don Syme的博客文章或 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 的结果等等，所以重复的调用只会从缓存中选择预先计算的值。

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

 打开System.Collections.Generic 
 
 let memoize（f）= 
 //创建（可变）缓存用于存储已经计算的函数参数
 //的结果。 
 let cache = new Dictionary< _，_>（）
（fun x  - > 
 //返回的函数首先执行缓存查找
 let succ，v = cache .tryGetValue（x）
 if succ then v else 
 //如果没有找到值，计算并缓存它
 let v = f（x）
 cache.Add（ x，v）
v）
  

为了编写更高效的Fibonacci函数，我们现在可以调用 memoize 并给它一个执行计算的函数作为参数：

 如果n <1然后1其他
（fibs（n-1））+（fibs（n-2）））
，则记录fibs = memoize（fun n  - > 
） / code> 

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


What is the most elegant way to implement dynamic programming algorithms that solve problems with overlapping subproblems? In imperative programming one would usually create an array indexed (at least in one dimension) by the size of the problem, and then the algorithm would start from the simplest problems and work towards more complicated once, using the results already computed.

The simplest example I can think of is computing the Nth Fibonacci number:

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

I know you can implement the same thing in F#, but I am looking for a nice functional solution (which is O(N) as well obviously).

解决方案

One technique that is quite useful for dynamic programming is called memoization. For more details, see for example blog post by Don Syme or introduction by Matthew Podwysocki.

The idea is that you write (a naive) recursive function and then add cache that stores previous results. This lets you write the function in a usual functional style, but get the performance of algorithm implemented using dynamic programming.

For example, a naive (inefficient) function for calculating Fibonacci number looks like this:

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

This is inefficient, because when you call fibs 3, it will call fibs 1 three times (and many more times if you call, for example, fibs 6). The idea behind memoization is that we write a cache that stores the result of fib 1 and fib 2, and so on, so repeated calls will just pick the pre-calculated value from the cache.

A generic function that does the memoization can be written like this:

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)

To write more efficient Fibonacci function, we can now call memoize and give it the function that performs the calculation as an argument:

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

Note that this is a recursive value - the body of the function calls the memoized fibs function.

这篇关于F＃中的动态编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！