動的計画法とメモ化の実行状況が見たい

N x N のマス上にいくつか穴が開いていて、2マスを使うドミノを置いて、穴以外のマスを埋めることができるか、という問題があるとする。愚直に一つずつ試していくやり方としては、動的計画法が使える。ドミノは2マス使うので、縦に置くか、横に置くか、の選択肢がある。それぞれで処理を再帰呼び出しで分岐して、最終的にマスを埋めることができたかどうか、を判定すればよい。

ただし、これだけだとスケールしない。全く同じ盤面が何度も出てくるのに、毎回調べなければならないからだ。マスを埋めることができなかった、と判断された盤面が再度現れたときには、答えは分かっているのだから、それ以上処理を継続する必要はないはずだ。それを実現するのがメモ化(つまりキャッシュ)。動的計画法は、このようにメモ化と組み合わせて実現される。

Cの実装

メモ化に使うデータ構造をどうするか、つまり、盤面を覚えておく効率的なデータ構造、を考えなければいけない。ここでは、ドミノ(< >^ Vで示される)で埋めたマスが連続する数と、埋まっていないマス(_)が連続する数、を配列として持つことにする。つまり、

< > < >
+ ^ _ +
+ V _ _

という盤面があるとすると、6 3 1 2 になる。穴(+)についてはこだわらなくて良いので、それまでカウントしていた方の一部としてカウントする。今回は、盤面に対する情報はTrueかFalseなので、キャッシュの配列に含まれる場合はTrue(マスを埋めることができなかった)と考えれば良い。

マスを埋めることができた場合には、その盤面を出力している。また実行結果には、キャッシュにヒットした回数も出力している。

f:id:nishidy:20160828125539g:plain

  • 8x8マス。30回連続で別の盤面を実行。

f:id:nishidy:20160828131607g:plain

Javaの実装

上記のようなデータ構造は使いづらい。盤面を覚えておくのであれば、全ての盤面に対して一意のIDを割り当てることができればいいので、そういう用途ではmd5ハッシュ値が使える。JavaのDigestUtils(標準ライブラリでは無い)を使って実装した。注意すべきなのは、ドミノがどの方向で置かれていても同じように扱う必要があるので、盤面をコピーしてドミノの部分を共通のマークに入れ替えてからハッシュを取る必要がある。

f:id:nishidy:20160828132115g:plain

アルゴリズムについて

このような問題に対して動的計画法とメモ化を使うのは、やり方として間違っていないものの、データ範囲が大きくなるにつれて収束が難しくなる。Code Jamで言えば、Smallまではこのやり方で問題無いが、Largeを解くためには、このように愚直に試すやり方ではなく、盤面を俯瞰的に見ることでうまくいくかどうかを検証するアルゴリズムが必要になる。

なんとなく以下のような構造が出てくると、うまくいかないということは分かる...

+ _ +
_ _ _