Python3 - 動的計画法(フィボナッチ数列)

動的計画法は、分割統治法とメモ化を合わせた方法のことらしい。分割統治法は、問題を細分化して、細かい部分を順に解いていくことで全体を解明するようなことの総称らしい。

分割統治法は、コード的には下記のようになり、再帰することになる。

function conquer(x)
  if xは簡単にconquerできる then
    return conquerの結果
  else
    (x1, x2, ...) := divide(x)     // 複数の小さな副問題に分割
    (y1, y2, ...) := (conquer(x1), conquer(x2), ...)  // 再帰
    return synthesize(y1, y2, ...)  // 各副問題の解を合成（最大値を選ぶ、等）

メモ化とは、再帰の際に同じ副問題を複数回解いてしまうことによる効率低下を防ぐために、副問題の結果を保存して再利用することらしい。キャッシュみたいな感じ。

下記のフィボナッチ数列を表示するプログラムは、動的計画法の具体的な例らしい。

int fib(unsigned int n) {
    int memo[1000] = {0, 1}, i;
    for (i = 2; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[n];
}

Python3だと下記のような感じ。

def fib(n):
    memo = [0] * n
    memo[0:2] = [0, 1]
    for i in range(2, n):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[0:n]
print(fib(100))

ちなみに、ネットでフィボナッチ数列のPython版しらべたら下記がでてきたけど、これはまさしく動的計画法じゃない例だと思った。毎回メモらずに計算しているようだ。

def fib2(n, a=1, b=0):
    return b if n < 1 else fib2(n - 1, a + b, a)
print([fib2(i) for i in range(100)])

せっかくだから時間図ってみる。

import time

def fib(n):
    memo = [0] * n
    memo[0:2] = [0, 1]
    for i in range(2, n):
        memo[i] = memo[i - 1] + memo[i - 2]
    return memo[0:n]
start = time.time()
print(fib(900))
print(time.time() - start)

def fib2(n, a=1, b=0):
    return b if n < 1 else fib2(n - 1, a + b, a)
start = time.time()
print([fib2(i) for i in range(900)])
print(time.time() - start)

結果

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...
0.001961946487426758
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...
0.0782785415649414

おー40倍速いってことか。さすが動的計画法だ。

下記のような方法もある。

#include <stdbool.h>

int memo[1000] = {0, 1};
bool in_memo[1000] = {true, true};

int fib(unsigned int n) {
    if (!in_memo[n]) {
        memo[n] = fib(n - 1) + fib(n - 2);
        in_memo[n] = true;
    }
    return memo[n];
}