システムの最適化

－ ５．動的計画法（ DP: Dynamic Programming ） －

1. ５．１ 最適性の原理
2. ５．２ 動的計画法の適用例（資源配分問題）

５．１ 最適性の原理

　　「決定の全系列にわたって最適化を行うためには，初期の状態と最初の決定がどんなものであっても，残りの決定は最初の決定から生じた状態に関して最適な政策を構成していなければならない」ということを，最適性の原理と呼びます．別の表現をすれば，「最適経路中の部分経路もまた最適経路になっている」ということを意味しています．

　　動的計画法（ DP: Dynamic Programming ）は，この原理を利用して最適化問題を解きます．基本的に，動的システムの最適化に利用される方法ですが，問題を，多段決定問題，つまり，各段における決定の系列を求めるような問題に変換できれば，動的計画法によって解くことが可能です．例えば，

目的関数： f(x) = f₁(x₁) + ･･･ + f_n(x_n)

制約条件： x₁ + ･･･ + x_n = a，　　x_i ≧ 0

のような問題は，最適性の原理に従って，

φ_i(a_i) = max [f_i(x_i) + φ_i-1(a_i - x_i)]　　　i = 2, ･･･, n　　　0 ≦ x_i ≦ a

φ₁(a₁) = max [f₁(x₁)] = f₁(a₁)　　　0 ≦ x₁ ≦ a

のような再帰方程式に変換し，動的計画法によって解くことが可能です．上の式では，1 ステップ目から解いていく表現がしてありますが，最終段から解く方法もあります．詳細については，次節で述べる例によって説明します．

５．２ 動的計画法の適用例（資源配分問題）

　　プログラム例（ C/C++ 版，Java 版，JavaScript 版）では，以下に示す資源配分問題以外に，0-1 ナップザック問題及びグラフ上の最短経路問題を扱っています．さらに，JavaScript 版では，画面上で実行することが可能です．なお，PHP，Ruby，Python によるプログラム例に関しては「 PHP と C/C++ 」，「 Ruby と C/C++ 」，「 Python と C/C++ 」，また，C#，VB によるプログラム例に関しては，「 プログラミング言語の落とし穴」第 9 章の「最適化（動的計画法）」をご覧ください．ただし，C#，VB においては，資源配分問題だけを扱っており，プログラムの記述方法も多少異なります．

［例］ある会社に 4 単位の資金があり，3 種類の投資先が候補にあるとします．資金は単位でしか配分できないものとしたとき，利益

f(x) = f₁(x₁) + f₂(x₂) + f₃(x₃)

を最大にする投資先をどのようにしたらよいのでしょうか．ただし，3 種類の投資先に対する利益関数は次の通りとします．分枝限定法の適用例において述べた 0-1 ナップザック問題も，問題の表現方法を変えることによって，同様の扱いが可能です．詳細については，プログラム例（ C/C++ 版，Java 版，JavaScript 版）を参照して下さい．

投資額： x	1	2	3	4
1 番目の投資先へ投資したときの利益： f1(x)	8	18	22	24
2 番目の投資先へ投資したときの利益： f2(x)	3	6	9	12
3 番目の投資先へ投資したときの利益： f3(x)	6	7	8	10

　　まず，再帰方程式の下の式によって，1 段目における利益（ 1 番目の投資先へ投資したときの利益） φ を計算します．投資額は 4 単位ですから，x₁ の値として 5 つの場合がありますので，以下のようになります．

φ₁(0) = max [f₁(x₁)] = f₁(0) = 0

φ₁(1) = max [f₁(x₁)] = f₁(1) = 8

φ₁(2) = max [f₁(x₁)] = f₁(2) = 18

φ₁(3) = max [f₁(x₁)] = f₁(3) = 22

φ₁(4) = max [f₁(x₁)] = f₁(4) = 24

　　次に，再帰方程式の上の式に従って，2 段目（ 1 番目と 2 番目の投資先へ投資したときの利益）の計算をします．この計算は多少分かりにくいかと思いますので詳細に説明します．この場合も，1 番目の投資先の場合と同様，5 つの場合が考えられます．まず，投資合計が 0 の場合です．これは，1 番目，及び，2 番目の投資先に全く投資しない場合だけであり，下に記した φ₂(0) に相当します．

