racket - 懒惰 Racket 中的动态编程

Question

我想记住如何在懒球拍中进行动态编程。解决了Euler项目的问题之一后，我开始感到奇怪：


从下面的三角形的顶部开始并移至相邻的三角形
在下面的行中，数字从上到下的最大值为23。

   3
  7 4
 2 4 6
8 5 9 3

即3 + 7 + 4 + 9 = 23。

在下面的三角形的顶部到底部找到最大总数：
...


我用下面的代码解决了。但是，我在学校里曾教过有关懒惰球拍（甚至是一般的编程语言）的知识，而且我似乎还记得，在懒惰的语言中，解决动态编程问题要容易得多。例如，在其他欧洲专家发布的解决方案中，有人发布了他用来解决问题的haskell代码，而实际上仅是一行代码，而不是实际指定问题中的数据所需要的代码（三角形中的内容）本身）。但是，我不理解代码，因此我仍然感到困惑。

摘要：


如何解决懒人球拍中的动态编程问题？例如，答案可以解决上面给出的4级三角形示例（而不是完整的15级三角形）问题，或者张贴一些以前制作的编辑距离代码（这就是我学习DP的方式）。
为什么用惰性语言（例如惰性球拍）进行动态编程会更容易？


下面给出了用于解决常规球拍中的DP问题的80行代码。

#lang racket
(define (triangle-ref x y)
  (let ((triangle
       (vector-immutable
         (vector-immutable 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)
         (vector-immutable 63 66 04 68 89 53 67 30 73 16 69 87 40 31)
         (vector-immutable 91 71 52 38 17 14 91 43 58 50 27 29 48)
         (vector-immutable 70 11 33 28 77 73 17 78 39 68 17 57)
         (vector-immutable 53 71 44 65 25 43 91 52 97 51 14)
         (vector-immutable 41 48 72 33 47 32 37 16 94 29)
         (vector-immutable 41 41 26 56 83 40 80 70 33)
         (vector-immutable 99 65 04 28 06 16 70 92)
         (vector-immutable 88 02 77 73 07 63 67)
         (vector-immutable 19 01 23 75 03 34)
         (vector-immutable 20 04 82 47 65)
         (vector-immutable 18 35 87 10)
         (vector-immutable 17 47 82)
         (vector-immutable 95 64)
         (vector-immutable 75))))
    (vector-ref (vector-ref triangle y) x)))
(define triangle-size 15)
(define (problem18)
  (let ((table (let fill-table ((table (hash))
                                (current-x 0)
                                (current-y 0))
                 (cond ((>= current-y triangle-size) table)
                       ((>= current-x (- triangle-size current-y))
                        (fill-table table 0 (add1 current-y)))
                       (else (let ((reference (cons current-x current-y))
                                   (triangle-value (triangle-ref current-x
                                                                 current-y)))
                               (if (= current-y 0)
                                 (fill-table (hash-set table
                                                       reference
                                                       (cons triangle-value
                                                             empty))
                                             (add1 current-x)
                                             current-y)
                                 (let* ((left-entry (hash-ref
                                                      table
                                                      (cons
                                                        current-x
                                                        (sub1 current-y))))
                                        (left-cost (car left-entry))
                                        (left-path (cdr left-entry))
                                        (right-entry (hash-ref
                                                       table
                                                       (cons
                                                         (add1
                                                           current-x)
                                                         (sub1
                                                           current-y))))
                                        (right-cost (car right-entry))
                                        (right-path (cdr right-entry)))
                                   (if (> left-cost right-cost)
                                     (fill-table (hash-set table
                                                           reference
                                                           (cons
                                                             (+ triangle-value
                                                                left-cost)
                                                             (cons
                                                               triangle-value
                                                               left-path)))
                                                 (add1 current-x)
                                                 current-y)
                                     (fill-table (hash-set table
                                                           reference
                                                           (cons
                                                             (+ triangle-value
                                                                right-cost)
                                                             (cons
                                                               triangle-value
                                                               right-path)))
                                                 (add1 current-x)
                                                 current-y))))))))))
    (car (hash-ref table (cons 0 (sub1 triangle-size))))))
(problem18)
(provide problem18)

Answer 1

对于某些类型的问题，懒惰可以让您以一种很好的模块化方式来组织解决方案，在这种情况下，您可以首先编写代码，就像生成所有可能的解决方案一样（即使有无限可能），然后分别编写代码以测试是否解决方案是有效的解决方案。在一种懒惰的语言中，这样的算法将仅检查可能的解决方案来计算最终结果，而其他所有可能性自然不会被计算出来，因此它与回溯等更复杂的策略一样有效。

一个典型的例子是解决数独难题的算法（谷歌搜索会出现很多例子）。您可能也对John Hughes的论文《为什么函数编程很重要》感兴趣。

话虽如此，在这种特定情况下，懒惰不会有多大帮助。急切或懒惰的语言中的动态编程风格的解决方案都可以很好地工作（外观大致相同）。

解决此类问题时，先计算一个幼稚的解决方案然后加以改进通常会很有帮助。天真的解决方案将计算每个可能的总数，然后取最大值。对于小三角形示例，您将计算3 + 7 + 2 + 8、3 + 7 + 2 + 5等，但是只要写下来就可以显示出可能的改进，因为重复了3 + 7 + 2。避免这些重复的计算正是动态编程所要做的。动态算法将只计算一次这些中间结果，然后将其重复使用多次。

为此，我们通过逐步计算最大总数，一次计算一行。以这种方式计算最大总数的函数可能如下所示：

（注意：您需要安装最新的每晚版本才能运行此Racket代码。）

