Google 지도와 같은 지도 라우팅이요?

Question

나는 항상 Map Routing에 흥미를 느꼈지만 이에 대한 좋은 입문(또는 고급!) 수준 튜토리얼을 찾지 못했습니다.누구든지 포인터, 힌트 등이 있습니까?

업데이트: 저는 주로 지도 시스템이 어떻게 구현되는지(데이터 구조, 알고리즘 등)에 대한 지침을 찾고 있습니다.

Answer 1

다음을 살펴보세요. 오픈 스트리트 맵 프로젝트 사용자가 제공하고 라이선스가 부여된 데이터만 사용하는 진정한 자유 소프트웨어 프로젝트에서 이런 종류의 문제가 어떻게 해결되고 있는지 확인하고 흥미로운 내용이 포함된 위키.

몇 년 전에는 관련된 사람들이 꽤 쉽게 진행되고 내가 가진 많은 질문에 답변했기 때문에 그들이 여전히 좋은 무리가 아닌 이유가 없습니다.

Answer 2

Google 지도 경로 찾기 기능의 엔지니어 중 한 명인 Barry Brumitt는 관심을 가질 만한 주제에 대해 다음과 같은 게시물을 작성했습니다.

더 나은 길 찾기를 위한 길2007년 11월 6일 오후 03:47:00

Answer 3

A*는 실제로 프로덕션 매핑 알고리즘에 훨씬 더 가깝습니다.Dijikstra의 원래 알고리즘에 비해 탐색이 훨씬 덜 필요합니다.

Answer 4

지도 라우팅이란 거리 네트워크를 따라 최단 경로를 찾는 것을 의미합니까?

Dijkstra 최단 경로 알고리즘이 가장 잘 알려져 있습니다.Wikipedia에는 ​​나쁜 소개가 없습니다. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

여기에 실제로 작동하는 모습을 볼 수 있는 Java 애플릿이 있습니다. http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html Google에서는 거의 모든 언어로 된 소스 코드를 제공합니다.

운전 경로를 생성하기 위한 실제 구현에는 도로 네트워크 계층 구조, 평균 속도, 교차로 우선 순위, 교통 신호 연결, 금지 회전 등 링크 및 노드 횡단과 관련된 비용을 설명하는 거리 네트워크에 대한 상당한 양의 데이터가 포함됩니다.

Answer 5

각 지도 서비스 제공업체(Gmaps, Ymaps api 등)에 API를 배우는 대신 배우는 것이 좋습니다. 지도추출

"Mapstraction은 다양한 자바스크립트 매핑 API에 대한 공통 API를 제공하는 라이브러리입니다."

URL로 이동하여 일반 API를 배우는 것이 좋습니다.How-To도 꽤 많이 있습니다.

Answer 6

아직 라우팅에 대한 좋은 튜토리얼을 찾지 못했지만 읽어야 할 코드가 많이 있습니다.

Openstreetmap 데이터를 사용하는 GPL 라우팅 애플리케이션이 있습니다. 고스모어 Windows(+ 모바일) 및 Linux에서 작동합니다.동일한 데이터를 사용하는 흥미로운 애플리케이션이 많이 있지만 gosmore에는 몇 가지 멋진 용도가 있습니다. 예를 들어웹사이트와의 인터페이스.

라우팅의 가장 큰 문제는 잘못된 데이터이며, 충분한 양의 데이터를 얻을 수 없다는 것입니다.따라서 시도하고 싶다면 테스트를 매우 로컬로 유지하여 데이터를 더 잘 제어할 수 있습니다.

Answer 7

개념적인 관점에서 연못에 돌을 떨어뜨리고 잔물결을 관찰하는 것을 상상해 보세요.경로는 연못을 나타내고 돌은 시작 위치를 나타냅니다.

물론 알고리즘은 거리 n이 증가함에 따라 일정 비율의 n^2 경로를 검색해야 합니다.시작 위치로 이동하여 해당 지점에서 사용 가능한 모든 경로를 확인합니다.그런 다음 해당 경로의 끝에 있는 점 등을 재귀적으로 호출합니다.

경로를 이중으로 백업하지 않고, 이미 커버된 지점에서 경로를 다시 확인하지 않고, 너무 오래 걸리는 경로를 포기함으로써 성능을 향상시킬 수 있습니다.

또 다른 방법은 개미 페로몬 접근 방식을 사용하는 것입니다. 개미는 시작 지점에서 무작위로 기어 다니면서 냄새 흔적을 남기고, 이는 더 많은 개미가 주어진 경로를 통과하게 됩니다.시작점과 끝점 모두에서 (충분한) 개미를 보내면 결국 가장 강한 향기가 나는 경로가 가장 짧아집니다.이는 개미가 일정한 속도로 걷는다는 점을 고려하면 주어진 기간 동안 최단 경로를 더 많이 방문하게 되기 때문입니다.

편집 @ Spikie

연못 알고리즘을 구현하는 방법에 대한 추가 설명으로 필요한 잠재적인 데이터 구조가 강조 표시됩니다.

지도를 네트워크로 저장해야 합니다.이건 그냥 세트에요 nodes 그리고 edges 그들 사이에.세트 nodes 구성하다 route.가장자리는 두 개의 노드(아마도 둘 다 동일한 노드)를 결합하고 연관된 노드를 갖습니다. cost ~와 같은 distance 또는 time 가장자리를 통과합니다.모서리는 양방향이거나 단방향일 수 있습니다.아마도 단방향 노드를 갖고 노드 간 양방향 이동을 위해 두 배로 늘리는 것이 가장 간단할 것입니다(예:A에서 B로의 한 가장자리와 B에서 A로의 다른 가장자리).

