C言語で解く最小コストパス問題 ― 動的計画法による効率的な実装方法

はじめに

本記事では、C言語を用いて「最小コストパス問題」を解く方法を解説します。この問題は、各セルに移動コストが設定された2次元行列を対象とし、左上隅から右下隅までの経路の中で、合計コストが最小になるものを見つけるというものです。あるセルから移動できるのは、下または右隣のセルのみです。

この種の問題は、単純な再帰処理よりも動的計画法（Dynamic Programming）を使ったほうがはるかに効率的に解けます。

コスト行列 cost[][] と座標 (m, n) が与えられたとき、(0, 0) から (m, n) に到達するまでの最小コストを返す関数を作成します。経路の総コストとは、出発点と目的地を含む経路上のすべてのセルのコストの合計です。

前提条件： すべてのコストは正の値であり、入力行列には負のコストサイクルが存在しないものとします。

例題：(2, 2) への最小コストパスを求める

次のような3×3のコスト行列を考えてみましょう。

1  2  3
4  8  2
1  5  3

このとき、最小コストとなる経路は (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2) であり、総コストは 8（1 + 2 + 2 + 3）です。

アプローチ：動的計画法による解法

基本的な考え方は、元の行列と同じサイズの回答用行列を作成し、それをボトムアップ方式で埋めていくことです。

与えられた行列 arrA[][] の各セル (i, j) に対しては「右に進む」「下に進む」という2つの選択肢があり、そのうち最小の方を選べばよいことになります。

solution[i][j] = A[0][j]　（i = 0 のとき：1行目）
              = A[i][0]　（j = 0 のとき：1列目）
              = A[i][j] + Min(solution[i-1][j], solution[i][j-1])　（i > 0 かつ j > 0 のとき）

この考え方に基づき、サイズ m×n の最小コストパステーブルを次のように定義します。

minimumCostPath[i][j] = (0, 0) から (i, j) に到達するまでの最小コスト

まず、初期条件は以下の通りです。

minimumCostPath[0][0] = costMatrix[0][0]
minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0]　（i > 0 のとき）
minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j]　（j > 0 のとき）

続いて、残りのセルを次の漸化式で埋めていきます。必要な値はすでにテーブル内で計算済みのため、再帰解法のように同じ計算を何度も繰り返す無駄がありません。

minimumCostPath[i][j] = costMatrix[i][j]
                       + Min(minimumCostPath[i - 1][j - 1],
                              minimumCostPath[i - 1][j],
                              minimumCostPath[i][j - 1])

(i, j) に到達できるのは (i-1, j-1)、(i-1, j)、(i, j-1) のいずれかのセルからだけであるため、これら3つのうち最小の値を採用します。最後に minimumCostPath[m][n] を返せば答えが得られます。

この動的計画法アルゴリズムの時間計算量は O(mn) です。

C言語でのサンプルコード

#include <stdio.h>

int min_(int a, int b, int c) {
    if (a < b)
        return (a < c) ? a : c;
    else
        return (b < c) ? b : c;
}

int min_cost(int cost[4][4], int m, int n) {
    int i, j;
    int tot_cost[4][4];

    tot_cost[0][0] = cost[0][0];

    for (i = 1; i <= m; i++)
        tot_cost[i][0] = tot_cost[i - 1][0] + cost[i][0];

    for (j = 1; j <= n; j++)
        tot_cost[0][j] = tot_cost[0][j - 1] + cost[0][j];

    for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            tot_cost[i][j] = min_(tot_cost[i - 1][j - 1],
                                   tot_cost[i - 1][j],
                                   tot_cost[i][j - 1]) + cost[i][j];

    return tot_cost[m][n];
}

int main(void) {
    int cost[4][4] = {
        { 9, 9, 4 },
        { 8, 0, 9 },
        { 1, 2, 8 }
    };

    printf("最小コストは %d です\n", min_cost(cost, 2, 2));
    return 0;
}

実行結果

最小コストは 17 です

補足：結果の違いについて

なお、上記サンプルコードの漸化式では斜め上のセル (i-1, j-1) も参照しているため、実際には「下・右・斜め下」の3方向への移動を許容した解法となっています。そのため、この行列の場合は (0, 0) → (1, 1) → (2, 2) という対角方向の経路 9 + 0 + 8 = 17 が最小コストとして返されます。「下と右のみ」に制限したい場合は、Min の引数から minimumCostPath[i - 1][j - 1] を除けば意図した動作になります。