動的計画法 その１

イントロダクション

動的計画法（Dynamic Programing：以下「DP」と記述）は，ある種の最適化問題を効率的に（少ない計算時間で）解くための方法である。

アルゴリズム関連の参考書籍では，次のように説明される。

　k 個の要素だけをとったときの最適解が表の形で与えられているとする。これに要素を1個付け加えたときに，最適解がどのように変わるかをこの表をもとに計算し，表を書き換える。
　この操作を続けて，n 個の要素すべてを使った最適解が求まればよい。表の添え字としては，問題の性格を規定するパラメータのうち要素の個数以外のものを選ぶ。

アルゴリズムとデータ構造 (岩波講座 ソフトウェア科学) より

問題を細かく小さい問題に分けて，それぞれにベストの解答を見つけよ。それらの回答を張り合わせて，全体の問題の回答を導け。

プログラマのための論理パズル 難題を突破する論理思考トレーニング より

DPをインターネットで検索して得られる情報も概ねこのような説明であると思う。これらの説明と，いくつかの例題を見ることでDPのやりたいこと（方法）を（ある程度）理解することはできるであろう

しかしながら，実際に問題の解法としてDPを適用しようとした場合，「何を“小さい問題”として定義するのか？」，「何を“（k 個の）要素”とするのか？」を考え付くことが難しく（そもそもDPで解くべき問題であるかも見抜けないことも多い），解を得るまでに至らないのである。

ここでは，DPを数学面から見直し*1，各種例題を数学的に捉えなおすことでDPの理解を深める。「DPで考える」ための考え方を習得することを目指す。

DPの数学表現

動的計画法は「離散値を取る変数で表される関数の最大値または最小値（最適値）」を効率的に求める方法である。

変数 x_i が 離散値{ a₁,a₂,・・・,a_n }をとるとき，

の最大値，最小値を求める問題を考える。

一般的には，この関数の最適値を求めるには x_i の全ての組み合わせについて関数の評価を行わなければならない。しかしながら，関数 f が次のような形で表されるとき，全件評価を行わずに最適値を求める方法が存在する。

ここでは，この関数の最大値を求めることを考える。

x₁ に着目すると， x₁ は f₁(x₁)，h₁(x₁,x₂) にのみに関係する。変数 x₂ に対して，f₁(x₁)+h₁(x₁,x₂)の最大値を値とする関数f₂(x₂)を考える。

式(1)が最大値をとるとき，次式

も最大値をとり，式(1)の最大値と同じ値となる。

続いて式(2)について同様に，変数x₃に対して，f₂(x₂)+h₂(x₂,x₃)の最大値を値とする関数f₃(x₃)を考える。

式(2)が最大値をとるとき，次式

も最大値をとり，同じ値となる。

以下，同様の式の置きかけを続けることで，最終的には関数f_n(x_n)を次のように導くことができる。

f_n(x_n)の最大値は式(1)，(2)，(3)の最大値と同じである。 このようにして部分ごとの最大値の計算を積み重ねることで，最終的に式(1)の最大値を求めることができる。

上述の説明は“最大値／max”を“最小値／min”に言い換えても成立する。（関数値の最小値を求めるときにも使える）

DPの計算手順は次の通りとなる。

関数f₁(x₁)，h_i(x_i,x_i+1) (i=1,n-1)が与えられたとき
1. f₂ = max(f₁(x₁)+h₁(x₁,x₂))を求める。
　　　　x₁, x₂は離散値なので，f₂(x₂)も離散値となる。==> 配列へ保存

f₂(x₂)の値を用いて，
2. f₃ = max(f₂(x₂)+h₂(x₂,x₃))を求める。

以下，f₄，f₅と求め，最終的には f_nを求める。

f_n の最大値が式(1)の最大値となる。

DPの適用

変数x_i, x_i+1を“問題”で定義される何らかの状態を表す値として捉えると，h_i(x_i,x_i+1) は現在の状態 x_i から次の状態 x_i+1 へ遷移すると得られる値（得点）として考えられる。

