Dynamic Programming...ケーキのお話

Dynamic programmingをならったのでメモ。

基本的にはcontrol theoryと一緒で、最適化問題に時間軸を加えた時の解の求め方の一つです。

特徴としては、時間軸の最後からその時間に置ける最適解を関数として求め、それを一つ前の時間軸に代入してまた関数として解を求めるという作業を初期まで繰り返す事です。

結果的に全ての時点の解を関数として含んだ式が出来上がるので、そいつを最大化して解けば答えが出ると言うもの。

授業で習った例が珍しく素晴らしかったので画像として乗っけておきます。

ある人がケーキを２日で食べようと考えている。
効用を最大化出来る様な摂取計画は？という問題。

d(t)^(-1/2)　がその人の効用関数。

d(t) :day tに置けるケーキの消費量
s(t) :day tに置けるケーキの残量
s(t+1) = s(t) - d(t) :明日のケーキ残量は、今日の残量から消費量を差し引いたもの

s(1) = 1 初日のケーキ量
T :ケーキを食べ尽くす日をTとする
s(T+1) = 0 : 食べ尽くした次の日の残量は当然0
s(3) = 0 ２日で食べ尽くそうと考えているので当然３日目の残量は0

s(3) = s(2) - d(2) =0
d(2) = s(2)

とまぁこんな条件があると下の様に解けます。






実はプログラミングを使って幾らかこういった問題を取り扱った事はあったのだけれども、ちゃんと数式で習うのは始めてだったので結構楽しかったです。