可以在Lisp中完成自下而上的动态编程吗？

Question

一个典型的Lisp方言可以使用自下而上的"动态编程"方法解决问题吗？

(请注意:我不是在谈论"memoization",据我所知,使用任何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和类似语言编程时坚持使用memoization.如果使用哈希表,则对于memoization和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代码的基本概念是将问题分解为简单(只做一件事)抽象,然后将它们组合起来解决主要问题.当然,必须始终根据手头的问题进行定制.