　　次に，投資合計が 1 になる場合を考えてみます．この場合は，1 番目の投資先に 1 単位，2 番目の投資先に 0 単位投資する場合と，1 番目の投資先に 0 単位，2 番目の投資先に 1 単位投資する場合とが考えられます．再帰方程式の上の式は，「それらの内，最大のものを選択する」ということを意味しており，具体的には，下に記した φ₂(1) に相当し，1 番目の投資先に 1 単位，2 番目の投資先に 0 単位投資する方法が最大になります（利益は 8 ）．同様に，投資合計が 2，3，及び，4 単位になる場合に対してその最大となる投資額の組合せを計算したのが，φ₂(2)，φ₂(3)，及び，φ₂(4) です．

φ₂(0) = max [f₂(x₂) + φ₁(0 - x₂)] = 0

φ₂(1) = max [f₂(x₂) + φ₁(1 - x₂)]

　　　 = max {f₂(0) + φ₁(1), f₂(1) + φ₁(0)}

　　　 = max {0 + 8, 3 + 0} = 8

φ₂(2) = max [f₂(x₂) + φ₁(2 - x₂)]

　　　 = max {f₂(0) + φ₁(2), f₂(1) + φ₁(1), f₂(2) + φ₁(0)}

　　　 = max {0 + 18, 3 + 8, 6 + 0} = 18

φ₂(3) = max [f₂(x₂) + φ₁(3 - x₂)]

　　　 = max {f₂(0) + φ₁(3), f₂(1) + φ₁(2), f₂(2) + φ₁(1), f₂(3) + φ₁(0)}

　　　 = max {0 + 22, 3 + 18, 6 + 8, 9 + 0} = 22

φ₂(4) = max [f₂(x₂) + φ₁(4 - x₂)]

　　　 = max {f₂(0) + φ₁(4), f₂(1) + φ₁(3), f₂(2) + φ₁(2), f₂(3) + φ₁(1), f₂(4) + φ₁(0)}

　　　 = max {0 + 24, 3 + 22, 6 + 18, 9 + 8, 12 + 0} = 25

　　最後に，最終段の計算を行います．この計算も，基本的には，2 段目の計算と同じです．最終段では，3 つの投資先にどのような配分で投資すべきかを決定するわけですが，下に示した式からも明らかなように，1 番目の投資先に対する項目（ φ₁ ）が陽に現れていません．前段で計算した φ₂ だけとの組合せで計算を行っています．これが，最適性の原理の力です．

φ₃(0) = max [f₃(x₃) + φ₂(0 - x₃)] = 0

φ₃(1) = max [f₃(x₃) + φ₂(1 - x₃)]

　　　 = max {f₃(0) + φ₂(1), f₃(1) + φ₂(0)}

　　　 = max {0 + 8, 6 + 0} = 8

φ₃(2) = max [f₃(x₃) + φ₂(2 - x₃)]

　　　 = max {f₃(0) + φ₂(2), f₃(1) + φ₂(1), f₃(2) + φ₂(0)}

　　　 = max {0 + 18, 6 + 8, 7 + 0} = 18

φ₃(3) = max [f₃(x₃) + φ₂(3 - x₃)]

　　　 = max {f₃(0) + φ₂(3), f₃(1) + φ₂(2), f₃(2) + φ₂(1), f₃(3) + φ₂(0)}

　　　 = max {0 + 22, 6 + 18, 7 + 8, 8 + 0} = 24

φ₃(4) = max [f₃(x₃) + φ₂(4 - x₃)]

　　　 = max {f₃(0) + φ₂(4), f₃(1) + φ₂(3), f₃(2) + φ₂(2), f₃(3) + φ₂(1), f₃(4) + φ₂(0)}

　　　 = max {0 + 25, 6 + 22, 7 + 18, 8 + 8, 10 + 0} = 28

　　最終段の結果より，最大値は 28 であることが分かります（黄色の部分）．その最大値を与えるのは，緑色の部分から，x₃ = 1 （ 3 番目の投資先に 1 単位投資する），かつ，φ₂(3) となります．

　　次に，2 段目の φ₂(3) の箇所を見ると，青色の部分から，x₂ = 0 （ 2 番目の投資先には投資しない），かつ，φ₁(3) で最大になっています．したがって，1 段目の φ₁(3) より，x₁ = 3 （ 1 番目の投資先に 3 単位投資する）となり，これが最終的な解になります．