DPは，この状態を進めることで得られる値(得点)の和について，その最適値を求める問題に適用することができる。

最適値に対応する各変数の値

式(1)が最適値をとるときの変数 x_i の値が必要な場合には，次のように求める。

変数 x_i+1 の関数，

を求めるときに変数 x_i+1 の各値に対して，最大値を与える x_i を記録しておく。これを m_i(x_i+1) とする。

f_n(x_n) の最大値（p_nとする）が求まると，m_n-1(p_n) から x_n-1 の値が求まる。これをp_n-1とする。 以下，同様にm_n-2(p_n-1) から p_n-2 を求め，p_n-3，p_n-4,･･･を順番に求める。p_i が x_i の値である。

例題１

TopCoder Tutorialから
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

このTutorialのIntermediateの問題では，次の例題が挙がっている。

N×Mの表の各マスに，それぞれいくつかのリンゴが置かれている。左上のマスからスタートして，右もしくは下へ進み，通ったマスのリンゴを集めながら右下のマスまで行く。リンゴは最大で何個集められるか？

マスを進む各ステップ（1ステップで1マス移動）の状態（状態＝どのマスの上にいるか）を x₀, x₁, ･･･, x_N+M-2 とする。i ステップ目にいるマス x_i は，左上のマスを(0,0)，右下のマスを(N-1, M-1)とする座標系を考えたとき，(p, q) ：p+q=i のマスとなる。 x₀は左上のマスであり，x_N-1+M-1 は右下のマスである。

この最適化(最大値)問題は，x_i における獲得リンゴ数を f(x_i) とすれば，

を最大化する問題となる。

ここで，x_i と x_i+1 の間には進む方向に関するルールからの依存関係があることに注意が必要である。
x_i 上のマス(p, q)は，x_i-1 においてマス (p-1, q)，もしくは(p, q-1) のときのみ移動可能である。

※x_i の位置に関わらず x_i+1 上の任意のマスに移動できるのであれば，各ステップでf(x_i) の最大値のマスを選択していけば良いこととなる（貪欲法となる）

ここで次の関数h(x_i,x_i+1)を考える。

ここでN/Aは評価されない値である。プログラミングする場合は，この関数値は評価対象から外すこと（行けない経路は評価しない）となる。
進む方向の依存関係を考慮した獲得リンゴ数の式は次のように書くことができる。

獲得リンゴ数を最大化するには，この式を最大化すればよい。

この式は前述の式(1)と同等の形式であり，DPを用いて最大値を計算することができる。f₁(x₁)を次のように定義すると，

前述の式の最大値は，次式の最大値と一致する。

これを繰り返し f_N+M-2(x_N+M-2) を求める。この値が求めるべき最大値となる。

例題２

有向グラフの経路最適化問題を考える。

SからスタートしてEまで進む経路を考える。進む方向は左から右へのみ進めることとし，i ステップ目にいる頂点を x_i で表す。各枝には得点が与えられて，SからEの経路で枝を通過すると得点を獲得する。このとき，得点を最大化する経路を求める。

各枝は２頂点 x_i と x_i+1 を結ぶものであるので，枝の得点は次のように表すことができる。

この値は，iステップ目の頂点 x_i から i+1ステップ目の頂点 x_i+1 を結ぶ枝の得点を示す。
SからEまでの経路で得られる得点は次のように書き表せる。

この式の最大値は，これまでの説明通りにDPで解くことができる。式(1)に対応する初期値f(x₀) は0であると考えればよい。

ここで，グラフの枝ではなく頂点に得点が与えられているケースを考える。この場合は，各ステップ i において，頂点 x_i のうち最大値をとる頂点を訪問すれば良いことは自明である。このケースは各ステップで最大となるものを選択していく“貪欲法”となる。

動的計画法は，あるステップの値が1つ前のステップの状態に依存するよう定義されるときに，それらの値の組み合わせ（これまでの例では加算）を最適化するときに用いることができると捉えることができる。

---

*1参考文献：これなら分かる最適化数学―基礎原理から計算手法まで