1
저는 그래프 스트림 라이브러리를 사용하여 자바에서 그래프를 재귀 적으로 작성합니다. 그러나이 그래프는 너무 커서 재귀가 매우 커서이 작업은 stackoverflow에서 끝납니다. 저를 믿으십시오, 반복조차 나의 문제를 해결하지 않을 것입니다. 나는 다만 도로의 아래 런타임 오류를 얻을 것이다.부분 그래프의 최단 경로 알고리즘
제 목표는 Disjktra 나 A * 등의 검색 알고리즘을 마지막 그래프에 사용하는 것입니다.
전체 그래프가 없기 때문에 부분지도에서 최단 경로 알고리즘과 같은 항목을 찾아보고 있습니다. 발견 적 방법의 사용 나는 많이 찾을 수 없었다.
누군가가 나에게 힌트 (논문, 아이디어, 구현은 대박이 될 것입니다 !!!! :-D)를 주어도 좋을 것입니다. PHA * 또는 일부 알고리즘과 같은 알고리즘을 살펴 봤습니다.
나는 그렇지 않습니다. 부분 그래프의 최단 경로 알고리즘은 각각의 새로운 에지가 지금까지 컴파일 된 모든 결과를 무효화 할 수 있으므로 도움이된다고 생각하십시오. 나는 또한 왜 iteration이 당신을 죽일 지 이해하지 못한다. - 단지 현재의 dfs 루트 경로가 스택에서가 아니라 힙에서 할당되는지 확인한다. (예를 들면 자동 vars 대신에'new'를 사용한다.) 말 그대로 수십억 개의 노드가 있습니다. 실제 문제는 코드의 사이클을 감지하지 못하고 부정적인 가중치가있을 수 있습니까? – collapsar
나는 모든 것을 메모리에로드하지 않고 파일을 읽고 쓰는 ** complete ** 그래프를 처리하는 알고리즘을 살펴볼 것이다. 예를 들어 출발점으로부터의 거리에 따라 노드를 정렬하여 너비 우선의 최단 경로 검색을 쉽게 수행 할 수 있습니다. –
@ collapsar : 아이디어를 가져 주셔서 감사합니다. 노드가 많으면 반복을하면 죽을 것입니다. 수십억 달러까지 올 수 있어요 .. 네. 그리고 나는 내 코드를 두 번 트리플 체크했다 : 나는 거기에 루프가 없다고 확신한다. 그렇기 때문에 휴리스틱을 사용하면 솔루션을 얻는 데 도움이 될 것이라고 생각합니다 ... – COR