「動的計画法」の版間の差分

動的計画法は対象となる最適化問題を複数の部分問題に分割し、求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法である。この考え方は計算機科学[[最適化問題]]における[[最適性原理]]に基づいている。最適性原理は「最適解を持つ問題の部分問題の最適解は元の最適解の部分解である」というものであり、直感的な例としては『A地点からB地点への最短経路上にC地点とD地点がある場合、C地点からD地点への最短経路は、A地点からB地点への最短経路の一部である』というものがある。