비용 비용 매트릭스가 양수 및 음수 인 최소 비용 경로

Question

이것은 저비용의 최소 비용 경로 동적 프로그래밍 문제의 변형입니다.

비용 매트릭스 mxn이 주어졌습니다. 비용 매트릭스에는 양수 버퍼가 있고 음수 비용은 임의로 배치됩니다. 나는 [1,1]부터 시작하여 [m, n]에 가야만합니다. 나는 초기 버퍼 x로 시작한다. 내 탐색을 통해 내 버퍼 x는 절대로 < = 0이되어서는 안됩니다. < = 0이되면 최종 상태가 양수 버퍼 인 경우에도 유효하지 않은 경로가됩니다 (초기 건강 상태로 시작하는 플레이어와 같다고 생각하면 부정적인 비용 공제 건강 및 긍정적 인 완충기는 건강을 추가한다). 그 사이에 0 버퍼를 두지 않고 [m, n]으로 만들 수있는 최소 초기 버퍼는 무엇입니까 (플레이어가 죽지 않고 경로를 완료 할 수 있도록 최소 초기 상태)

Answer 1

하자 H[i, j]은에서 시작할 때 플레이어가 필요로하는 최소한의 건강이라고 말합니다. 우리는 시작 광장에서 필요한 최소 건강 인 H[1, 1]에 관심이 있습니다.

비용 매트릭스 M의 모든 값이 정수라고 가정합니다. 그러므로 가장 작은 양의 건강 상태는 1입니다.

마지막 스퀘어를 스테핑하기 전에 필요한 건강 상태는 간단합니다. 해당 스퀘어 값이 양수이면 1이 필요하고 그렇지 않으면 빼기 수보다 적어도 더 많이 필요합니다.

M[m, i] 및 i 및 j 임의위한 M[j, n] :

H[m, n] = max(1 - M[m, n], 1) 

다른 것들은 쉽게 매트릭스의 에지이다.

H[m, i] = max(H[m, i+1] - M[m, i], 1) 
H[j, n] = max(H[j+1, n] - M[j, n], 1) 

행렬의 중심에 우리가 오른쪽으로 추락 (모두 선택 사항이 현재 값이 음수이면 우리는 그렇지 않으면 우리는 그것을 줄일 수 있습니다 (그러나 결코 더 1보다) 필요한 건강 버퍼를 증가시켜야). 따라서 해당 대안의 최소값을 취합니다 :

H[i, j] = min(max(H[i, j+1] - M[i, j], 1), 
       max(H[i+1, j] - M[i, j], 1)) 

그게 전부입니다! 코드에이 변환 간단한다 (M, m 및 n 제공하고 M을 가정하고 1-기반) :

int[] H = new int[m, n]; 

H[m, n] = max(1 - M[m, n], 1); 

// remember to loop backwards 
for (int i = m-1; i >= 1; i--) 
    H[m, i] = max(H[m, i+1] - M[m, i], 1); 
for (int j = n-1; j >= 1; j--) 
    H[j, n] = max(H[j+1, n] - M[j, n], 1); 

// again, loop backwards 
for (int i = m-1; i >= 1; i--) 
    for (int j = n-1; j >= 1; j--) 
     H[i, j] = min(max(H[i, j+1] - M[i, j], 1), 
         max(H[i+1, j] - M[i, j], 1)); 

return H[1, 1];