대칭 인접 매트릭스를 위해 Floyd-Warshall을 최적화하십시오

StackOverflow https://stackoverflow.com/questions/2037735

  •  19-09-2019
  •  | 
  •  

문제

대칭 인접 매트릭스를 보장 받으면 Floyd-Warshall의 런타임의 일정한 요인을 낮추는 최적화가 있습니까?

도움이 되었습니까?

해결책

어떤 생각을 한 후에 나는 다음과 같이 생각했다.

for (int k = 0; k < N; ++k)
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

물론 우리 둘 다 그것이 정확하고 빠른 것을 보여줄 필요가 있습니다.

정확성은 사소한 플로이드-와 홀 (Floyd-Warshall)의 증거에 의존하기 때문에 증명하기가 더 어렵습니다. 꽤 좋은 증거가 여기에 제공됩니다. 플로이드-와 홀 증거

입력 행렬은입니다 대칭. 이제 나머지 증명서는 수정 된 Floyd-Warshall의 증거를 사용하여 2 개의 내부 루프의 계산 순서가 중요하지 않으며 그래프를 보여줍니다. 머물러 있습니다 각 단계 후 대칭. 이 두 조건이 모두 사실임을 보여 주면 두 알고리즘 모두 같은 일을합니다.

정의합시다 dist[i][j][k] 멀리서 i 에게 j 세트의 정점 만 사용합니다 {0, ..., k} 경로의 중간 정점으로 i 에게 j.

dist[i][j][k-1] 가장자리의 무게로 정의됩니다 i 에게 j. 이 무게 사이에 가장자리가없는 경우이 무게는 무한대로 사용됩니다.

이제 위의 링크 된 증거에 사용 된 것과 동일한 논리를 사용합니다.

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

이제 계산 중입니다 dist[i][k][k] (그리고 마찬가지로 dist[k][i][k]):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

이제 그 이후로 dist[k][k][k-1] 부정적 일 수 없습니다 (또는 우리는 a 네거티브 루프 그래프에서), 이것은 그것을 의미합니다 dist[i][k][k] = dist[i][k][k-1]. 만약 이후 dist[k][k][k-1] = 0 그러면 두 매개 변수 모두 동일합니다. 그렇지 않으면 첫 번째 매개 변수입니다. min() 선택됩니다.

그래서 지금. 왜냐하면 dist[i][k][k] = dist[i][k][k-1], 계산할 때 dist[i][j][k] 그것은 중요하지 않습니다 dist[i][k] 또는 dist[k][j] 이미 허용합니다 k 그들의 길에. 부터 dist[i][j][k-1] 계산에만 사용됩니다 dist[i][j][k], dist[i][j] 머물 것입니다 dist[i][j][k-1] 매트릭스에서 dist[i][j][k] 계산됩니다. 만약에 i 또는 j 동등합니다 k 위의 경우가 적용됩니다.

따라서 계산 순서는 중요하지 않습니다.

이제 우리는 그것을 보여줄 필요가 있습니다 dist[i][j] = dist[j][i] 알고리즘의 모든 단계 후.

우리는 대칭 그리드로 시작합니다 dist[a][b] = dist[b][a], 모든 a 그리고 b.

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
           = min(dist[j][i], dist[k][i] + dist[j][k])
           = min(dist[j][i], dist[j][k] + dist[k][i])
           = dist[j][i]

그러므로 우리의 임무는 모두 사실이며 dist[a][b] = dist[b][a]. 그러므로 dist[i][j] = dist[j][i] 알고리즘의 모든 단계 후

따라서 두 알고리즘 모두 동일하고 올바른 결과를 산출합니다.

속도는 증명하기가 더 쉽습니다. 내부 루프는 일반적으로 호출되는 횟수의 절반 이상이라고 불리우므로 기능은 약 2 배 빠릅니다. 여전히 같은 횟수를 할당하기 때문에 약간 느리게 만들었지 만 이것은 중요하지 않습니다. min() 대부분의 시간을 차지하는 것입니다.

내 증거에 잘못된 것이 있지만 기술적이지만 자유롭게 지적하면 고치려고 노력할 것입니다.

편집하다:

루프를 변경하여 속도를 높이고 메모리의 절반을 절약 할 수 있습니다.

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < k; ++i)
        for (int j = 0; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
    for (int i = k; i < N; ++i) {
        for (int j = 0; j < k; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]);
        for (int j = k; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]);
    }
}

이것은 최적화 된 알고리즘의 루프에 대해 위의 부분을 나누기 때문에 여전히 정확하며 동일한 속도가 발생하지만 메모리의 절반을 사용합니다.

아이디어에 대해 Chris Elion에게 감사합니다.

다른 팁

(Wikipedia 기사의 의사 코드에서 표기법을 사용하여) Edgecost 행렬이 대칭 인 경우 각 반복 후에도 경로 행렬도 대칭이라고 생각합니다. 따라서 각 반복에서 항목의 절반 만 업데이트하면됩니다.

낮은 레벨에서 행렬의 절반 만 저장하면 (d (i, j) = d (j, i)이므로 사용 된 메모리의 양을 줄이고 캐시 누락 수를 줄일 수 있습니다. 동일한 데이터에 여러 번 액세스 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top