動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える

0. この記事の要点

• 動的計画法は「問題を部分問題に分ける」技法ではありません。分割統治もそれをします。本質は、分けた部分問題が重複して現れるときに、答えを表に記録して一度しか解かないことです。
• 部分問題の依存関係が有向非巡回グラフ（DAG）になっていれば、位相順に解けます。全体の計算時間は「部分問題の個数 × 1 つあたりの遷移コスト」で見積もれます（定理 3.2）。この 1 本の定理で、以下のすべての計算量が出ます。
• フィボナッチ数を定義どおりの再帰で計算すると、関数呼び出しの総数はちょうど $2F_{n+1} - 1$ 回、すなわち $\Theta(\varphi^n)$ 回です。表を使えば $O(n)$ 回の加算で済みます。
• 動的計画法が使えるかどうかは最適部分構造が成り立つかで決まります。成り立たない例（最長単純道）を見れば、どこで壊れるのかがはっきりします。
• 0-1 ナップサック問題は $O(nW)$ の表計算で最適値と最適解の両方が求まります。ただしこれは入力のビット長に対する多項式時間ではありません（擬多項式時間）。この差は本質的で、ナップサック問題自体は NP 困難です。

1. 動機：同じ部分問題を何度も解いていないか

再帰は、問題を小さな同種の問題に分解する強力な道具です。マージソートは長さ $n$ の列を長さ $\lfloor n/2 \rfloor$ と $\lceil n/2 \rceil$ の 2 つに分け、それぞれを整列してから併合しました（ソートアルゴリズム、定理 4.2［ソートアルゴリズム］）。ここで見落としやすい前提があります。分割された 2 つの部分列は互いに交わらない、つまり左半分を整列する仕事と右半分を整列する仕事はまったく別物だ、ということです。

ところが、同じ形で書いた再帰が破滅的に遅くなることがあります。フィボナッチ数 $F_0 = 0$、$F_1 = 1$、$F_n = F_{n-1} + F_{n-2}$ $(n \ge 2)$ の定義をそのまま Python に写してみます。

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

このコードは正しく動きます。しかし fib_naive(40) は普通の計算機で数秒かかり、fib_naive(50) は分単位になります。$n$ を 1 増やすごとに時間がおよそ 1.6 倍、10 増やすと約 123 倍です。理由は、呼び出しの木を描けばすぐに見えます。

flowchart TD
a5["F(5)"] --> a4["F(4)"]
a5 --> b3["F(3)"]
a4 --> a3["F(3)"]
a4 --> b2["F(2)"]
b3 --> c2["F(2)"]
b3 --> d1["F(1)"]
a3 --> e2["F(2)"]
a3 --> f1["F(1)"]
b2 --> g1["F(1)"]
b2 --> h0["F(0)"]
c2 --> i1["F(1)"]
c2 --> j0["F(0)"]
e2 --> k1["F(1)"]
e2 --> l0["F(0)"]

fib_naive(5) の呼び出し木。F(3) は 2 回、F(2) は 3 回、F(1) は 5 回、それぞれ独立に計算されている

$F(3)$ を計算する部分木が、まるごと 2 回現れています。$F(2)$ は 3 回です。$n$ を大きくすればこの重複は指数的に膨れ上がります。一方で、私たちが本当に知る必要のある値は $F_0, F_1, \ldots, F_n$ の $n+1$ 個しかありません。一度計算した答えを書き留めて使い回す——これが動的計画法のすべてです。

アイデア自体は素朴です。しかしそれだけでは、次の 3 つの問いに答えられません。

1. 使い回してよいのはなぜか。部分問題の答えは、それを呼び出した文脈に依存しないのか。
2. どんな問題で使えるのか。使えない問題との境目はどこか。
3. どれだけ速くなるのか。速さは何で決まるのか。

この記事はこの 3 つに順に答えます。なお「動的計画法（dynamic programming）」という名前は 1950 年代に Richard Bellman が付けたものです。彼は自伝のなかで、当時の国防長官が「研究」という語を嫌ったため、数学的な色を消しつつ印象のよい語を選んだ、という趣旨のことを書いています。名前から意味を読み取ろうとしても徒労で、ここでの programming は「表を作る計画」ほどの意味であり、プログラミング言語とは関係ありません。

ここから先は Pro プランの内容です。

この章の続き（定義・定理・証明・例・演習）をすべて読むには Pro プランにご登録ください。無料の章は最後まで読めます。

プランを見る ログイン