エンジニア実践的基礎: 動的計画法

背景

このシリーズでは、エンジニアとして7年目を迎える節目に、これまで蓄積した知識を整理し、共有します。すべての記事を読めば、ミドルエンジニアとしてのスキルを身につけることができます。コンピュータサイエンスの理論よりも、実践的なソフトウェアエンジニアリングの知識に焦点を当てています。コーディングインタビューにも役立つ内容です。データ構造とアルゴリズムから設計、要件定義、バージョン管理、アジャイルなチーム開発、データベース、ネットワークなど、幅広いテーマを扱います。要するに、仕事に困らないレベルの知識を網羅します。

動的計画法とは？

動的計画法は、再帰処理を最適化した手法です。再帰では同じ部分問題を何度も計算することがあるため、これを記録（メモ化）し、再利用することで重複する計算を排除し、時間計算量を削減します。このアプローチをトップダウン式動的計画法と呼びます。しかし、この方法をさらに最適化することで、すべての部分問題の結果をメモ化する必要がないことに気づきます。具体的には、直前の結果だけを保持し、必要に応じてその結果を上書きしていくことで、同じ計算結果を得ることができます。この最適化手法がボトムアップ式動的計画法です。理屈だけだとわかりにくいため、動的計画法の代表的な例であるフィボナッチ数列を確認しましょう。

フィボナッチ数列とは「1、1、2、3、5、8、13、21、34、55、89、144、233…」のように、前の数字を足した数が続く法則のことです。1,23,…n 番目のフィボナッチ数列の実装は以下の通りです。

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

この実装は答えは正しく得られますが、同じ処理を繰り返すため効率が悪いです。決定木を確認しましょう。

緑枠で囲まれた処理が重複しています。15処理中の9処理が同じ処理を繰り返しています。これらの重複した処理の結果を記録して再利用すれば、計算量を節約できます。

重複を排除する前は、数字ごとに2通りの選択肢があるため時間計算量は O(2^n) です。メモ化すると数字の数だけ処理が必要なので O(n) まで減ります。インプットに対するアウトプットを記録するため、ハッシュマップで記録します。ハッシュマップは0(1) で検索できるため、高速メモ済みか調べられます。

def fibonacci(n, memo):
    if n == 0:
        return 0
    if n == 1:
        return 1
    # メモ化されている場合はそれを返す
    if n in memo:
        return memo[n]
    
    # メモ化されていない場合は計算してメモ化する
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)

    return memo[n]

print(fibonacci(5, {}))

もっと突き詰めて考えてみましょう。そもそも、フィボナッチ数列の計算には次の2つの数字だけ必要です。

• 1つ前の数字

• 1つ前と2つ前の数字の合計値

これら2つの数字だけをメモして反復処理をすれば再帰も不要になり、空間計算量を 0(1) に抑えられます。

上の画像を計算式に表すと次の通りです。

0 + 1 = 1
1 + 1 = 2
1 + 2 = 3
2 + 3 = 5

これをボトムアップ式動的計画法と呼びます。トップダウン式動的計画法は決定木を上から下に処理したましたが、ボトムアップ式動的計画法はベースケースから徐々に上に上がって処理します。

def fibonacci(n):
    num1 = 0
    num2 = 1
    for i in range(n-1): # n = 5 のとき、n = 4 の合計値が戻り値になるため n - 1
        num1, num2 = num2, num1 + num2
    return num2

print(fibonacci(5))