読者です 読者をやめる 読者になる 読者になる

Learn to Live and Live to Learn

IT(たまにビジネス)に関する記事を読んで、考えて、使ってみたことをまとめる場。

PHPで実践する動的計画法

※Qiitaに”動的計画法とメモ化”を説明する記事を書きましたので,こちらにも記載したいと思います.内容は全く同じです(>_<) qiita.com

動的計画法とメモ化

動的計画法(Dynamic Programming)とメモ化(Memorization)は,競技プログラミングなんかでよく使われるアルゴリズムの一緒です. 両者とも計算結果を保存し再利用することで,重複した計算による時間ロスを防ぐものです.

例を示しながら説明したいと思います.

動的計画法 or メモ化を使う動機

まず,フィボナッチ数列とは

n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に F0 = 0, F1 = 1, F(n + 2) = Fn + (Fn + 1) (n ≧ 0)

で定義される数列です.(Wikipediaより)

標準入力から入力される数字を n とし n 番目(0番目スタート)のフィボナッチ数を求めたい場合どう実装するでしょうか.

(色々な方法はあると思いますが)数学的に一般項を求めようとせず,定義をそのまま使うと,こんな感じの再帰的な処理が書けると思います.

<?php
fscanf(STDIN, "%d", $n);
echo fib($n) . "\n";
function fib($n) {
    if ($n == 0) return 0;
    if ($n == 1) return 1;
    return fib($n - 1) + fib($n - 2);
}

しかし,これだと尋常じゃない時間がかかります. n=4でもこれだけ再帰的にfib関数が呼ばれるんです↓

fib(4) = fib(3) + fib(2)
 = (fib(2) + fib(1)) + (fib(1) + fib(0))

この時間を短縮しくてれるのが動的計画法 or メモ化です! 使いたくなりませんか?w では,実際にコードへ適用していきます.

メモ化でフィボナッチ数を求める

ポイントは$memoListという配列に計算結果を保存しておき,余計な計算を減らすことです. n 番目から計算するトップダウンなイメージです. コードにするとこんな感じです.

<?php
fscanf(STDIN, "%d", $n);
echo fib($n) . "\n";

$memoList;

function fib($n) {
    global $memoList;
    if (isset($memoList[$n])) return $memoList[$n]; // 保存済みならその結果を使う
    if ($n == 0) return 0;
    if ($n == 1) return 1;
    $memoList[$n] = fib($n - 1) + fib($n - 2); // 新たに計算した結果を保存する
    return fib($n - 1) + fib($n - 2);
}

動的計画法でフィボナッチ数を求める

ポイントは$dpという配列で,計算結果を保存するという点ではメモ化と一緒です. ただ,こちらはメモ化とは逆向きに,0番目から計算するボトムアップなイメージです. だから,関数は一度呼ぶだけです.

<?php
fscanf(STDIN, "%d", $n);
echo fib($n) . "\n";

function fib($n) {
    $dp[0] = 0;
    $dp[1] = 1;

    for ($i = 2; $i <= $n; $i++) { // ひたすら計算し,結果を配列に保存していく
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }

    return $dp[$n];
}

使い分け

• 計算の重複が起きる心配がないか、気にならないほど頻度が低い場 合は、素朴な再帰呼び出しで十分。

• 計算に必要な値がとびとびの場合は、メモ化が計算時間を節約でき て良い。

• 計算に必要な値がぎちぎちの場合は、動的計画法が計算時間を節約 できて良い。

「アルゴリズム」資料 18. 動的計画法とメモ化より) とのことです.

参考文献

動的計画法(京大 マイコンクラブ)

プログラミングコンテストでの動的計画法( Takuya Akibaさん)