racket - Lazy Racket 中的动态编程

Question

我试图记住如何在懒惰的球拍中进行动态编程。在我解决了 Project Euler 的一个问题后，我开始怀疑这一点：

通过从下方三角形的顶部开始并移动到下方行中的相邻数字，从上到下的最大总数为 23。

   3
  7 4
 2 4 6
8 5 9 3

也就是说，3 + 7 + 4 + 9 = 23。

求下面三角形从上到下的最大总数：...

我用下面的代码解决了这个问题。然而，我在学校里被教过惰性球拍（实际上是一般的编程语言），我似乎记得在惰性语言中，解决动态编程问题要容易得多。例如，在其他 eulerists 发布的解决方案中，一个人发布了他用来解决问题的 haskell 代码，而实际上只需要一行代码就可以指定问题中的数据（三角形中的内容是什么）本身）。但是，我不理解代码，所以我仍然感到困惑。

概括：

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

下面给出了我用来解决常规球拍中 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 的一篇名为“为什么函数式编程很重要”的论文感兴趣。

话虽如此，在这种特定情况下，懒惰并没有多大帮助。使用 Eager 或惰性语言的动态编程风格的解决方案都可以正常工作（并且看起来大致相同）。

在解决这样的问题时，首先计算一个简单的解决方案然后改进它通常很有帮助。天真的解决方案将计算所有可能的总数，然后取最大值。对于小三角形示例，您将计算 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 函数将第二行合并到中间总计中，可能看起来像这样：

;; 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 和下一行 2 4 6 调用 process-row，它首先会考虑 10 和 2和 4，产生 12 和 14。但它也必须考虑 7 和下面的 4。由于 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)))])

使用自下而上的方法，我们最后只有一个值，即最终答案。此外，process-row/bottom-up 比 process-row 更简单，因为我们现在可以直接保留这两个数字中的较大者。

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

采取＃3：

这种遍历列表并累积中间值的模式非常普遍，因此有内置函数可以做到这一点：foldr 和 foldl。这些函数中的每一个都需要一个要遍历的列表、一个初始中间值以及一个将列表中的下一个值与当前中间值组合的函数。但是我们需要的组合函数是什么？事实证明，这正是我们的 process-row 函数。这是 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 开始，使用最后一行作为初始累加器？foldr 的问题是我们必须显式指定一个初始累加器，但是像 Haskell 这样的一些语言有一个内置函数 foldr1，它自动使用列表的最后一个元素作为初始中间值。Racket 没有它，但我们可以轻松实现它。

;; ----------------------------------------------------------------------------
;; 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 解决方案的样子。

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