動的計画法は、最適部分構造と重複部分問題を持つ最適化問題に対する解法を効率化するアルゴリズム技法です。本記事では、その定義を分解し、概念と実装を深く掘り下げます。

最適部分構造と重複部分問題

問題が最適部分構造を持つとは、その最適解がより小さい部分問題の最適解で構成されることを指します。このブログを追っている読者であれば、 例えば以前Haskellのシリーズで紹介したフィボナッチ数列の問題を思い出すかもしれません。最適解である $fib(n)$ は、部分問題の最適解 $fib(n-1)$ および $fib(n-2)$ によって決まります（$fib(n) = fib(n-1) + fib(n-2)$）。 現実世界の最適化問題、例えば最短経路問題なども同様に最適部分構造を持ちます。たとえば、AからCへの最短経路は、通常、AからBへの最短経路とBからCへの最短経路の組み合わせになります。

フィボナッチ数列の問題は重複部分問題も持っています。たとえば、$fib(3)$ を計算するには $fib(2) + fib(1)$ が必要であり、 それをさらに分解すると $fib(1) + fib(0) + fib(1)$ という形になります。このように、$fib(1)$ が複数回計算される必要があり、 従来の再帰法では無駄が生じます。動的計画法は、このような繰り返し計算を効率化するための技法です。

タブレーションとメモ化

動的計画法の主な戦略は、部分問題の解を一度だけ計算し、その結果を保存して再利用することです。これを実現する方法には、 タブレーション（表形式）とメモ化（記憶化） の2つがあります。 メモ化はトップダウンアプローチです。再帰呼び出しの際に部分問題の解を保存し、必要に応じてそれを再利用します。たとえば、$fib(2) + fib(1)$ を計算する際、$fib(1)$ の結果を保存し、 それを利用して $fib(2)$ を計算し、それをさらに利用して $fib(3)$ を計算できます。

// Memorization
int fibMemo(int n, vector<int> &memo) {
    if (n == 0) {
        return 1;
    }
 
    if (memo[n] != -1) {
        return memo[n];
    }
 
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo);
    return memo[n];
};
 
// Tabulation
int fibTable (int n) {
    vector<int> table(n+1);
 
    table[0] = 1;
    table[1] = 1;
 
    for (int i = 2; i <= n; i++) {
        table[i] = table[i-1] + table[i-2];
    }
 
    return table[n];
};

タブレーションはボトムアップアプローチです。基底ケースから始めて表を埋め、元の問題の解が見つかるまで反復的に計算を進めます。 たとえば、$fib(0)$ と $fib(1)$ を計算して保存し、それを利用して $fib(2)$ を計算し、次に $fib(3)$ を計算する、という手順です。 解くべき部分問題が少ない場合、メモ化の方が効率的かもしれません。しかし、タブレーションはその単純さと、スタックオーバーフローのリスクがない点から一般的に好まれます。 また、タブレーションではメモリ使用量を削減できる場合があります。たとえば、フィボナッチ数列の問題では、過去2つの解だけを保存すれば十分であり、 サイズ$n$の配列を用意する必要はありません（クイズQ1）。

動的計画法のフレームワーク

動的計画法を適切に適用するためには、問題を特定し、分析し、正確に適用する必要があります。まず、小さな問題を解いて基底ケースや帰納関係を理解することから始めます。 フィボナッチ数列の問題では、$fib(0)$、$fib(1)$、$fib(2)$、$fib(3)$ を計算すると、基底ケースが $fib(0)$ と $fib(1)$ であり、帰納関係が $fib(n) = fib(n-1) + fib(n-2)$ であることに気づきます。 次に、各反復ステップで保存すべき内容（タブレーションの場合）を決定し、解を構築します。この文脈では、$fib(0)$ は $fib(3)$ 以降の計算には不要であることがわかり、 過去2つの値だけを保存すればよいと判断できます。

ベルマン-フォードアルゴリズム

ダイクストラ法には負の重みを許容しないという制約がありますが、ベルマン-フォードアルゴリズムは動的計画法を用いてこれを克服します。このアルゴリズムは、 出発点から目的地への最短経路にはサイクルが含まれず、最長でも$V-1$個のエッジで構成されるという事実を利用します。最初のノードから到達可能なすべてのノードへの最小距離を$V-1$回以内に更新することで、 すべての経路を調べ、負の重みを含む場合でも最短経路を保証します。

void Bellman_Ford(WeightedAdjacencyMatrix graph, int start, int end) {
    int v = graph.mat.size();
    vector<int> estimates(v, 100);
    estimates[start] = 0;
 
    for (int i = 0; i < v; i++) {
        for (int j = 0; j < v; j++) {
            if (estimates[j] != 100) {
                for (int k = 0; k < v; k++) {
                    if (graph.mat[j][k] != 0) {
                        estimates[k] = min(estimates[k], estimates[j] + graph.mat[j][k]);
                    }
                }
            }
        }
    }
 
    cout << "Min cost is " << estimates[end] << endl;
};

重み付き隣接リストを使用する場合、このアルゴリズムの計算量は隣接行列の場合の$O(V^3)$から$O(VE)$に削減されます。 これは、すべてのエッジを$V$回反復してコストを更新するだけで済むためです。ただし、このアルゴリズムはコストが無限に減少する負のサイクルを含むグラフには適用できません。 更新の際に以前のノードを記録することで、最短経路を復元することも可能です（クイズQ2）。

結論

本記事では、動的計画法が解決する問題、その仕組み、そしてフィボナッチ数列や最短経路問題における実装について説明しました。 動的計画法は最適化問題を扱うため、機械学習などの分野で非常に関連性があります。機械学習シリーズの今後の記事で、このテーマをさらに掘り下げていきます。

クイズ

この記事では、学習した内容を確認するためのクイズを設けます。記事のメイン部分を読んだ後に、ぜひ自分で問題を解いてみることを強くお勧めします。各問題をクリックすると答えが表示されます。

リソース

• GeeksForGeeks. 2024. Bellman–Ford Algorithm. GeeksForGeeks.