動的計画法の考え方
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/03 14:35 UTC 版)
「ベルマン方程式」の記事における「動的計画法の考え方」の解説
ベルマン方程式を理解するには、いくつかの背景となる概念を理解しなくてはならない。 第一に、最適化問題は何らかの目標を持つ。具体例を挙げれば、移動時間を最短にする、コストを最小に抑える、利益を最大化する、効用を最大化する、などである。これらの目標を数学の関数で表現したものを 目的関数 (objective function) と呼ぶ。 動的計画法は複数段階にわたる計画問題を、各時点の簡単な手順へと分解する。そのため、ある時点でなされた決定がそれ以降どのように影響を及ぼすか正しく記述しなくてはならない。正しい判断を下すために必要な現在の状況を示す情報を 状態 (state) と呼ぶ。例えば、人がある時点で何をどれだけ消費するか決めるには、（何よりもまず）現在の富（資産額）を知らなくてはならない。 そのゆえ、富は、経済活動を行う人が持つ状態変数（英語版）の一つと考えられる。言うまでもなく、このような状態変数は他にも存在する。 任意の時点で選ぶことのできる変数を通常 制御変数（英語版） (control variables) と呼ぶ。 例えば、人々は与えられた富のもとで、どれだけ消費すべきか判断する。制御変数を選ぶことは、次の状態を選択することでもある。ただし、一般に次の状態は制御変数だけではなく他の要因によっても影響を受ける。具体例で示そう。最も単純には、今日の富（状態）と消費（制御変数）によって明日の富（次の状態）が決まる。だが、多くの場合、明日の富には別の要因（例：予期せぬボーナス、天災など）も影響するであろう。 動的計画法は、与えられたどんな状態に対しても、適切な制御の指針を与えるような最適な計画を記述する。一例として、消費 c {\displaystyle c} が富 W {\displaystyle W} だけに依存する場合には、我々は、財産の関数として消費を決定するような制御則 c ( W ) {\displaystyle c(W)} を探索することになる。 状態に基づいて制御変数を決定するこのような関数を、方策関数 (policy function)（Bellman、1957、Ch. III.2を参照)と呼ぶ。 最後に、最適な決定ルール（制御則）はその定義から、実現可能な最良の目的関数の値をもたらすものである。例えば、ある人が与えられた富のもと、満足度を最大化するための消費活動を選ぶとしよう。ただし、満足度 H {\displaystyle H} は効用関数(utility function)のような目的関数で表現できるとする。この時、各時刻の財産はそれで実現可能な満足度の最大値 H ( W ) {\displaystyle H(W)} と関係付けることができる。ある状態で実現しうる最良の目的関数の値を示す関数を 価値関数 (value function) と呼ぶ。 リチャード・ベルマンは、離散時間形式の動的最適化問題が、ある時刻の価値関数とその次の時刻の価値関数の間の関係式を書き下すことによって、再帰的な、後ろ向き帰納法（英語版）(backward induction)と呼ばれる逐次的な形式で表現できることを示した。上述の時間的に隣接する二つの価値関数の関係式がベルマン方程式である。このアプローチでは、終端時刻における最適な方策は、その時刻の状態変数の関数としてすでに決まっており、結果として得られる目的関数の最適値は状態変数で与えられる。次に、最後から一つ前の時刻の最適化を考えると、決定に際して、その状態変数に付随する最適な方策のもとで、その時刻の目的関数と未来の目的関数の和を最大化する。このアルゴリズムは、再帰的に時間を遡る形で進み、初期時刻において、初期状態の関数としての決定ルールが初期時刻に固有の目的関数と2番目のステップの価値関数（第2ステップ以降すべての未来の価値）の和の最適化計算によって得られるまで繰り返される。ゆえに、各ステップにおける決定は、それ以降の未来すべての判断が最適である事を前提として行われるのである。
※この「動的計画法の考え方」の解説は、「ベルマン方程式」の解説の一部です。
「動的計画法の考え方」を含む「ベルマン方程式」の記事については、「ベルマン方程式」の概要を参照ください。
- 動的計画法の考え方のページへのリンク
