動的計画法 (dynamic programming) †最適化手法のメタ解法の一つ.隠れMarkovモデルで状態の遷移を推定するViterbiアルゴリズムや,グラフの最短パスを求めるDijkstra法などが該当する. 最適部分構造:問題全体を部分問題に分割でき,問題全体の最適化にその部分問題の最適化が利用できる. 動的計画法はこの最適部分構造を持つ問題に適用できる. 最も小さな部分問題を最適化し,その解を使って再帰的により大きな部分問題を解く.
関連項目 †リンク集 †関連文献 †
|