最小コストパスの C プログラム-C++-php.cn

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

王林

リリース： 2023-08-26 18:17:07

転載

1123 人が閲覧しました

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

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

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

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

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

例

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

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

コストはそれ自体が与えられた画像にあります。パスは (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;
}

ログイン後にコピー