3
최적화 문제가 있습니다.스타 검색 : 많은 노드와 노드 간의 "느린"CheckLink ... 어떤 제안?
평면이있는 점을 나타내는 많은 노드 (10^5) 그래프가 있습니다.
"시작 노드"에서 시작하여 "끝 노드"에 도달하려면 그래프에서 최단 경로를 찾아야합니다.
노드 쌍을 연결하거나 연결하지 않을 수 있습니다. 그들이 연결되어 있는지 확인하는 것은 매우 비용이 많이 드는 작업입니다. 링크가 연결된 경우 링크에 연결된 가중치는 두 노드 사이의 유클리드 거리입니다.
현재 "현재 노드"에서 모든 다른 노드로의 모든 링크 만 확인하여 A *의 "열린 목록"을 채 웁니다. 나는 A *를 선택했다. 그것은 길 찾기에서 최고의 알고리즘 인 것처럼 보이고 노드 J (H = 목표 거리)에 대해 빠르고 허용 가능한 휴리스틱 H를 가졌지 만 그것이 내 문제에 대해 좋은지 확신 할 수 없다.
그래프를 앞면으로 작성하는 것이 관리하기 어렵습니다. N^2 링크를 확인해야합니다. 너무 느립니다. 현재 (almst) 전체 그래프는 솔루션이 없으면 처음부터 끝까지 경로가 만들어지지 않습니다.
더 나은 솔루션에 대한 힌트를 얻고 싶습니다 ... 감사합니다!
CheckLink는 어떻게 구현됩니까? 해결책을 찾을 수 없을 때 거의 완전한 그래프를 작성해야합니다. –
Bresenham 알고리즘 "이미지와 같은"격자 – ugasoft