수백만 개의 꼭지점과 가장자리가있는 유향 그래프가 있습니다. 정점 집합이 주어지며, 정점이 "START_POINTS"라고 가정 해 봅시다. "END_POINTS"라고하는 다른 정점 세트도 제공됩니다. 문제는 어느 START_POINTS에서 어느 END_POINTS에 도달 할 수 있는지를 찾는 것입니다.유향 그래프에서 효율적인 검색
START_POINTS: S1 S2 S3 S4 S5 S6 S7 ...
END_POINTS : E1 E2 E3 E4 E5 E6 E7 ...
알고리즘은 다음과 같이 말할 수있을 것입니다 :
S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....
END_POINTS의 일부
는 START_POINT에서 도달되지 않을 수 있습니다 여기에 은 예입니다.이제 질문은 다음과 같습니다. 구현하는 가장 효율적인 방법은 무엇입니까?
각 START_POINT부터 시작하여 깊이 우선 검색 (또는 BFS를 사용하여 도달 시간을 많이 변경 함)을 사용하여 도달 가능한 END_POINTS를 찾습니다. 그러나 너무 많은 START_POINTS가 있기 때문에 많은 시간이 필요합니다 (많은 END_POINTS도 있음).
추적 경로 START_POINTS 사이에 큰 겹침이 있기 때문에 검색을 최적화 할 수 있습니다. 어떤 경로가 어느 END_POINTS에 도달 할 수 있는지 기억해야합니다. 이것을 달성하는 가장 효율적인 방법은 무엇입니까? 이것은 잘 알려진 문제 일지 모르지만 아직 해결책을 찾지 못했습니다. 1월 6일에
편집 :
나는 (키스 랜달은 제안 된 것과 유사한 방식으로) 고 대역폭의 아이디어를 구현하기 위해 노력 :이 노드가 END 포인트를 시작하거나하지 않는 경우 각 노드를 들어, 모든 연결 입력을 출력에 연결 한 다음 노드를 제거하십시오.
foreach NODE in NODES
Skip if NODE is START_POINT or END_POINT
foreach OUTPUT_NODE of NODE
Disconnect NODE from INPUT_NODE
end
foreach INPUT_NODE of NODE
Disconnect NODE from INPUT_NODE
foreach OUTPUT_NODE of NODE
Connect INPUT_NODE to OUTPUT_NODE
end
end
Remove NODE from NODES
end
이 매우 빠르게 시작하고 신속하게 나머지 노드의 입력/출력 카운트가 매우 크고 루프 중첩 얻을 주로하기 때문에, 매우 느려지는 성능을 죽인다. 어떻게하면 더 효율적으로 만들 수 있을지 아십니까?
이 방법을 구현하고 결과를 얻으려고합니다. – Yilmaz