최소 비용 경로를 위한 C 프로그램

여기에서 우리는 C에서 최소 비용 경로 문제를 해결할 것입니다. 의미는 각 셀에 이동 비용이 있는 2D 매트릭스에서 수행됩니다. 최소한의 여행 비용으로 왼쪽 상단 모서리에서 오른쪽 하단 모서리까지의 경로를 찾아야 합니다. 주어진 셀에서 아래쪽 및 오른쪽 아래쪽 셀만 탐색할 수 있습니다.

이 특정 문제를 해결하려면 재귀보다 동적 프로그래밍에 접근하는 것이 훨씬 좋습니다.

주어진 비용 매트릭스 c ost[ ][ ] 및 위치(m,n) , 우리는 (0,0)에서 (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