フィボナッチ数と動的計画法
40番目のフィボナッチ数をいちばん素直な方法でコンピューターに求めさせると、3億3100万回を超える呼び出しが行われます。表を使えば、足し算は39回で済みます。この違いが動的計画法であり、ほとんどの人が最初に出会うのがフィボナッチ数です。
問題
フィボナッチ数は 0, 1 から始まり、その後の数はすべて直前の2つの数の和です。0, 1, 1, 2, 3, 5, 8, 13, 21 と続きます。規則として書くと、F(0) = 0、F(1) = 1、F(n) = F(n − 1) + F(n − 2) です。この規則は再帰的で、そのまま再帰のプログラムにするのは簡単ですが、そのプログラムはとても遅いことがわかります。
再帰が同じ計算を繰り返す理由
F(5) を求めるために、プログラムは F(4) と F(3) を求めます。F(4) は F(3) と F(2) を求めるので、F(3) は2回、F(2) は3回、F(1) は5回計算されます。木として描くと、呼び出しは段を下るごとにほぼ2倍になり、F(n) の合計は 2·F(n + 1) − 1 回です。小さな問題が重なり合い、同じものが何度も出てきます。これが、動的計画法が役に立つというサインです。
覚えておく2つの方法
メモ化は再帰をそのまま使いますが、答えをすべて表に書き込み、どの呼び出しも計算を始める前に表を確認します。表を使う方法は、表をボトムアップで埋めます。まず F(0) と F(1)、次にそれらから F(2)、F(2) と F(1) から F(3)、というように F(n) まで進みます。どちらの方法でも各項は1回しか計算されないので、F(n) は指数的な回数の呼び出しではなく、n − 1 回の足し算で求まります。
計算例
F(7) をボトムアップで求めます。0 と 1 から始めます。次に 0 + 1 = 1、1 + 1 = 2、1 + 2 = 3、2 + 3 = 5、3 + 5 = 8、5 + 8 = 13 となり、6回の足し算で F(7) = 13 です。単純な再帰では、同じ答えに 2·F(8) − 1 = 41 回の呼び出しが必要です。トップダウンでは、最初の呼び出しが木の左端に沿って F(1) まで下りていきます。戻る途中では、ほぼ2回に1回の呼び出しで答えがすでに表にあります。
名前の由来
リチャード・ベルマンは1950年代初め、ランド研究所(RAND Corporation)で働いていたときに動的計画法と名づけました。のちに彼は、programming は「計画を立てる」という古い意味で選び、dynamic は響きが立派で反対しにくいから選んだと書いています。小さな問題の答えを使って問題を解くというこの方法は、今ではスペルチェック、経路探索、DNA の比較などで使われています。
試してみよう
アプリを開いて「ステップ」を押してください。ボトムアップでは、オレンジのセルが記入中のセルで、2つの青いセルが足し合わせる項です。トップダウンに切り替えると、表の下の呼び出しのスタックが n まで伸び、答えが返ってくるにつれて縮んでいきます。「足し算の回数」の下のヒントには、表から直接答えが得られた呼び出しの数が表示されます。
よくある質問
部分問題が重なるとはどういうことですか?
解くために2回以上必要になる小さな問題があるということです。F(n) と F(n − 1) はどちらも F(n − 2) を必要とするので、単純な再帰ではそれを2回計算し、下に行くほど無駄が増えていきます。動的計画法は各部分問題を1回だけ解いて答えを覚えておきます。
メモ化は表を使う方法より速いですか?
どちらも足し算は同じです。表を使う方法は呼び出しをしないので通常は少し速く、スタック領域が足りなくなることもありません。メモ化は、小さな答えの一部だけが必要なときに便利です。必要なものだけを計算するからです。
フィボナッチ数はもっと速く計算できますか?
はい。F(2k) = F(k)·(2·F(k + 1) − F(k)) と F(2k + 1) = F(k)² + F(k + 1)² を使う高速倍加法なら、約 log₂ n ステップで済みます。黄金比を使ったビネの公式でも同じ数が得られますが、丸め誤差のため n が大きいと信頼できません。
表にはどれくらいのメモリが必要ですか?
表全体には n + 1 個の数が入りますが、新しい項に必要なのは直前の2項だけなので、2つの数だけを持つループなら一定のメモリで同じ計算ができます。すべての項が欲しいときや、方法のしくみを見たいときには、表全体を持っておくと便利です。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
動的計画法でフィボナッチ数を試す