【Ruby】動的計画法を考える①「フィボナッチ数列」

全探索では解けないような難しい問題を解くのに欠かせない「動的計画法」について考える。

そもそも動的計画法が何なのかをざっくり言うと、
「計算結果をメモしながら解くと、効率よく問題を解ける」
という、問題を解くための指針である。

「それのどこが動的で計画なのよ？」と思うだろう。
正直、名前だけではイメージは付きにくい。
動的は「その時に決まる」という意味であり、
「その時その時に計画する」というのはもはや無計画に見える。

"Dynamic Programming" という英語名から考えると
「動的にプログラムを生成している…？」ようにも捉えられるだろう。

実際には要素を一つずつ計算していき、その時の計算結果が次の計算に用いられる。
つまり
「その時の計算結果が次の計算の予定になる」ために
「動的に計画している」といえる。

問題によっては、計算結果に以下のパターンが現れる。

その情報を整理することで計算量を減らし、多項式時間の計算に納められるという技術だ。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

これらの数は「前の二つの数を足し合わせたもの」という法則で並んでいる。
これを「フィボナッチ数列」という。
これは以下のような漸化式で定義される。

$F_0=0$
$F_1=1$
$F_n=F_{n-1}+F_{n-2}$
$(n\geqq2)$

フィボナッチ数列では「ある数は一つ前の数と二つ前の数を足したもの」であるため
一つのものから二つに分かれていく…つまり「二分木」のような構造で表せる。

この構造を全て埋めていくことがフィボナッチ数列の計算とも言える。
しかし、数列の次の数を計算しようとする度、この構造の大きさも2倍程度に増えてしまう。
故に計算量も $O(2^n)$ となる。
よく見ると重複する部分があり、無駄な計算をしていることが分かる。

そんな愚直な計算はしなくていい。
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
この次は89 + 144 = 233 であると簡単に分かる。
計算結果をメモしながら解いていくと効率がいいと言うのはこういうことだ。

実際に $F_n$ はいくつなのかを計算するプログラムを組んでみる。

def f(n)
  return n <= 1 ? n : f(n - 1) + f(n - 2)
end

puts f(10) # => 55

数式の関係性を再帰関数で表すだけで簡単にプログラムにすることができる。
計算量は $O(2^n)$ になる。n=40で約1兆という増え方である。

@memo = []
def f(n)
  return n <= 1 ? n : @memo[n] ||= f(n - 1) + f(n - 2)
end

puts f(70) # => 190392490709135

やることは簡単で、配列を作り、そこに計算結果をメモさせる。
メモに計算結果があれば再帰せずそれを利用する。
再帰にメモを組み合わせるので「メモ化再帰」とも呼ばれる。

ゴールからスタートへ( $F_n$ → $F_0$ )向かって実行される(トップダウン方式)。

n = 70
memo = [0, 1]

i = 2
while i <= n
  memo[i] = memo[i - 1] + memo[i - 2]
  i += 1
end

puts memo[n] # => 190392490709135

再帰関数はスタック上限に引っかかったり、パフォーマンスで不利な場合がある。
この場合であれば単純なループでも実装できる。

スタートからゴールへ( $F_0$ → $F_n$ )向かって実行される(ボトムアップ方式)。
計算量は $O(n)$ にまで減り、非DPのものとは雲泥の差である。

※
2024/12/12 一部の表現が分かりにくかったり不正確だった感じがしたので、記事を修正。

地上の洞窟