動的計画法 (dynamic programming)

最適化手法のメタ解法の一つ.隠れMarkovモデルで状態の遷移を推定するViterbiアルゴリズムや,グラフの最短パスを求めるDijkstra法などが該当する.

最適部分構造:問題全体を部分問題に分割でき,問題全体の最適化にその部分問題の最適化が利用できる.

動的計画法はこの最適部分構造を持つ問題に適用できる. 最も小さな部分問題を最適化し,その解を使って再帰的により大きな部分問題を解く.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:12:41