最小コストパスの C プログラム

ここではC言語で最小コストパス問題を解きます。これは、各セルに移動コストがある 2D マトリックス上で実行されることを目的としています。最小の移動コストで左上隅から右下隅までのパスを見つけなければなりません。特定のセルから右下にのみセルを移動できます。

この特定の問題を解決するには、再帰よりも動的プログラミングの方が適しています。

コスト行列 c ost[ ][ ] と位置 (m,n) が与えられた場合、(0, 0) (m,n) からの最小パス コスト (m,n) へのパスの総コストは、そのパス上のすべてのコスト (送信元と宛先を含む) の合計です。

仮定- すべてのコストは正です。入力行列には負のコスト サイクルはありません。

例

(2,2) への最小コスト パスを見つけます。

コストはそれ自体が与えられた画像にあります。パスは (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2) となります。パスの値は 8 (1 2 2 3) です。

メソッド- 指定された行列と同じサイズの回答行列を作成します。

このマトリックスにボトムアップ方式で値を入力します。

与えられた- arrA[ ][ ]。各セルには 2 つのオプション (右または下) があり、任意の i,j セルに対して、これら 2 つのオプションの最小値を選択できます。

solution[i][j]=A[0][j] if i=0, 1st row
   =A[i][0] if j=0, 1st column
=A[i][j]+Min(solution[i=1],[j],solution[i][j-1]) if i>0 && j>0

アルゴリズムの回答で採用されているアプローチでは、動的プログラミングを適用することで、この問題を効率的に解決できます。サイズ m,n の最小コスト パス テーブルを作成し、次のように定義します。

minimumCostPath[i][j] = minimum value to achieve (i, j) from (0, 0)

当然のことながら、

minimumCostPath[0][0] = costMatrix[0][0]
minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0], for all values of i > zero
minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j], for all values of j >zero

次に、アルゴリズムで適用されるのと同様の式を適用して、最小コスト パス行列を埋めます。以前のすべての値は最小コスト パス マトリックス内で計算されているため、アルゴリズムの答えのようにこれらの値を再計算しません。

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

ここでは、minimumCostPath[i][j]を計算するために、minimumCostPath[i - 1][j - 1]、minimumCostPath[i - 1][j]、minimumCostPath[i]を使用する傾向があります。 ][ j - 1] 結果として、これらは、minimumCostPath[i][j] に達する唯一の許可されたセルになります。最後に、minimumCostPath[m][n]を返します。

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

例

リアルタイム デモンストレーション

#include <iostream>
using namespace std;
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(){
   int cost[4][4] = {
      { 9, 9, 4 },
      { 8, 0, 9 },
      {1, 2, 8}
   };
   cout<<" The minimum cost is "<<min_cost(cost, 2, 2);
   return 0;
}

出力

The minimum cost is 17

以上が最小コストパスの C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。