예를 들어 위쪽을 가리키는 정삼각형으로 배열된 세 개의 기차역을 상상해 보세요.또한 중간에 각각 3개의 역이 더 있습니다.모서리는 인접한 모든 스테이션을 함께 연결하며 최종 다이어그램에는 더 큰 삼각형 내부에 역삼각형이 있습니다.

왼쪽 아래부터 시작하여 왼쪽에서 오른쪽으로 위쪽으로 A,B,C,D,E,F(상단에 F)로 노드에 레이블을 지정합니다.

모서리가 어느 방향으로든 횡단될 수 있다고 가정합니다.각 가장자리의 비용은 1km입니다.

좋아, 그래서 우리는 왼쪽 하단 A에서 상단 스테이션 F까지 경로를 지정하고 싶습니다.스스로를 두 배로 되돌리는 경로를 포함하여 가능한 경로가 많이 있습니다.ABCEBDEF.

우리에겐 일상적인 말이 있어요. NextNode, 이는 다음을 허용합니다. node 그리고 cost 이동할 수 있는 각 노드에 대해 자신을 호출합니다.

분명히 이 루틴을 실행하면 길이가 무한할 수 있는 경로(예: ABABABAB 등)를 포함하여 결국 모든 경로를 검색하게 됩니다.우리는 다음을 확인하여 이러한 일이 발생하지 않도록 합니다. cost.이전에 방문한 적이 없는 노드를 방문할 때마다 우리는 해당 노드에 대해 비용과 우리가 온 노드를 모두 넣습니다.기존 비용을 확인하기 전에 노드를 방문했고 더 저렴하다면 노드를 업데이트하고 계속합니다(반복).비용이 더 많이 든다면 노드를 건너뜁니다.모든 노드를 건너뛰면 루틴을 종료합니다.

대상 노드에 도달하면 루틴도 종료됩니다.

이렇게 하면 실행 가능한 모든 경로가 확인되지만, 결정적으로는 비용이 가장 낮은 경로만 확인됩니다.프로세스가 끝나면 각 노드는 대상 노드를 포함하여 해당 노드에 도달하는 데 가장 낮은 비용을 갖게 됩니다.

경로를 얻으려면 대상 노드에서 거꾸로 작업합니다.비용과 함께 우리가 온 노드를 저장했기 때문에 경로를 구축하면서 뒤로 홉하면 됩니다.이 예에서는 다음과 같이 끝납니다.

노드 A - (총) 비용 0 - 노드에서 없음
노드 B - 비용 1 - 노드 A에서
노드 C - 비용 2 - 노드 B에서
노드 D - 비용 1 - 노드 A에서
노드 E - 비용 2 - 노드 D에서 / 비용 2 - 노드 B에서(비용이 동일하므로 예외입니다)
노드 F - 비용 2 - 노드 D에서

따라서 가장 짧은 경로는 ADF입니다.

Answer 8

이 분야에서 일한 경험에 비추어 볼 때 A*는 일을 아주 잘 해냅니다.위에서 언급했듯이 Dijkstra의 알고리즘보다 빠르지만 여전히 유능한 프로그래머가 구현하고 이해하기에 충분히 간단합니다.

경로 네트워크 구축은 가장 어려운 부분이지만 일련의 간단한 단계로 나눌 수 있습니다.모든 도로를 확보하십시오.포인트를 순서대로 정렬합니다.서로 다른 도로의 동일한 지점 그룹을 교차점(노드)으로 만듭니다.노드가 연결되는 양방향(또는 일방통행 도로의 경우 한 방향)으로 호를 추가합니다.

A* 알고리즘 자체는 다음과 같습니다. Wikipedia에 잘 문서화되어 있습니다..최적화할 핵심 장소는 공개 목록에서 고성능 우선순위 대기열이 필요한 최상의 노드를 선택하는 것입니다.C++를 사용하는 경우 STL Priority_queue 어댑터를 사용할 수 있습니다.

속도, 거리 또는 기타 기준에 따라 네트워크의 다양한 부분(예: 보행자, 자동차, 대중 교통 등)을 통해 경로를 지정하도록 알고리즘을 사용자 정의하는 것은 매우 쉽습니다.네트워크를 구축할 때 사용 가능한 경로 세그먼트를 제어하고 각 세그먼트에 할당되는 가중치를 제어하는 ​​필터를 작성하면 됩니다.

Answer 9

각 순회 비용에 관해 또 다른 생각이 들지만 계산에 필요한 시간과 처리 능력이 증가합니다.

예: GoogleMaps에 따르면 내가 사는 곳에서 A지점에서 B지점으로 이동할 수 있는 방법은 3가지가 있습니다.Garmin 장치는 다음과 같은 3가지 경로를 각각 제공합니다. Quickest 경로 계산.이러한 각 경로를 여러 번 통과하고 평균을 낸 후에(분명히 시간, 카페인 양 등에 따라 오류가 있을 수 있음) 알고리즘이 높은 수준의 정확도를 위해 도로의 굴곡 수를 고려할 수 있다고 생각합니다. , 예를 들어 1마일의 직선 도로는 급커브가 있는 1마일의 도로보다 빠릅니다..실용적인 제안은 아니지만 확실히 매일 통근 결과를 개선하기 위해 사용하는 제안입니다.