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方言でそのようなことを行うことは可能ですか？いいえの場合、なぜですか？

4

4 に答える 4

15

もちろん、これは可能です。必要なのは、配列、整数、およびループ構造だけです。たとえば、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や同様の言語でプログラミングするときはメモ化に固執することをお勧めします。ハッシュテーブルを使用する場合、予想される漸近的な時間とスペースの複雑さは、メモ化とDPで同じです。

于 2011-10-19T16:50:43.590 に答える
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)))

Idomatic Clojureコードがどのように見えるかの基本的な概念は、問題を単純な（1つのことだけを行う）抽象化に分解し、それらを構成して主要な問題を解決することです。もちろん、これは常に目前の問題に合うように調整する必要があります。

于 2011-10-19T18:09:01.950 に答える
4

これを言って申し訳ありませんが、あなたが参照しているウィキペディアのページは（imnsho）あまりよく書かれていません。特に、それは多かれ少なかれトップダウンとボトムアップの動的計画法の間の二分法を作り上げ、そしてそれを「より興味深い」と表現し続けます。2つの違いは、テーブルが作成される順序だけです。メモ化により、呼び出しが行われる順序に応じて、これらの両方が発生します。

ページのこのセクションを書いた人には事前に謝罪します。私はあなたの努力に感謝します、私はただセクションがいくらかの仕事を必要としていると思います。

于 2011-10-19T17:01:25.753 に答える
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
于 2011-10-19T20:26:01.703 に答える