racket - Lazy Racket での動的プログラミング

Question

怠惰なラケットで動的プログラミングを行う方法を覚えようとしています。Project Eulerの問題の1つを解決した後、私はこれを疑問に思い始めました:

下の三角形の上部から始めて、下の行の隣接する数字に移動すると、上から下までの最大合計は 23 になります。

   3
  7 4
 2 4 6
8 5 9 3

つまり、3 + 7 + 4 + 9 = 23 です。

下の三角形の上から下までの合計の最大値を求めてください: ...

以下のコードで解決しました。しかし、私は学校でレイジー ラケット (および実際にはプログラミング言語全般) について教えられました。レイジー言語では、動的プログラミングの問題を解決する方がはるかに簡単であることを覚えているようです。たとえば、他のユーラー主義者が投稿した解決策では、問題を解決するために使用した haskell コードを投稿しましたが、問題のデータを実際に指定するのにかかったコードはわずか 1 行でした (三角形の中にあるもの)。自体）。しかし、私はコードを理解していなかったので、まだ混乱しています。

概要：

1. 怠惰なラケットで動的プログラミングの問題をどのように解決しますか? 例として、答えは上記のように（完全な15レベルの三角形ではなく）4レベルの三角形の例を解決するか、以前に作成された編集距離コードを投稿する可能性があります（これが私が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

特定の種類の問題の場合、怠惰により、ソリューションをモジュール式の優れた方法で整理できます。最初に、考えられるすべてのソリューションを生成しているかのようにコードを記述し、次にコードを個別に記述して、解決策は有効な解決策です。怠惰な言語では、そのようなアルゴリズムは最終結果を計算するのに十分な可能な解決策のみをチェックし、他のすべての可能性は当然計算されないため、バックトラックなどのより複雑な戦略と同じくらい効率的です。

正規の例は、数独パズルを解くためのアルゴリズムです（グーグル検索でたくさんの例が見つかります）。JohnHughesによる「関数型プログラミングが重要な理由」という論文にも興味があるかもしれません。

そうは言っても、この特定のケースでは、怠惰はあまり役に立ちません。熱心な言語または怠惰な言語のいずれかでの動的計画法スタイルのソリューションは正常に機能します（そしてほぼ同じように見えます）。

このような問題を解決するときは、最初に単純な解決策を計算してからそれを改善すると役立つことがよくあります。素朴なソリューションは、可能なすべての合計を計算してから、最大値を取ります。小さな三角形の例では、3 + 7 + 2 + 8、3 + 7 + 2 + 5などを計算しますが、それを書き留めるだけで、3 + 7 + 2が繰り返されるため、改善の可能性がわかります。このような繰り返しの計算を回避することは、まさに動的計画法が行うことです。動的アルゴリズムは、これらの中間結果を1回だけ計算し、それを複数回再利用します。

これを行うには、一度に1行ずつ、最大合計を段階的に計算します。この方法で最大合計を計算する関数は、次のようになります。

（注：このラケットコードを実行するには、最新のナイトリービルドをインストールする必要があります。）

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

三角形はリストのリストで表され、各サブリストは行を表すと想定しています。三角形の最初の行は、増分計算された合計を表すと想定しています。この関数は、行が1つしかない場合は、その行の最大値を取得することを示しています。それ以外の場合は、最初の行（これまでの合計）と2番目の行を使用してprocess-row関数を呼び出します。process-row関数は、2番目の行を中間合計に組み込み、次のようになります。

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

この関数は、2番目に指定された行が常に最初に指定された行よりも1つ多い数を持っていることを前提としています。指定された2つの行にそれぞれ1つと2つの番号しかない場合は、最初の行の番号を2番目の行の各番号に追加するだけです。それ以外の場合は、一度に3つの数値を考慮して新しい中間合計を計算します。1つは最初の指定された行から、2つの隣接する数値は2番目の指定された行からです。もちろん、2番目に指定された行（端を除く）の各番号には、最初の行から2つの隣接する番号があるため、大きい方の番号のみを取得します。たとえば、小さな三角形の例では、最初の2行でprocess-rowを呼び出すと、中間値10と7が生成されます。次に、process-rowが107で呼び出され、次の行が2 4 6である場合、最初に10を2で考慮します。および4、12および14を生成します。しかし、それはまた、以下の4で7を考慮する必要があります。7 + 4 = 11は14未満であるため、保持する中間合計は14です。3行目を組み込んだ後の結果の中間合計は121413です。

上記の解決策は、問題67の三角形に対しても、効率的に正しい答えを生成します。しかし、特に、重複するケースを考慮しなければならないプロセス行の2番目の部分では、少し厄介な感じがします。ソリューションを改善できるかどうか見てみましょう。

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

ボトムアップアプローチでは、最後に1つの値、つまり最終的な答えがあります。また、2つの数値のうち大きい方を直接保持できるため、process-row/bottom-upはprocess-rowよりも単純です。

しかし、私たちはさらに良いことをすることができます。

＃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はリストの左側から始まりますが、ボトムアップにしたいので、最初にリストを逆にします。最初の（つまり一番下の）行を初期中間値として使用し、残りの行を三角形として使用します。完了すると、1つの値、つまり回答のリストが表示されます。

＃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関数は、指定したリストに少なくとも1つの要素があることを前提としています。foldr1関数を使用し、以前のプロセス行/ボトムアップ関数を使用することで、ソリューションは1行の関数になりました。これはおそらく、あなたが見たHaskellソリューションも同様に見えたものです。

このコードを含む完全なプログラムについては、ここを参照してください。