・DPの復習

関数 f(x1,x2,...,xN) の最大値を求めたいとする。

もし f(x1,x2,...,xN) = Σ[i=1,N-1] fi(xi,x[i+1]) の形になっていれば
全てのx1,x2,...,xN の組み合わせを探索しなくてもよい。

説明を簡単化するため N=3の場合を考える。
目的関数は f(x1,x2,x3) = f1(x1,x2)+f2(x2,x3) の3変数関数である。

もしもx1,x2,x3各々の取りうる値が100パターンであれば
これらの全組み合わせのパターン数は100^3=1000000である。
しかし、この全てを探索する必要はない

第1項目 f1(x1,x2)に対して x2をある値に固定し、x1を探索して最大化したものを V1(x2)とする。(ここまでで探索回数 100)
つまり V1(x2) = max[x1] f1(x1,x2)
これを全ての x2 に対して計算する。(ここまでで探索回数 10000)

次に V1(x2)+f2(x2,x3) に対して x3をある値に固定し,x2を探索して最大化したものを V2(x3)とする。(ここまでで探索回数10000+100)
つまり V2(x3) = max[x2] V1(x2)+f2(x2,x3)
これを全ての x3 に対して計算する。(ここまでで探索回数 20000)

最後に V2(x3)が最大となる x3を求めるとこれが f1(x1,x2)+f2(x2,x3)の最大値になっている。 (ここまでで探索回数 20100)

全ての組み合わせを求める方法が 1000000回
後者の方法では 20100回
この比は約 50倍

3変数の場合を考えたが、探索回数の差は変数の個数が多いほど急激に大きくなる。
N変数の場合、全ての組み合わせパターンは 100^N 回
後者の方法では(たぶん) 10000(N-1)+100 回

N=1000 程度の問題は珍しくなく
効率のよい後者の方法では 9990100 回だが
この場合前者の方法では 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 回になる。
ばかあほとろまぬけ。

後者で使った V1(x2),V2(x3) は途中の項までの最大値を
x2やx3の取りうる全て可能性に対して求めている。
これらは部分問題の解を保存している。
計算機に、このような変数を持たせるためには記憶領域が必要である。
一方、前者の方法ではこのような記憶領域を必要としない。
部分問題の解を保存しておく必要がないからである。
後者の方法は記憶領域を犠牲にして計算時間の速さを稼いでいる。
一般に使用する記憶領域と計算時間はトレードオフの関係になると考えられる。

・ここから妄想
DP計算をグラフとして図示することを試みる。(トレリスではない。)
各fiをノードとする。
変数を共有しているノードを結ぶ。
例えば、f2(x2,x3)とf3(x3,x4)はx3を共有しているため、節f2とf3は結ばれる。

するとDP計算の概念図を描く事が出来る。
赤い点線枠が、部分問題の解を求めていくイメージ。


もっと一般的なグラフ構造をもつ数式に対しても
下図のイメージでDP計算が出来るコトが期待出来る。萌える。