月謝3500円のそろばん塾で出たチャレンジ問題(動的計画法で)
Arigataさんが書かれたエントリをフムフムと呼んでいて、MSのソルバに興味を持ちつつ、そもそも「部分和問題」という言葉も「ナップザック問題」という言葉も知らなかった自分の不勉強に恥じ、ちゃんと勉強しないとなぁ・・・と考えているだけの日々を送っていたのですが、何の因果か「
アルゴリズムを学ぼう」などという本が絶好のタイミングで出てしまい、この中にこの「ナップザック問題」の解説が乗っていたので、これを参考にF#で「動的計画法」を使った解法を試してみることにしました。
動的計画法
まず基礎知識として、このそろばん塾の問題は、「
部分和問題」という有名なカテゴリに属する問題で、金額の部分が整数でない場合には「
NP完全」という、要素数が上がるにつれ幾何級数的に計算量が増えていく性質を持っているということです。
- 金額の部分が整数でかまわない(重さのように少数点の値を考慮しない)。
- とにかくひとつ解が見つかればよい。見つからない場合はリミットを超えない範囲で最大の値がわかればよい。
動的計画法については「アルゴリズムを学ぼう」や他のサイトに詳しい解説がありますので、そちらを参照してもらったほうがいいと思います。
「アルゴリズムを学ぼう」は、限られたページで沢山のアルゴリズムを紹介しようとするあまり、一つ一つの解説は少な目となっており、動的計画法もこの本を読んだだけではちょっとわかりづらいかもしれません。動的計画法はとても有名なアルゴリズムなので解説ページも多いのですが、僕は「
Gushwell's C# Programming Page」や「
Algorithms with Python」のの下半分にある説明が一番わかりやすい気がしました。下のサンプルも、この説明と「アルゴリズムを学ぼう」の説明を読んで頭に入れ、電車の中で書き起こしたものです。
実装
let goods = [ ("プロ野球", 19373)
("ディズニーランド", 20453) ~ 前回のものを使用 ~
let max3f x y z f = let max_xy = max x y in if z > max_xy then f () ; z else max_xy
let dp l target =
let ar : int array = Array.zeroCreate (target + 1)
let g : (string * int) array = Array.zeroCreate (target + 1)
for gds in l do
let wk = snd gds
for w in [target..(-1)..1] do
ar.[w] <- max3f
ar.[w]
ar.[w - 1]
(if w >= wk then ar.[w - wk] + wk else 0)
(fun () -> g.[w] <- gds)
// printfn "%A" ar
ar, g
let rec pp (g : (string * int) array) (ar : int array) pnt =
printfn "%A" g.[pnt]
if ar.[pnt] > (snd g.[pnt]) then pp g ar (ar.[pnt] - (snd g.[pnt]))
let solve total =
let res, g = dp goods total
pp g res total
solve 150000
実行結果は以下のようになります。
("にくまん", 155)
("机いす", 67275)
("リポD", 1737)
("CDプレーヤー", 36307)
("電動歯ブラシ", 4282)
("たこ焼き", 534)
("ピアニカ", 3351)
("回転ずし", 15906)
("ディズニーランド", 20453)
val dp : seq<string * int> -> int -> int array * (string * int) array
val pp : (string * int) array -> int array -> int -> unit
val solve : int -> unit
val it : unit = ()
ざっくりとした解説
最初の関数max3fは、三つの数と関数(unit->unit)を引数にとります。三つの引数のうち、最大の値を返すのですが、最後の数が一番大きかった場合だけ、引数で渡された関数を実行する機能を持っています。
二つ目の関数dpがこのプログラムの心臓部です。金額(150000)ぶんの配列を用意し、それぞれの金額ごとにどのように商品を買うのが一番いいかを考えていきます。
forループが2段になっていますが、外側では商品リストについて、内側では金額ごとのループを回っています。内側のループが減数ループになっている点に注目してください。このプログラムは配列arを変えながら動くのですが、ループの中でar.[w - wk]を参照しているため、後ろから値を変えていかないとまずいのです。このあたりのことについては、上記の本と二つのサイトを読んでじっくり考えてもらえばわかると思います。
ループの中は、max3fを呼び出し、参つの値の最大値を取りつつ、最後の数が一番大きかった場合だけ商品購入配列gを更新しています。
最後にar,gで計算結果を返しています。ちょっと信じがたいですがこれで結果が得られるのです。
再帰関数ppはdpの結果として得られた二つの配列から、購入すべき商品の一覧を抜き出して出力する関数です。
最後のsolveは、dpを呼び出してppに渡すだけの関数です。
雑感
前回のエントリでは、「ちょっとコーヒーを淹れてるぐらいの時間」などと書いていますが、この「動的計画法」を使うと最初の解にたどり着くのに必要な時間は「Enterキーが戻るぐらい」になってしまいます。つまり0.1秒以下ということです。
とてつもない高速化と言えますが、動的計画法を知らなかった僕は前回のエントリのプログラムで満足していました。
もちろん、動的計画法が使えない場合(全部の解を列挙しなければならないなど)は、前回の方法が有効なのですが、アルゴリズムを知っているか知らないかでこれほどの結果の差が出るのですから、やはりプログラマは日々勉強しなければいけないということなのでしょう。
例によって上のプログラムは一例ですので、いろいろな方法(ArigataさんのようにSolverを使った方法など)や実装の流儀がありますので、上で挙げたサイト以外の情報も含めていろいろあたってみてください。
(文責:片山 功士 2012/06/06)
今日: - 人
昨日: - 人
トータル: - 人
最終更新:2014年05月05日 22:02