最小コストパスのための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