그리드에서 2 노드 사이의 경로를 찾는 가장 효율적인 방법

Question

나는이 특별한 문제가 어떻게 가장 잘 해결되는지 궁금해했습니다. 내가 문제가 될 수있는 점은 파이프 라인 게임 컨셉이었다. see screenshot

나는 그리드가 10x10이다. 그리드의 모든 사각형은 인접한 필드에 연결할 수 있습니다. 그리드의 왼쪽에있는 1 ~ 4 개의 모서리 (대각선 없음, 위쪽, 봇, 왼쪽, 오른쪽)는 각 행에 하나씩 10 개의 시작점이 될 수 있습니다. 오른쪽 10 종점은 그리드의 각 행에 1도 있습니다.

이제 내 질문 : 출발점에서 끝점까지 모든 가능한 경로를 찾는 가장 효율적인 방법은 무엇입니까? 시작 지점에 있지만 끝점에 연결하지 않음)?

나는 폭 - 우선 검색 알고리즘을 사용하여 그 사이의 모든 경로를 찾았지만 시도해 볼 수있는 더 나은 대안이 있습니까?

Answer 1

A* 보통 약간의 그래프에 최단 경로를 찾기 위해, 훨씬 빠른 BFS 다음이다.

A *는 admissible heuristic function [manhattan distance 발견 일반적으로 그리드에 적용 할 수 있습니다]을 가지고 당신을 필요로하고, 연락하기 때문에, 훨씬 빠르게 BFS 후 보통 - 그래서으로 이어질 가능성이 높습니다 조사 노드를 preferes 더 나은 해결책.

또한 A *도 완전합니다 [경로가있는 경우 경로를 찾습니다] 및 최적 [단락 경로를 찾습니다].

편집 : 예를 들면 다음과 같습니다 : 또한 시간/성능의 오프 더 무역 수 있습니다 *
A A weighted A*를 사용하여, 당신이 아닌 최적의 솔루션을 얻을 것이다,하지만 당신은 훨씬 더 빨리 그것을 얻을 가능성이 높다. 받지 A의 * [h=0] A * 당신이 아닌 가중 가장자리

Answer 2

너비를 먼저 시작하면 길이가 1이고 그 다음에 2, 3, 4 등의 경로가 수집됩니다. 길이 k에서 k + 1까지 다음 단계에서 종점이 이미 일부 경로에서 사용되지 않은 경우 일부 경로에만 종점을 추가합니다. 그것은 당신이 덜 또는 동등하게 최적의 경로를 버리는 것을 보장합니다.

원점 이외에도 모든 경로 점에는 명확한 들어오는 가장자리가 있습니다. 따라서 데이터 구조로서 점 당 들어오는 가장자리 (또는 no_incoming)를 저장할 수 있습니다. 이렇게하면 최적의 경로가 삭제됩니다.

케이스 : 마찬가지로 최적 경로가 몇 인입 에지를 갖는 데이터 포인트로서 표현 될 수있는 최적의 경로와 동일. 길이 k에서 k + 1로 가면서 모든 새로운 종점이 수집됩니다.

• 경로에 후보 엔드 포인트가 있지만 새 (k + 1) 개의 종점에없는 경우 후보 최적 경로이며 삭제됩니다. 재귀가 실패합니다.
• 후보 엔드 포인트가 최신 인 경우 새로운 최적 경로가 발견됩니다. 재귀가 계속됩니다.
• 후보 종점이 새 종점에만있는 경우 대체 최적 경로가 발견됩니다. 재귀도 멈 춥니 다.

---

코드

public void determineAllPaths(Grid grid, Point origin) { 
    this.grid = grid; 
    this.origin = origin; 
    grid.setOnPath(origin, null); // to, from 
    Set<Point> priorEndPoints = Collections.singleton(origin); 
    determinePaths(priorEndPoints); 
} 

private void determinePaths(Set<Point> priorEndPoints) { 
    if (priorEndPoints.isEmpty()) 
     return; 
    Set<Point> nextEndPoints = new HashSet<Point>(); 
    for (Point priorEndPoint : priorEndPoints) { 
     for (Point nextEndPoint : priorEndPoint.naybours()) { 
      if (grid.isOnPath(nextEndPoint) 
        && !nextEndPoints.contains(nextEndPoint)) { 
       continue; 
      } 
      //if (nextEndPoints.contains(nextEndPoint)) { 
      // continue; 
      //} 
      grid.setOnPath(nextEndPoint, priorEndPoint); // to, from 
      nextEndPoints.add(nextEndPoint); 
     } 
    } 
    determinePaths(nextEndPoints); 
}