복잡한 경로 지정 경로

Question

     L->| 
    A -> B   ^| 
    |__> C -> D-> G->X--| | 
     K |_> T | |_>Z 
     |___________| 

이 작은 그림이 내가하려는 일을 전달하는 데 도움이되기를 바랍니다.

나는 7000 개의 위치리스트를 가지고 있는데, 각각은 정의되지는 않았지만 적은 수의 문이 있습니다. 각 문은 두 위치 사이의 다리 역할을합니다.

위의 다이어그램을 참조하면 A부터 Z까지가는 가장 빠른 경로를 찾는 방법은 무엇입니까?

원본에 전체가 필요하지 않습니다. 단지 의사 코드 만 좋을 것입니다.

명백히 취할 수 A -> B -> C -> D -> G -> X -> L -> Z, 있지만, 최단 경로가 A -> B -> C -> K -> X -> Z.

Answer 1

위치를 노드로 표시하고 문을 그래프의 가장자리로 나타냅니다. 그런 다음 다소 표준 인 shortest path algorithm(s)을 적용하면 완료됩니다.

Answer 2

위키 피 디아에서 Pathfinding 알고리즘을 찾으십시오. 기본적으로 일련의 노드와 연결을 구축하고 알고리즘을 통해 처음부터 끝까지 길을 찾습니다.

Answer 3

각 객실에는 노드 각각의 문이 노드이고 당신을 수 발견이있는 경우 문제가 당신이 예를

Answer 4

에 대한 Dijkstra's algorithm으로 찾을 수 있습니다 그래프에서 최단 경로를 찾는 될 것이라고 가정 할 수 최선의 노드에 대해 합리적인 추측을 시도한 다음 A * 알고리즘을 사용할 수 있습니다. 내 블로그에 C#을 구현했습니다. 코드를 자유롭게 사용하십시오. 올바른 경험적 방법이 주어지면, A *는 다른 경로 찾기 알고리즘보다 훨씬 더 효율적일 수 있습니다.

http://blogs.msdn.com/ericlippert/archive/tags/AStar/default.aspx