Pythonで最小コストパスを求める方法｜動的計画法による実装を徹底解説

本記事では、以下の問題文に対する解決策について詳しく解説します。

問題文

コスト行列と目標位置 (m, n) が与えられたとき、開始地点 (0, 0) から (m, n) まで移動するための最小コストパスのコストを求めます。行列の各セルには、そのセルを通過する際にかかるコストが設定されており、移動は「右」「下」「右下」のいずれかの方向に進むことができます。

それでは、実際の実装を見ながら解決策を確認していきましょう。

実装例

# 動的計画法によるアプローチ
R = 3
C = 3
def minCost(cost, m, n):
    # 初期化
    tc = [[0 for x in range(C)] for x in range(R)]
    # ベースケース
    tc[0][0] = cost[0][0]
    # 1列目の合計コスト(tc)配列を計算
    for i in range(1, m + 1):
        tc[i][0] = tc[i-1][0] + cost[i][0]
    # 1行目のtc配列を計算
    for j in range(1, n + 1):
        tc[0][j] = tc[0][j-1] + cost[0][j]
    # 残りのtc配列を計算
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            tc[i][j] = min(tc[i-1][j-1], tc[i-1][j], tc[i][j-1]) + cost[i][j]
    return tc[m][n]
# メイン処理
cost = [[1, 5, 3],
        [7, 7, 4],
        [8, 5, 3]]
print("Total Cost:", minCost(cost, 2, 1))

出力

Total Cost: 13

アルゴリズムの解説

このプログラムでは、動的計画法（Dynamic Programming）を用いて、各セルまでの最小累積コストを順番に計算しています。補助配列 tc の各要素には、(0, 0) からそのセルに到達するまでの最小コストが格納されます。

• ベースケース： 開始地点 tc[0][0] のコストは、そのセル自身のコストと一致します。
• 1行目・1列目： 移動方向が限定されるため、それぞれ左または上からの一方向のみの累積和として計算します。
• それ以外のセル： 左上・上・左の3つの隣接セルの中から最小値を選び、現在のセルのコストを加算します。

なお、使用されている変数はすべてローカルスコープ内で宣言されており、関数外の状態に依存しない安全な設計になっています。

まとめ

本記事では、動的計画法を活用して最小コストパスを求めるPythonプログラムの実装方法について学びました。この手法を使えば、すべての経路を総当たりで探索する必要がなく、計算量を大幅に抑えながら最適解を効率的に導き出すことができます。経路探索やコスト最適化の問題に取り組む際の参考にぜひしてください。