動的計画法とは (ドウテキケイカクホウとは) [単語記事]

動的計画法とは、アルゴリズムの形の一つである。

概要

具体的な例で考えてみよう。東京から大阪まで陸路で移動する最短ルートを検索せよ、といった問題があるとする。

最も単純な回答は、考えられるルートの組み合わせを全部並べて、その中で一番短いものを探す方法だが、これはどう考えても効率が悪い。

例えば、名古屋を経由するルートに注目すると、「東京→名古屋の全パターン」×「名古屋 → 大阪の全パターン」の組み合わせを考える必要があるわけだが、その大部分は99%同じルートでどこか100 メートルだけ違う道みたいなものが延々並ぶので、一々すべて計算するのは時間の無駄なわけである。

ところで、東京→名古屋の最短経路、名古屋→大阪の最短経路がそれぞれ分かっていると仮定すると、当たり前だが

　東京→名古屋→大阪の最短経路　＝　東京→名古屋の最短経路　＋　名古屋→大阪の最短経路

になる。東京→名古屋間でどのようなルートを通ろうと、名古屋→大阪間の選択には影響しないので、この分割ができれば無駄な組み合わせを大幅にカットすることができる。

この考え方は当然ながらもっと細かく適用できる。東京→名古屋の最短経路は長野経由か静岡経由のどちらかの最短経路を考えればいいだろうということになるし、どちらのルートも手近な首都高インターまでは共通というような感じになる。あるいは名古屋を経由しないで中央道から北陸に抜けたらどうなるかという可能性について考慮するなら、長野のジャンクションまでは使いまわせるだろう。

これをパターンとして抽出すると、次のように説明できる。

ある部分の(最適)解 = それを構成するパーツの(最適)解の和で説明できる
複数箇所で共通のパーツは一度計算すれば他で使いまわせる

このようなパターンで問題を分割し、必要な計算量を最適化する方法を動的計画法という。

例

n個の中からr個選ぶ組み合わせは何通り？(パスカルの三角形)

高校数学に出てくる_nC_r。これはn個の中からr個取り出す組み合わせが何通りあるかを表している。例えば、{A,B,C,D,E}の中から3つを選ぶ組み合わせは、{A,B,C}, {A,B,D}, {A,B,E}, {A,C,D}, ..., {C,D,E}の10通りである。単純に_nC_rを求めるには教科書に載っていれば公式を使えばよい。しかし、予め必要な範囲を事前に計算して配列に入れておくことでプログラムを高速化することができる場合がある。このようなときに使われるのがパスカルの三角形である。

パスカルの三角形では以下の公式を使う。

_nC_r=_n-1C_r-1+_n-1C_r

なんとなく漸化式っぽく見えると思う。これを使って動的計画法を説明していく。動的計画法では表に数値を書き込んでいくように計算を行う。まずは表を用意する。続いて一番最初の答えを書き込む。ここでは₀C₀=1を書き込む。(0個の中から0個取り出す組み合わせは1通りである。)

n↓ r→	0	1	2	3	4
0	1
1
2
3
4

続いて公式を使って、一つ前の計算結果から次の計算結果を計算できるところを順に埋めていく。ここでは2行目のn=1の部分を埋めていく。公式は_nC_r=_n-1C_r-1+_n-1C_rとなっているので、_nC_rを計算するには_n-1C_r-1と_n-1C_rを足せば良い。これは、計算しようとしているマス目の左上と上のマス目の値を足せばそのマス目の値が計算できるということである。

n↓ r→	0	1	2	3	4
0	1
1	1	1
2
3
4

ここで、空欄となっているところや、表の外側に出た部分は0として扱っている。同様に次の行も埋めていく。

n↓ r→	0	1	2	3	4
0	1
1	1	1
2	1	2	1
3
4

同様に最後まで埋めていくとパスカルの三角形が完成する。

n↓ r→	0	1	2	3	4
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1

これらをC++風に書くと以下のようになる。

int main() {
        static const int N = 30;
        int C[N][N];
        memset(C, 0, sizeof(C));
        C[0][0] = 1;
        for (int n = 1; n < N; ++n) {
                C[n][0] = C[n - 1][0];
                for (int r = 1; r < N; ++r) {
                        C[n][r] = C[n - 1][r - 1] + C[n - 1][r];
                }
        }
}