최소 비용 경로를 위한 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)입니다.

Method− 주어진 행렬과 크기가 비슷한 답안 행렬을 만듭니다.

이 행렬을 상향식 방식으로 채웁니다.

주어진 − 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])

여기에서 최소 비용 경로[i][j]를 계산하기 위해 우리는 최소 비용 경로[i - 1][j - 1], 최소 비용 경로[i - 1][j] 및 최소 비용 경로[i][j -를 사용하는 경향이 있습니다. 1] 결과적으로 이는 최소 비용 경로[i][j]에 도달하는 유일한 허용 셀입니다. 마지막으로 최소 비용 경로[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 중국어 웹사이트의 기타 관련 기사를 참조하세요!