java - 将类 Java 2D 动态规划矩阵转换为 Haskell

Question

我目前正在使用java中的动态规划算法，该算法使用经典的2D矩阵进行反向计算。我正在尝试将其转换为像 Haskell 这样的函数式语言，但事实证明它超出了我的能力。寻找有关解决方案的任何建议:

int[][] dynamic = new int[size][size];
for (int outer = 0; outer < size; j++){
    Arrays.fill(dynamic[outer], 0);
}

dynamic[0][0] = 1; 

for (int a = 0; a < size; a++){ 
   for (int b = a; b < size; b++){ 
      if (a == 0){
        dynamic[a+1][b+1] = dynamic[a][b] * 2;

        dynamic[a][b+1] = dynamic[a][b] * -1;
      } else{
        dynamic[a+1][b+1] = dynamic[a+1][b+1] + (dynamic[a][b] * 3);
        dynamic[a][b+1] = dynamic[a][b+1] + (dynamic[a][b] * 2);
      }
    }
}

到目前为止，我一直在寻找创建二维数组的不同选项，但没有成功。我猜测是因为 Haskell 不使用可变状态，所以它不是一个 super 流行的选项。这可能只是我的java大脑，但我希望一些具有功能背景的人能够给我一些关于如何思考或解决这种转换的指导？

Answer 1

通常手动进行突变对于 Haskell 来说是一个错误。这很尴尬，而且它重新引入了 Haskell 中通常不会遇到的所有突变错误。通常你会让懒惰替你处理事情。动态编程问题的结构在 Haskell 中可以非常简单地用惰性来表达，但您需要从不太困惑的代码规范开始。

要做的第一件事就是反混淆成低效的递归表示。对于您的示例来说，这完全是一个痛苦 - 我希望您只是或多或少随机地输入代码。

这是我得到的，用 Haskell 表达的，尽管我不保证它是正确的:

present :: Int -> Int -> Int
present 0 0 = 1
present _ 0 = 0
present 0 b = negate (present 0 (b - 1))
present a b = future a b + 2 * present a (b - 1)

future :: Int -> Int -> Int
future 1 b = 2 * present 0 b
future a b = 3 * present (a - 1) (b - 1)

为了解决您的突变，我必须使用相互递归函数，其中 present 在概念上跟踪循环中当前行的状态，并 future 跟踪状态下一行的。请注意，第一行之后的行的 future 情况并不完全反射(reflect)您所写的内容。我擅自修剪了 dynamic[a+1][b+1] + 部分，因为 dynamic[a+1][b+1] 始终是按照您的逻辑布局方式，该值将为零。

通常，您会使用递归解决方案开始动态编程，因此您不需要像我在这里那样进行逆向工程。此外，您通常会遇到一些看起来不像完全随机的操作。不过，我有点喜欢多个函数之间存在相互递归。它使下一部分更酷。

让我们对 ghci 进行一些研究，只是为了大致了解它的性能。

*Main> :set +s
*Main> present 10 10
-39366
(0.00 secs, 801,616 bytes)
*Main> present 11 11
-118098
(0.00 secs, 1,530,632 bytes)
*Main> present 20 20
-2324522934
(1.07 secs, 746,657,288 bytes)
*Main> present 21 21
-6973568802
(2.22 secs, 1,493,244,064 bytes)
*Main> present 22 22
-20920706406
(4.14 secs, 2,986,417,752 bytes)

这开始看起来大致像预期的运行时指数增长。

这就是事情变得很酷的地方。 Haskell 中的值可以根据其自身进行定义。基本思想是建立与每个函数相对应的常规装箱数组，其中每个单元格的值通过一个函数表示，该函数用数组查找替换函数调用。只要定义中不存在任何循环，惰性就会让一切顺利进行。

代码如下:

import Data.Array
import Data.Ix

memoPresent :: Int -> Int -> Int
memoPresent r c = pArray ! (r, c)
  where
    bounds = ((0, 0), (r, c))

    pArray = listArray bounds (map (uncurry present) (range bounds))

    present 0 0 = 1
    present _ 0 = 0
    present 0 b = negate (pArray ! (0, b - 1))
    present a b = fArray ! (a, b) + 2 * pArray ! (a, b - 1)

    fArray = listArray bounds (map (uncurry future) (range bounds))

    future 1 b = 2 * pArray ! (0, b)
    future a b = 3 * pArray ! (a - 1, b - 1)

如果您密切注意，您可能会注意到 fArray 的整个第一行都没有定义。如果访问该行中的任何内容，您会收到错误，但如果您调用 future 0 another，这与递归代码最终遇到的情况相同。

让我们看看它的表现如何:

*Main> :set +s
*Main> memoPresent 10 10
-39366
(0.00 secs, 194,176 bytes)
*Main> memoPresent 11 11
-118098
(0.00 secs, 223,344 bytes)
*Main> memoPresent 20 20
-2324522934
(0.00 secs, 521,944 bytes)
*Main> memoPresent 21 21
-6973568802
(0.00 secs, 566,544 bytes)
*Main> memoPresent 22 22
-20920706406
(0.00 secs, 616,304 bytes)
*Main> memoPresent 100 100
1989748563691696842
(0.01 secs, 10,442,400 bytes)
*Main> memoPresent 200 200
7879235843265279210
(0.05 secs, 41,116,704 bytes)
*Main> memoPresent 1000 1000
-4135538464527847958
(1.26 secs, 1,064,652,488 bytes)

嗯。我没想到它会突然开始得到肯定的答案。哦，这可能只是 Int 下溢。 Integer 可能是更好的类型选择，尽管它也不能反射(reflect)您的 Java 代码。

无论如何 - 如果你利用惰性来发挥你的优势，那么在 Haskell 中从递归形式到动态编程的转换非常简单。您只需要确保按照低效递归而不是混淆但有效的循环突变来执行原始公式。