可以在Lisp中完成自底向上的动态规划吗?

Question

典型的Lisp方言可以使用自下而上的"动态规划"方法解决问题吗?

(请注意:我不是在谈论"记忆"，据我所知，使用任何Lisp方言都是微不足道的。我说的是自底向上的动态规划，比如，你先自底向上构建数组，然后使用刚刚介绍的元素来计算下一个元素。

例如，使用动态规划，"0-1背包"问题可以在伪多项式时间内解决，而其他任何方法都无法解决。

一个命令式的(不完整的)解决方案是:

for (int k = 1; k <= a.length; k++) {
    for (int y = 1; y <= b; y++) { 
        if (y < a[k-1]) {
            knap[k][y-1] = knap[k-1][y-1];
        } else {
            if (y > a[k-1]) {
                knap[k][y-1] = Math.max(knap[k-1][y-1], knap[k-1][y-1-a[k-1]] + c[k-1]);
            } else {
                knap[k][y-1] = Math.max(knap[k-1][y-1], c[k-1]);
    }
}

这样的事情在各种Lisp方言中可能做到吗?如果没有，为什么?

Answer 1

当然这是可能的。您只需要数组、整数和循环结构。例如，在Scheme中，您的算法可以使用向量进行转录。主要的问题是它变得难以阅读，因为knap[k-1][y-1]变成了(vector-ref (vector-ref knap (- k 1)) (- y 1))和

knap[k][y-1] = knap[k-1][y-1];

是

(vector-set! (vector-ref knap k) (- y 1)
             (vector-ref (vector-ref knap (- k 1)) (- y 1)))

(或者是模的一个可怕的技巧)，而记忆递归仍然是可读的。

根据我的经验，我建议你在用Lisp和类似的语言编程时坚持使用记忆法。如果您使用哈希表，对于记忆和DP，期望的渐近时间和空间复杂度是相同的。

Answer 2

简短的回答是肯定的，Clojure可以直接与java数组一起工作，所以直接转换非常直接

 (for [k (range 1 (count a)) 
       y (range 1 b)]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                                 (aget c (dec k))))))))))

这不是非常典型的Clojure，因为它将循环与要完成的工作结合在一起。如果将循环的元素分开，生成的代码将更清晰，更容易显示正确。

作为简单的第一步，如果我们将循环从"工作"中分离出来，那么我们得到。

(defn edit-array [k y]
   (if (< y (aget a (dec k)))
     (aset knap k (dec y) (aget knap (dec k) (dec y))
           (if (> y (aget a (dec k)))
             (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                       (aget knap (dec k) (+ (- y 1 (aget a (dec k)))
                                                             (aget c (dec k))))
                                       (aset knap k (dec y) (max (aget knap (dec k) (dec y))
                                                             (aget c (dec k))))))))))
(for [k (range 1 (count a)) y (range 1 b)]
   (edit-array k y))

然后我们可以从repl中测试编辑数组，并让我们自己相信它是有效的(也许还可以写一个单元测试)。在那之后，也许你想开始更密切地关注edit-array，并决定是否有可能将其分解成更容易独立测试的步骤。也许您可以将其更改为使用函数式样式，而不是更改数组。在这里，我将离开你的具体问题，因为我不得不承认，我不理解这个线性规划解决方案最初要解决的问题。

 (defn finished? [row] ... determine if we have reached the final state ...)
 (defn next-row [current-row]
    (for [y (range 1 (count current-row)]
      ... code to produce a new vector based on the previous one ...))
(take-while #(not (finished? %) (iterate next-row (initial-state)))

我所看到的Idomatic Clojure代码的基本概念是将问题分解为简单的(只做一件事)抽象，然后将它们组合起来解决主要问题。当然，这必须始终适合手头的问题。

Answer 3

请原谅我这么说，但你所指的维基百科页面(imnsho)写得不是很好。特别是，它或多或少地制造了自顶向下和自底向上动态规划之间的二分法，并继续将其中一种描述为"更有趣"。两者之间的唯一区别是表的构造顺序不同。根据调用的顺序，记忆会产生这两个。

提前向撰写这部分内容的人道歉;我很欣赏你的努力，我只是觉得这部分需要改进。

Answer 4

这是Clojure中一个很好的自底向上版本的斐波那契数列(我相信最初是由Christophe Grand编写的):

(defn fib []
  (map first (iterate
              (fn [[a b]] [b (+ a b)])
              [0 1])))

这将生成一个无限惰性序列，因此您可以根据需要请求任意多或任意少:

(take 10 (fib))
=> (0 1 1 2 3 5 8 13 21 34)
(nth (fib) 1000)
=> 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875