The Secret Number (Problem C, 2003 Japan Domestic) [2/3]
前回はDP（動的計画法）で "http://www.acm-japan.org/past-icpc/domestic2003/C.htm" を解きました。今回と次回ではこれをmemoize（メモ化）で解いてみることにします。
さて，前回は全探索時の計算量を（組み合わせ論の知識を用いて）解析的に求めました。今回は違う方法で求めてみることにします。
前回の全探索法は次のようになっていました：
真っ先に思い浮かぶのは始点となるノードを探して，そこから再帰で右or下に数字があれば連結していくという手法。コーディングはこんな感じ（記法はPython-likeな適当言語です）：
def rec(x, y, string): string += field[x][y] if stringがmaxよりも大きければ: max = string if 右が数字: rec(x+1, y, string) if 下が数字: rec(x, y+1, string) max = "" for x in [0, WIDTH): for y in [0, HEIGHT): if field[x][y]が数字 and 左が非数字 and 上が非数字: rec(x, y, "")
では，再帰関数による探索の分かれ道を数えてみましょう。最初は小さいフィールドで考えてみます。1x1の場合，分かれ道は1通りです。2x2の場合，分かれ道は2通りです。さらに，縦と横のどちらかが1列しかなければ，1通りになります。
次に3x3の場合を考えてみます。これは2x2が（左上に）一段大きくなったものと見做すことができます。左上を頂点に考えると，新しく追加されたマス目からの道のりは次の図のように4通り（(W-1)+(H-1)通り）しかありません。従って，それらの4通りがそれぞれ何通りであるかを調べ，それらを足していけば3x3の計算回数（探索の分かれ道の数）を求めることができます。
以上より，漸化式で書けば，計算回数は
で求められます。
これをそのままコーディングすると次のようになります（このプログラムはPythonで実行できます）：
#! /bin/env python
import sys
def rec(x, y):
if x == 1 or y == 1:
return 1
else:
sum = 0
for i in range(1, x):
sum += rec(i, y-1)
for i in range(1, y):
sum += rec(x-1, i)
return sum
for n in range(1, 36):
sys.stdout.write("%dx%d -> %d\n" % (n, n, rec(n, n)))実際に実行してみると分かりますが，このプログラムは（現在のPCでは）14x14あたりから計算がすぐに終了しなくなります。というのも，このアルゴリズムは再帰による分岐数が非常に多いからです。4x4の場合のrec(x, y)の呼び出しをトレースしてみると，次のような結果になります：
(4, 4) |-(1, 3) |-(2, 3) | |-(1, 2) | |-(1, 1) | |-(1, 2) |-(3, 3) | |-(1, 2) | |-(2, 2) | | |-(1, 1) | | |-(1, 1) | |-(2, 1) | |-(2, 2) | | |-(1, 1) | | |-(1, 1) |-(3, 1) |-(3, 2) | |-(1, 1) | |-(2, 1) | |-(2, 1) |-(3, 3) | |-(1, 2) | |-(2, 2) | | |-(1, 1) | | |-(1, 1) | |-(2, 1) | |-(2, 2) | | |-(1, 1) | | |-(1, 1)
5x5を計算する場合，少なくともこの4x4の計算を2回含むわけですから，5x5は4x4の2倍以上の計算回数が必要で，計算量は で爆発してしまってnが大きくなると動きません（nに対してスケーラビリティがないわけです）。
ではこのアルゴリズムはダメなのかというとそうでもなく，非常に簡単な工夫をすれば立派に動きます。上記の4x4の場合では，3x3の計算を2回行っていますが，これは1回行えば結果は分かっているので，2度計算する必要はないはずです。前回の3x3の結果をキャッシュしておけば無駄な重複計算を省くことができるわけです。
この計算結果をキャッシュしておくことをmemoize（memoization，メモ化）と呼びます*1。実例を見せましょう。上記のプログラムをmemoizeすると：
#! /bin/env python
import sys
cache = {}
def rec(x, y):
if cache.has_key((x, y)):
return cache[(x, y)]
if x == 1 or y == 1:
return 1
else:
sum = 0
for i in range(1, x):
sum += rec(i, y-1)
for i in range(1, y):
sum += rec(x-1, i)
cache[(x, y)] = sum
cache[(y, x)] = sum
return sum
for n in range(1, 36):
sys.stdout.write("%dx%d -> %d\n" % (n, n, rec(n, n)))となります。cacheを操作する分で5行だけ追加しています。このようにキャッシュにハッシュテーブル（Python方言で言えば辞書）という O(1) アルゴリズムを使えば，計算回数（探索の分かれ道の数）を求めるアルゴリズムは十分に高速になります。
考え方は単なるキャッシュなので簡単なのですが，memoizeという用語に関連して少しうんちくを垂れておきましょう。数学の関数とCやJava，Pythonのような命令型言語の関数との決定的な違いというものがあります。それは，数学の関数は全引数の値を固定すれば必ず結果は同じになるのに対して，命令型言語では必ずしもそうならない（例：if文でグローバル変数を参照して分岐）ことであり，違う言い方をすれば命令型言語には（副作用のある）代入という操作がある，ということです。数学の関数のように外部の状態を参照しなければ，関数に渡された引数をハッシュテーブルのキーに対して値をキャッシュすることで（どんな関数でも）確実にmemoizeができます。逆に言えば，外部の状態に依存しているならばその保証はないわけです。
ちなみに，数学の関数のように代入のような副作用がない関数を（主に）用いる言語を関数型言語と呼びます（Lisp, Scheme, Haskellなど）。関数型言語を使っている場合は再帰関数を多用するわけですが，（副作用のない）再帰関数の最初にチェックを，最後に計算結果の保存をすれば手軽に確実にmemoizeができるので，（副作用のない）再帰関数とmemoizeは相性がよいのです。ただし，副作用がなければ計算結果の保存が難しいので，そこだけは代入の副作用に頼った方が楽なのですが。
memoizeは非常に一般的な手法なので広く様々な場面で使えます。DPと比較すると，DPは個々の問題に応じてアルゴリズムが大きく異なるのに対して，memoizeは再帰関数にキャッシュを付けるだけ，という利点があります（再帰関数でなくてもキャッシュを行った方がよい場面は多々あるでしょう）。探索問題の解法をDPだけではなく同時にmemoizeでも考えられると，その問題を解ける可能性は高まることと思います。
さて，前置きが長くなりましたが，次回は "http://www.acm-japan.org/past-icpc/domestic2003/C.htm" を実際にmemoizeで解いてみます。
