T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS 「ダイナミックプログラミング」について

<<   作成日時 : 2016/01/27 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

コンピュータサイエンスとプログラミング入門(Part2)の五回目の授業:"13. Dynamic Programming: Overlapping Subproblems, Optimal Substructure(動的計画法:部分問題重複性、部分構造最適法)"の話題です。(実は四回目の授業もあったのですが直接プログラミングの話題が無かったので省略しました。)

まず、最初の例はフィボナッチ数を求めるプログラムで、\(fib(6)=13\) を出力しています。
画像

これを見ると、\(25\) 回も再帰的呼び出しをしていて、同じ計算をダブって冗長な処理を実行しているように思えます。
\(fib(6)\) から、\(fib(5)\) と \(fib(4)\) を計算することになりますが、分岐した \(fib(5)\) でまた \(fib(4)\) が出てきて、こういう感じで重複していくようですね。
ここで「メモ化」\((Memolization)\) という手法を使ってみましょう。最初の計算のときに値を記録しておき、後で必要なときにはその値を参照するのです。 
画像

同じ結果を得るために、再帰的呼び出し回数は \(25\) → \(11\) に半減しています。
もう少し \(n\) を大きくして \(fib(n)\) と \(fib1(n)\) を比較してみましょう。
画像

2行ずつ出力してありますが、上が \(fib(n)\) で、下が \(fib1(n)\) で、\(n=30\) となると、再帰的呼び出し回数は \(2,692,537:59\) と比べ物にならない位の差が出てきてしまいます。

このメモ化というのが動的計画法と呼ばれる汎用技術の中心にあるものだそうです。
これの最終形というのが、予め結果を表に貯めておいて参照する \(table\; lookup\) です。
(これが \(Dynamic\; Programming\) なの?って感じですが。。)

さて、この \(Dynamic\; Programming\) は @重複する部分問題 A最適な基礎構造 という条件がある場合、しばしば有効なんだろうと思います。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
「ダイナミックプログラミング」について T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる