11

Can a typical Lisp dialect solve problems using the bottom-up "dynamic programming" approach?

(Please note: I'm not talking about "memoization" which, as far as I understand, is trivial using any Lisp dialect. I'm really talking about bottom-up Dynamic Programming, where you build, for an example, your array bottom up and then use the elements you just introduced to compute the next ones.)

For example, using dynamic programming, the "0-1 knapsack" problem can be solved in pseudo-polynomial time for inputs on which any other method would fail.

An imperative (incomplete) solution is:

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

Is such a thing possible to do in the various Lisp dialects? If no, why not?

4

4 回答 4

15

当然这是可能的。您唯一需要的是数组、整数和循环结构。例如，在 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 和类似语言进行编程时坚持记忆。如果使用哈希表，则预期的渐近时间和空间复杂度对于 memoization 和 DP 是相同的。

于 2011-10-19T16:50:43.590 回答
5

简短的回答是肯定的，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 代码的基本概念是将问题分解为简单的（只做一件事）抽象，然后将它们组合起来以解决主要问题。当然，这必须始终量身定制以适应手头的问题。

于 2011-10-19T18:09:01.950 回答
4

请原谅我这么说，但是您所指的维基百科页面（imnsho）写得不是很好。特别是，它或多或少地制造了自顶向下和自底向上动态编程之间的二分法，并继续将其中一种描述为“更有趣”。两者之间的唯一区别是构建表的顺序。记忆会产生这两种情况，具体取决于调用的顺序。

提前向写这部分页面的人道歉；感谢您的努力，我只是认为该部分需要一些工作。

于 2011-10-19T17:01:25.753 回答
2

这是 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
于 2011-10-19T20:26:01.703 回答