경로 찾기 소프트웨어는 어떻게 작동합니까?

Question

나는 언어에 구애받지 않는 꽤 높은 수준의 질문을하고있다.

경로 찾기 (Google지도 '길 찾기'또는 GPS 찾기)는 어떻게 작동합니까? 나는 그것이 생각할 수있는 모든 경로를 시도하고 가장 짧은/가장 빠른 등을 선택한다고 믿을 수 없습니다. 시작과 끝 점이 주어진 최상의 경로를 찾는 논리적 인 방법이 있어야합니다.

어떤 종류의 설명이 좋을 것입니다.

Answer 1

shortest path problem 및 Dijkstra's algorithm을 읽어야합니다. 두 점 모두 두 점 사이의 경로를 결정하는 데 사용됩니다. Google지도 (및 기타 매핑 응용 프로그램)는 추가 기능 (예 : 경로 재설정 등)을 추가하지만 이러한 두 가지 개념은 문제가 어떻게 해결되는지에 대한 기본 전제입니다.

Answer 2

아주 오래된 포스트,하지만 난 그냥이 특정 문제를 찾고 내가 설명과 좋은 글 발견 http://blog.kdgregory.com/2011/12/how-gps-calculates-routes.html

기본적으로,이 A* search algorithm 및 경로 분류 (짧은 경로, 긴 경로를 사용을, 등) 계산 및 메모리 요구 사항을 줄일 수 있습니다.