底部动态规划可以在Lisp中实现吗？

Question

底部动态规划可以在Lisp中实现吗？

algorithmclojurelispdynamic-programmingknapsack-problem

11

一个典型的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方言中是否可能做到这样的事情？如果不行，为什么？

- Cedric Martin

我不确定我理解这个问题；Lisp中算法的规范实现几乎总是递归和“自底向上”的。 - Dave Newton

3

@Dave Newton：我可能表达得不是很清楚……我所指的是动态规划中维基百科文章中的“自底向上”和“自顶向下”概念。其中，“记忆化”（保存幂等方法/函数调用的结果以供稍后重复使用）是“自顶向下”的，而从底部开始逐步推导则是“自底向上”的。这两种方法都可以将某些问题简化为伪多项式时间。但在这种情况下，我不关心记忆化：我想知道是否可以从“自底向上”构建数组（计算单元格1，然后使用单元格1来计算单元格2，依此类推）。 - Cedric Martin

3

你觉得你不能用Lisp做到这一点的原因是什么？ - Rainer Joswig

1

@CedricMartin：Common Lisp是一种多范式语言，充分利用其功能并没有任何问题。几乎所有真实世界的Common Lisp代码都使用可变对象、数组甚至全局变量。据我所知，如果可能的话，Scheme程序员会尽最大努力避免使用命令式代码。 - han

@Cedric：我知道有其他可能的标准来决定一种语言是否可以被认为是函数式的（例如，支持TCO或闭包），但我认为我在这里提出的标准（“纯度/杂质编码在函数类型中”）很有用，因为它直接解决了所有倡导FP而非命令式编程的人们的主要关注点——即强制所有访问或更改状态的代码都是故意的和可见的。（顺便说一句，如果闭包/一级函数是您首选的标准，那么Perl就是一种函数式语言：）） - j_random_hacker

显示剩余6条评论

4个回答

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)))

我认为符合惯用的Clojure代码的基本概念是将问题分解成简单（只做一件事）的抽象，然后组合它们来解决主要问题。当然，这必须始终根据手头的问题进行调整。

- Arthur Ulfeldt

这段代码不是很符合Clojure的惯用写法，因为它将循环和要执行的工作结合在了一起。你能详细说明一下吗？ - edoloughlin

谢谢，我正在尝试使用Clojure，但从未正式学习过FP。我一直听说命令式循环不好，但没有进一步的解释。我尽可能使用内置迭代器，但有时会失败，例如当迭代涉及多个集合时。 - edoloughlin

一个小问题：在你上面的最后一行中 [(take-while...], current-row 的值从哪里来的？ - edoloughlin

你没有透露我的小秘密！我发布了这个内容却没有测试！真丢人。 - Arthur Ulfeldt

4

请原谅我这么说，但你所参考的维基百科页面（在我看来）写得不是很好。特别是，它几乎捏造了自顶向下和自底向上动态规划之间的二分法，并将其中一种描述为“更有趣”。两者之间唯一的区别就是构建表格的顺序。备忘录法会导致这两者出现，具体取决于调用的顺序。

提前向编写此页面的人道歉；我感谢你们的努力，只是认为这部分需要改进。

- John Clements

但是，“记忆化”特指在后续调用中重复使用幂等方法调用的结果，以避免需要多次计算它们。从头开始构建数组，从单元格1/行1到单元格2/行1到单元格3/行1等，然后从单元格1/行2（重用行1中的单元格）到单元格2/行2等，不是记忆化。因为这里没有保存/重用幂等方法调用。 larsmans 的好答案似乎正是我想要的，并且似乎与“我的”（和维基百科的）“记忆化”的定义相符。 - Cedric Martin

2

在这篇 WP （维基百科）文章中，我找不到词语 "interesting"。我只是快速浏览了一下，并发现它对 自顶向下 和 自底向上 这两个术语的使用似乎与解析中的使用方式相匹配，至少在自然语言处理（NLP）中是如此（在解析策略的选择可能非常重要的情况下）。 - Fred Foo

1

@larsmans - 因为我在过去几天里阅读了那篇文章来刷新自己的知识，他们在这里使用了它：“自底向上的方法：这是更有趣的情况。”- 来自这个部分：http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_computer_programming - wkl

啊，不好意思，我手头拿的是“记忆化搜索”这篇文章，而不是“动态规划”。 - Fred Foo

1

@John Clements：成为尖锐的人没有问题；）在这里https://dev59.com/sG025IYBdhLWcg3wKCb-，用户aaoibe（我写这篇文章时有65K rep）解释了“自上而下”和“自下而上”的区别。据我所知，有具体的问题，其中自下而上的方法比自上而下的方法更好（更有效/节省空间）。我不会说它们是相同的。也许在“概念上”或“数学上”它们是相同的，但考虑到我们正在使用的设备的物理限制，我倾向于认为它们实际上并不是同一回事。 - Cedric Martin

显示剩余3条评论

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

- Justin Kramer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Fred Foo · Accepted Answer

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