2D 행렬에서 최저 비용 경로를 찾는 방법

Question

나는 경로의 최저 비용을 얻는 것이 목표입니다. 경로가 수평 또는 대각선으로 진행될 수 있습니다. 수직이 아닙니다. 아래처럼. 이고 첫 번째 행과 마지막 행도 인접합니다. 매트릭스 아래 참조 예를 들어

:

output for 1st matrix : 
16 
1 2 3 4 4 5-->path row number 

output for second matrix: 
11 
1 2 1 5 4 5-->path row number 

자바에서 그 일을하고는 가장 낮은 경로를 얻고 있지만 행을 사용하여 경로를 인쇄 경로를 받고 있지 않다 번호.

int minCost(int cost[r][r], int m, int n) 
{ 
    if (n < 0 || m < 0) 
     return Integer.MAX_VALUE;; 
    else if ((m == r-1 && n == c-1)|| n+1>=c) 
     return cost[m][n]; 
    else 
     return cost[m][n] + min(minCost(cost, m+1>=r?r-1:m+1,n+1), 
             minCost(cost, m,n+1), 
           minCost(cost, m-1>=0?m-1:r-1,n+1)); 
    } 
// calling it 
minCost(cost, 0, 0); 

최단 경로에 대한 행 번호를 얻는 방법은 무엇입니까?

Answer 1

내가 파비안의 의견을 확장하려고합니다 :

그것은 같은 인수로 호출 경우 minCost 함수가 같은 값을 반환합니다 분명하다. 귀하의 알고리즘에서는 실제로 동일한 값으로 여러 번 호출됩니다. 열 0에 대한 모든 호출은 열 1에 대해 3 개의 호출을 생성하고, 차례로 열 2에 대해 9 개의 호출을 생성합니다. 마지막 열은 엄청난 수의 호출을 가져 오며 (대부분 fabian이 지적한 것처럼 3^r) 다른 호출에 대해 동일한 값.

아이디어는 필요할 때마다 다시 계산할 필요가 없도록 이러한 값을 저장하는 것입니다. 이 작업을 수행하는 가장 간단한 방법은 원본과 동일한 크기의 새 행렬을 만들고 각 셀에 도달하기위한 최소 합계를 계산하는 것입니다. 첫 번째 열은 간단합니다 (단 한 단계 만 포함되므로 원래 배열에서 복사). 그리고 이미 계산 된 값을 다시 사용하여 다른 열을 계속 진행합니다.

그런 다음 두 번째 행렬을 두 개의 열로 바꿔 공간 사용을 최적화 할 수 있습니다. 일단 n 열을 계산하면 n-1 열이 필요하지 않습니다. 이것은 약간 까다로울 수 있으므로 확실하지 않은 경우 전체 배열을 처음 사용할 것을 권장합니다.

Answer 2

귀하의 알고리즘은 매우 비효율적입니다. 내가 생각할 수있는 가장 좋은 해결책은 뒤로 계산하는 것입니다 (오른쪽에서 왼쪽으로). 두 번째 행렬의 오른쪽 2 열을 고려 : 지금 우리는 값 8 셀에있는

8 6 
7 4 
9 5 
2 6 
2 3 

경우, 다음 단계는 6/4/3 수 있습니다. 물론 우리는 더 적은 비용을 원하기 때문에 3을 선택합니다. 우리가 값 7 셀에있는 지금 경우, 다음 단계는 우리가 4를 선택합니다, 6/4/5 할 수 있도록 두 개의 열은 하나 개의 컬럼에 병합 할 수 있습니다

11 //8+3 
11 //7+4 
13 //9+4 
5 //2+3 
5 //2+3 

이제 마지막 두 개의 열을 반복 :

2 11 
2 11 
9 13 
3 5 
1 5 

마지막으로 행렬이 하나의 열에 병합됩니다. 열의 최소값이 가장 낮습니다.