最小成本路徑的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中文網其他相關文章！