시공간 트레이드 오프를 사용하는 최단 경로 알고리즘은 무엇입니까?

Question

문제점 : 가중치가없는 방향이없는 그래프에서 최단 경로를 찾는 것.

너비 우선 탐색은 두 노드 간의 최단 경로를 찾을 수 있지만 O (| V | + | E |) 시간까지 걸릴 수 있습니다. 미리 계산 된 룩업 테이블은 요청이 O (1) 시간에 응답 될 수 있지만 O (| V |^2) 공간의 비용으로 응답 할 수 있습니다.

내가 궁금하네요 : 더 세밀한의하는 공간 - 시간의 트레이드 오프을 제공하는 알고리즘은 있습니까?

1. 가 O보다 시간에 최단의 경로를 찾아 낸다 (1)이지만 쌍방향 너비 우선 탐색
2. 보다 빠른 것이보다 적은 공간을 차지 미리 계산 된 데이터를 사용한다 : 즉, 알고리즘이있다 O (| V |^2)?

실용적인 측면에서 : 그래프는 800,000 개의 노드로, 작은 세계 네트워크로 여겨집니다. 모든 페어 최단 경로 테이블은 기가 바이트 단위 일 것입니다. 요즘은 어쩔 수 없지만 요구 사항에 맞지 않습니다.

그러나 호기심 때문에 제 질문을하고 있습니다. 밤에 나를 지키고있는 것이 이 아니라이 아닙니다. "어떻게 모든 쌍의 룩업 테이블에 대해 캐시 실패를 줄일 수 있습니까?"하지만 "들어 본 적이없는 완전히 다른 알고리즘이 있습니까?"

대답이 '아니오'일 수도 있습니다. 괜찮습니다.

Answer 1

가장 짧은 경로를 찾으려면 Dijkstra's algorithm부터 시작해야합니다. a * 알고리즘은 휴리스틱을 사용하여 시작과 목표 노드 사이의 최적 경로를 계산하는 데 걸리는 시간 (예 : 유클리드 거리)을 줄이는 변형입니다. 성능이나 정확성을 위해이 추론을 수정할 수 있습니다.

Answer 2

조회 테이블이 너무 커서 디스크에 저장할 수없는 경우 입력 세트가 매우 커야하는 것처럼 보입니다. 나는 데이터가 RAM에 들어 가지 않을 것이라고 생각한다. 즉, 사용하는 알고리즘이 읽기와 쓰기의 양을 최소화하도록 조정되어야한다는 것을 의미한다. 디스크에 쓰기가 너무 느리기 때문에 디스크에 공간 == 시간이 포함될 때마다.

정확한 알고리즘은 사용하는 그래프의 종류에 따라 다릅니다. This research paper이 관심있어 할 것입니다. 전체 공개 : 나는 그것을 직접 읽지 않았지만 그것이 당신이 찾고있는 것처럼 보입니다.

편집 : 그래프이다

경우 (거의) 연결된 작은 세상 네트워크 인 룩업 테이블 V^2보다 작을 수 없다. 즉, 모든 조회에는 디스크 액세스가 필요합니다. 가장자리가 주 메모리에 맞으면 매번 경로를 계산하는 것이 더 빠를 수도 있습니다. 그렇지 않으면 모든 최단 경로의 길이를 포함하는 테이블에서 경로를 계산할 수 있습니다. 해당 테이블에서 경로를 재구성 할 수 있습니다.

키는 어느 방향으로 서로 가깝게 테이블의 항목이 디스크에서 서로 가깝게 있는지 확인하는 것입니다. 이 저장 패턴은 다음을 수행합니다.

1 2 1 2 5 6 
3 4 3 4 7 8 
     9 10 13 14 
     11 12 15 16 

캐시 계층 구조에서도 잘 작동합니다.

테이블을 계산하려면 블록으로 데이터를 처리하는 수정 된 Floyd-Warshall을 사용할 수 있습니다. 이렇게하면 합리적인 시간에 계산을 수행 할 수 있습니다 (특히 병렬 처리하는 경우).