　　今までの計算過程を図示すると，右のようになります．図の左から，1 段目，2 段目，及び，3 段目に相当しています．各点は，その段における累積投資単位を表しており，下から，0，1，2，3，4 に相当します．また，点の箇所に付けられた数値は，利益（関数値）を表しています．

　　例えば，2 段目の一番上の点は，1 番目，及び，2 番目の投資先に，併せて 4 単位投資すると，最大 25 単位の利益が得られることを表しています．1 番目，及び，2 番目の投資先に，併せて 4 単位投資する方法はいくつかありますが，1 段目の 上から 2 番目の点と直線で結ばれていますので，1 番目の投資先に 3 単位，2 番目の投資先に 1 単位投資したときの結果であることが分かります．これが，2 段目における φ₂(4) の計算に相当しています．なお，最適解は，太線で表現してあります．

　　次に，同じ問題を，最終段から計算してみます．まず，再帰方程式の下の式によって，3 段目における利益φを計算します．

φ₃(0) = max [f₃(x₃)] = f₃(0) = 0

φ₃(1) = max [f₃(x₃)] = f₃(1) = 6

φ₃(2) = max [f₃(x₃)] = f₃(2) = 7

φ₃(3) = max [f₃(x₃)] = f₃(3) = 8

φ₃(4) = max [f₃(x₃)] = f₃(4) = 10

　　次に，再帰方程式の上の式に従って，2 段目の計算をします．

φ₂(0) = max [f₂(x₂) + φ₃(0 - x₂)] = 0

φ₂(1) = max [f₂(x₂) + φ₃(1 - x₂)]

　　　 = max {f₂(0) + φ₃(1), f₂(1) + φ₃(0)}

　　　 = max {0 + 6, 3 + 0} = 6

φ₂(2) = max [f₂(x₂) + φ₃(2 - x₂)]

　　　 = max {f₂(0) + φ₃(2), f₂(1) + φ₃(1), f₂(2) + φ₃(0)}

　　　 = max {0 + 7, 3 + 6, 6 + 0} = 9

φ₂(3) = max [f₂(x₂) + φ₃(3 - x₂)]

　　　 = max {f₂(0) + φ₃(3), f₂(1) + φ₃(2), f₂(2) + φ₃(1), f₂(3) + φ₃(0)}

　　　 = max {0 + 8, 3 + 7, 6 + 6, 9 + 0} = 12

φ₂(4) = max [f₂(x₂) + φ₃(4 - x₂)]

　　　 = max {f₂(0) + φ₃(4), f₂(1) + φ₃(3), f₂(2) + φ₃(2), f₂(3) + φ₃(1), f₂(4) + φ₃(0)}

　　　 = max {0 + 10, 3 + 8, 6 + 7, 9 + 6, 12 + 0} = 15

　　最後に，1 段目の計算を行います．

φ₁(0) = max [f₁(x₁) + φ₂(0 - x₁)] = 0

φ₁(1) = max [f₁(x₁) + φ₂(1 - x₁)]

　　　 = max {f₁(0) + φ₂(1), f₁(1) + φ₂(0)}

　　　 = max {0 + 6, 8 + 0} = 8

φ₁(2) = max [f₁(x₁) + φ₂(2 - x₁)]

　　　 = max {f₁(0) + φ₂(2), f₁(1) + φ₂(1), f₁(2) + φ₂(0)}

　　　 = max {0 + 9, 8 + 6, 18 + 0} = 18

φ₁(3) = max [f₁(x₁) + φ₂(3 - x₁)]

　　　 = max {f₁(0) + φ₂(3), f₁(1) + φ₂(2), f₁(2) + φ₂(1), f₁(3) + φ₂(0)}

　　　 = max {0 + 12, 8 + 9, 18 + 6, 22 + 0} = 24

φ₁(4) = max [f₁(x₁) + φ₂(4 - x₁)]

　　　 = max {f₁(0) + φ₂(4), f₁(1) + φ₂(3), f₁(2) + φ₂(2), f₁(3) + φ₂(1), f₁(4) + φ₂(0)}

　　　 = max {0 + 15, 8 + 12, 18 + 9, 22 + 6, 24 + 0} = 28

　　結局，同じ結果が得られます．