;; A Row is a list of at least one number.

;; A Triangle is a list of at least one Row,
;;  where each row has one more number than the previous row.

;; ----------------------------------------------------------------------------
;; top-down solution

;; max-tri-route : Triangle -> Number
;; Computes the maximum total when moving from top of triangle to bottom.
(define/match (max-tri-route tri)
  [((list a-single-row)) 
   (apply max a-single-row)]
  [((list-rest row1 row2 rest-rows))
   (max-tri-route (cons (process-row row1 row2) rest-rows))])

我假设三角形用列表列表表示，其中每个子列表表示一行。我们假设三角形的第一行代表我们递增计算的总数。该函数表示，如果只有一行，则取该行的最大值。否则，请在第一行（到目前为止的总数）和第二行中调用流程行函数。 process-row函数将第二行合并到中间总计中，可能看起来像这样：

;; process-row : Row Row -> Row
;; Takes a list of intermediate maximum values and a row, and incorporates
;;  the given row into the intermediate values.
;; - new-row always has one more element than tmp-maxes
;; - produces list of length new-row
(define/match (process-row tmp-maxes new-row)
  [((list x) (list y z)) 
   (list (+ x y) (+ x z))]
  [((list-rest x rest-maxes) (list-rest y z rest-row)) 
   (define res (process-row rest-maxes (cons z rest-row)))
   (cons (+ x y) (cons (max (+ x z) (first res)) (rest res)))])

此函数假定第二给定行的编号始终比第一给定行的编号多。如果给定的两行分别只有一个和两个数字，则只需将第一行中的数字添加到第二行中的每个数字。否则，我们一次要考虑三个数字来计算新的中间总数：一个来自第一个给定行，两个相邻的数字来自第二个给定行。当然，给定第二行中的每个数字（末尾除外）在第一行中都有两个相邻的数字，因此我们只想取大一个。例如，在小三角形示例中，在前两行调用process-row会产生中间值10和7。然后，如果用10 7调用process-row，而下一行2 4 6则调用了process-row，则首先考虑2的10和4，得出12和14。但还必须考虑下面的4与7。由于7 + 4 = 11小于14，因此我们保留的中间总数为14。合并第三行后得到的中间总数为12 14 13。

上面的解决方案即使对于问题67中的三角形也可以有效地产生正确的答案。但是，这感觉有点尴尬，尤其是在过程行的第二部分，我们必须考虑重叠的情况。让我们看看是否可以使解决方案更好。

参加＃2：

在第一个解决方案中，由于我们自上而下处理三角形，因此中间总计的列表随每一行而增长。但是最后，我们必须计算所有中间值的最大值。但是没有什么说我们必须从上到下处理三角形。由于我们只对总数感兴趣，因此自下而上将得到相同的答案。让我们看看它是什么样的：

;; ----------------------------------------------------------------------------
;; bottom-up solution

(define (max-tri-route2 tri) (max-tri/bottom-up (reverse tri)))

;; Computes total starting from bottom row.
(define/match (max-tri/bottom-up tri)
  [((list (list the-max-total))) 
   the-max-total]
  [((list-rest row1 row2 rest-rows))
   (max-tri/bottom-up (cons (process-row/bottom-up row2 row1) rest-rows))])

;; - tmp-maxes always has one more element than new-row
;; - produces list of length new-row
(define/match (process-row/bottom-up new-row tmp-maxes)
  [((list x) (list y z))
   (list (+ x (max y z)))]
  [((list-rest x rest-row) (list-rest y z rest-maxes))
   (cons (+ x (max y z)) (process-row/bottom-up rest-row (cons z rest-maxes)))])

使用自下而上的方法时，最后我们只有一个值，即最终答案。而且，进程行/自下而上比进程行更简单，因为我们现在可以直接直接保留两个数字中的较大者。

但是，我们可以做得更好。

参加＃3：

这种遍历列表和累积中间值的模式非常普遍，以至于内置函数可以执行此操作：foldr和foldl。这些函数中的每一个都使用一个要遍历的列表，一个初始中间值以及一个将列表中的下一个值与当前中间值组合在一起的函数。但是我们需要什么合并功能？事实证明，这正是我们的进程行功能。这是foldl的解决方案：

;; ----------------------------------------------------------------------------
;; bottom-up, with foldl

(define (max-tri-route3 tri)
  (define rev-tri (reverse tri))
  (first (foldl process-row/bottom-up (first rev-tri) (rest rev-tri))))

foldl从列表的左侧开始，但是由于我们要自下而上，因此我们首先反转列表。我们将第一行（即底部）用作初始中间值，并将其余行用作三角形。完成后，我们将获得一个值列表，即答案。

采取＃4：

最后的完善。我们为什么要反转三角形，然后从左侧开始。为什么我们不从文件夹开始，将最后一行用作初始累加器呢？ foldr的问题在于，我们必须显式指定一个初始累加器，但是某些语言（例如Haskell）具有内置函数foldr1，该函数自动使用列表的最后一个元素作为初始中间值。球拍没有它，但我们可以轻松实现它。

;; ----------------------------------------------------------------------------
;; bottom-up, with foldr1

(define/match (foldr1 f lst)
  [(_ (list x)) x]
  [(_ (list-rest x rest)) (f x (foldr1 f rest))])

(define (max-tri-route4 tri) (first (foldr1 process-row/bottom-up tri)))

当然，foldr1函数假定您给它的列表至少包含一个元素。通过使用foldr1函数并使用以前的process-row / bottom-up函数，我们的解决方案现在是单行函数。这也可能是您看到的Haskell解决方案的样子。

有关具有此代码的完整程序，请参见 here。