동적 프로그래밍을 사용하여 지형지도 최단 경로를 해결하는 방법은 무엇입니까?

Question

가장 왼쪽 열 0th부터 시작하여 positive 정수의 행렬이 주어지면 가장 오른쪽 열 (n - 1)th의 최소 경로를 찾으십시오. 예 :

최소 경로는 1을 포함하는 경로입니다.

임의의 정사각형 m[i, j]에서 4 방향 (left, right, up, down)으로 이동할 수 있습니다. 물론 가장 왼쪽, 가장 오른쪽 행/열의 모든 코너 케이스를 제외하고. 예를 들어 [0, 0] 일 경우 right 또는 down 만 이동할 수 있습니다.
내 솔루션은 m x n 버텍스의 그래프를 작성한 후 Floyd-Warshall을 실행하여 두 개의 버텍스의 모든 쌍 최단 경로를 계산합니다. (u, v). 그런 다음 다른 중첩 된 for 루프를 실행하여 열의 모든 정점이있는 0th 열의 모든 정점을 검사하여 최소 경로를 찾습니다.
하지만, 내 교수는 다음과 재발을 사용하여 다른 알고리즘을 제안 : 나는 그것이 어떻게 작동하는지 단서가 없다

S[i, j, L] = 
    min(
     S[i - 1, j, L - 1] + cost[i - 1, j], 
     S[i + 1, j, L - 1] + cost[i + 1, j], 
     S[i, j - 1, L - 1] + cost[i, j - 1], 
     S[i, j + 1, L - 1] + cost[i, j + 1]); 

을! 어떤 정사각형이라도 [i, j]에서 우리는 4 방향으로 이동할 수 있기 때문에 이전에 계산 된 값을 기반으로 테이블을 만들 수 없습니다.
여기에 뭔가 빠졌습니까? 이 재발이 어떻게 작동하는지 나는 볼 수 없다. 어떤 생각?

Answer 1

S [0, j, L] = 0을 제외하고 S [i, j, 0] = 무한대 인 경우 작동해야합니다. 결국 모든 S [i, j, L] == S [i, j, L + 1] 반복을 멈출 수 있습니다. S [i, j, L]는 첫 번째 열에서 그 셀까지의 최단 경로 비용을 갖는다.

이이 재발는 더 이상의 변경은 왼쪽 상단 모서리에 자리를 차지할 것 L.

의

0 inf inf inf inf 
0 inf inf inf inf 
0 inf inf inf inf 

0 1 inf inf inf inf 
0 20 inf inf inf inf 
0 21 inf inf inf inf 

0 1 2 inf inf inf 
0 2 30 inf inf inf 
0 21 22 inf inf inf 

0 1 2 3 inf inf 
0 2 3 39 inf inf 
0 12 22 23 inf inf 

0 1 2 3 4 inf 
0 2 3 4 47 inf 
0 12 12 23 24 inf 

0 1 2 3 4 5 
0 2 3 4 5 48 
0 12 12 12 24 25 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 12 12 12 6 25 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 12 12 7 6 7 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 12 8 7 6 7 

0 1 2 3 4 5 
0 2 3 4 5 6 
0 9 8 7 6 7 

을 값을 증가 왼쪽 상단 모서리에 어떻게 보일지입니다. 각 셀에 도달하는 데 드는 최소 비용을 천천히 발견하고 있음을 알 수 있습니다.