最小コストパス問題とは？動的計画法による解法とC++実装例を解説

問題の概要

各セルに異なるコストが設定された行列が与えられ、あわせて目的地となるセルも指定されます。この問題では、開始セル (0, 0) から目的セルまで移動するときの「最小コスト経路」を求めます。

行列の各セルの値は、そのセルを通過する際にかかるコストを表しています。

移動できる方向には制限があり、あるセルからは「右」「下」「右下（斜め）」のいずれかにのみ進むことができます。

入力と出力

入力：
コスト行列と目的地の座標。ここでは目的地を (2, 2) とします。
1 2 3
4 8 2
1 5 3

出力：
(0, 0) から目的地まで到達するための最小コスト。この例では最小コストは 8 になります。

アルゴリズム（動的計画法）

この問題は動的計画法（DP）を使うことで効率よく解けます。補助行列 totalCost の各要素 totalCost[i][j] には、スタート地点 (0, 0) からセル (i, j) まで移動したときの最小累積コストを格納していきます。

minCostPath(destX, destY, cost)

入力： 目的地の座標 (destX, destY) とコスト行列。

出力： 目的地まで到達する最小コスト。

Begin
    コスト行列と同じサイズの行列 totalCost を定義する
    totalCost[0, 0] = cost[0, 0]

    // 最初の列：真上からしか移動できないため、そのまま累積和を計算
    for i := 1 to destX, do
        totalCost[i, 0] := totalCost[i-1, 0] + cost[i, 0]
    done

    // 最初の行：左からしか移動できないため、そのまま累積和を計算
    for j := 1 to destY, do
        totalCost[0, j] := totalCost[0, j-1] + cost[0, j]
    done

    // 残りのすべてのセル (i, j) を (1, 1) から (destX, destY) まで順に処理
    for all cells (i, j) from (1, 1) to (destX, destY), do
        totalCost[i, j] := min(totalCost[i-1, j-1], totalCost[i-1, j], totalCost[i, j-1]) + cost[i, j]
    done

    return totalCost[destX, destY]
End

ポイントは、各セルへ到達できる経路が「左上」「真上」「左」の3パターンに限られる点です。したがって、この3つのうち累積コストが最小となるセルから移動してくればよく、表を左上から順に埋めていくことで目的地までの最小コストが求まります。

C++による実装例

#include<iostream>
#define ROW 3
#define COL 3
using namespace std;

int cost[ROW][COL] = {
    {1, 2, 3},
    {4, 8, 2},
    {1, 5, 3}
};

int min(int a, int b, int c) {
    return (a<b)?((a<c)?a:c):((b<c)?b:c);
}

int minCostPath(int destX, int destY) {
    int totalCost[ROW][COL];

    totalCost[0][0] = cost[0][0];

    for (int i = 1; i <= destX; i++)
        totalCost[i][0] = totalCost[i-1][0] + cost[i][0];     //totalCost配列の1列目を設定

    for (int j = 1; j <= destY; j++)                          //totalCost配列の1行目を設定
        totalCost[0][j] = totalCost[0][j-1] + cost[0][j];

    for (int i = 1; i <= destX; i++)                          //2行目以降を順に計算
        for (int j = 1; j <= destY; j++)
            totalCost[i][j] = min(totalCost[i-1][j-1], totalCost[i-1][j], totalCost[i][j-1]) + cost[i][j];
    return totalCost[destX][destY];
}

int main() {
    cout << "Minimum Cost: "<< minCostPath(2, 2);             //目的地 (2, 2)
    return 0;
}

実行結果

Minimum Cost: 8

計算量

このアルゴリズムの時間計算量・空間計算量はどちらも O(destX × destY) です。すべての経路を列挙する全探索（指数時間）と比べて、動的計画法により大幅な効率化が実現できます。