dijkstra 알고리즘에 관한 질문

Question

데이터 세트의 두 노드 사이에서 최단 경로를 찾으려고합니다. 나는 dijkstra 알고리즘을 구현했으며 두 개의 노드 (예 : Andrew_Card 및 Dick_Cheney)가 있음을 증명하기 위해이를 사용하고 있습니다. 경로가 소스와 대상 사이에 존재하지 않습니다. 그러나, 나는 내 프로그램이 운영 체제에 의해 죽게되는 을 찾고 있습니다.

디버깅 후이 문제는 RAM에 할당 된 리소스와 관련이있는 것으로 나타났습니다. 다 익스트라 알고리즘에 관해서는, 노드의 수는 N = 16,375,503는 다음 공간 요구 사항은, 그것을하지 않습니다

n*n = 16,375,503 * 16,375,503 > 10^{14}. 

우리가 그래서 적어도

(10^{14} * 4)/(1024 * 1024 * 1024) = 10^5 GB (approximately equal) 
of RAM. 

필요한 메모리에이 알고리즘을 실행하는 경우 우리가 큰 연결된 그래프를 메모리에 유지하려는 경우 dijkstra를 사용하여 최단 경로를 찾을 수 있습니다. 오랫동안 내가 붙어있어서 내가 틀렸다고 정정 해 주시겠습니까? 또는 내가 점검해야 할 다른 가능한 이유가있을 수 있다면, 나도 그 점을 지적 해주십시오. 당신이 A* 같은 것을 사용하여 두 노드 사이 그냥 거리를해야하는 경우

나는

C++로 가장자리의 번호 = 25908132

Answer 1

가장자리 수가 비교적 적으므로 (모든 가장자리가 주 메모리에 맞을 수 있도록) 인접 목록을 사용하여 그래프를 저장할 수 있습니다. O(V^2) 대신 O(V + E) 메모리가 필요합니다. 또한, 우선 순위 큐와 함께 Dijkstra의 알고리즘을 사용할 수 있습니다. 이것은 희소 그래프 (O(E log V) 시간 복잡성)에 적합합니다. 이 접근법은 약 2 * 10^7 개의 꼭지점과 가장자리가있는 그래프에서 잘 작동합니다 (좋은 구현은 주 메모리에 쉽게 맞춰지며 몇 분 이상 실행되지 않습니다).

Answer 2

을 프로그램을 구현했습니다.

그러나 모든 포인트가 최단 경로 일 경우 확실히 O(n^2) 공백이 붙어 있습니다. O(n^2) 답변을 찾고 있습니다. 따라서 모든 것을 저장하는 것보다 더 잘 할 수는 없습니다.

Answer 3

프로그램에서 실제로 메모리가 부족한 지 확인하려면 try-catch 블록에서 callsite를 래핑하고 std :: bad_alloc 예외가 발생하는지 확인하십시오. 잡는 예외를 볼 때까지 프로그램의 어느 부분이 실패했는지에 대한 가정을하지 마십시오.

두 노드 간의 최단 경로를 찾는 측면에서 가장 적합한 것이 무엇인지 찾아야합니다 귀하의 유스 케이스에 대한 알고리즘.

A * : http://en.wikipedia.org/wiki/A * _search_algorithm

수축 계층 구조 : 당신은 노드의 수를 줄일 수있는 방법을 찾아야한다

Answer 4

http://algo2.iti.kit.edu/schultes/hwy/contract.pdf. 노드 수가 많습니다. Voronoi Diagram을 사용하여 노드 수를 줄일 수 있습니다.

Answer 5

우선 순위 큐에 정점을 한 번만 저장할 수 있습니다. 우선 순위 큐에 동일한 버텍스를 계속 추가하는 대신 우선 순위 큐를 업데이트하십시오.