iPhone 용 Dijkstra 알고리즘

StackOverflow https://stackoverflow.com/questions/876623

  •  22-08-2019
  •  | 
  •  

문제

SDK 3.0 이후 iPhone에서 GPS 기능을 쉽게 사용할 수는 있지만 Google지도를 사용하는 것은 명시 적으로 금지되어 있습니다. 이것은 두 가지 의미가 있다고 생각합니다.

  1. 당신은지도를 직접 제공해야합니다
  2. 가장 짧은 경로를 직접 계산해야합니다.

나는 가장 짧은 경로를 계산하면 수학자들이 오랜 세월 동안 당황했지만 Tom Tom과 Google은 모두 훌륭한 일을하고 있으므로 문제가 해결 된 것으로 보입니다. '그물을 찾아서 수학자가 아니라 dijkstra 알고리즘. iPhone의 맵과 같은 앱 에서이 알고리즘을 성공적으로 사용한 사람이 있습니까? 나/커뮤니티와 기꺼이 공유 하시겠습니까? 이것이 올바른 접근법일까요, 아니면 다른 옵션입니까? 고려해 주셔서 감사합니다.

도움이 되었습니까?

해결책

Dijkstra의 알고리즘은 모든 노드 (단일 시작 노드에서)에 대한 가장 짧은 경로를 찾는 것입니다. 게임 프로그래머는 A*와 같은 지시 된 검색을 사용합니다. 여기서 dijkstra가 시작 위치에 가장 가까운 노드를 먼저 처리하는 경우 a*는 끝 위치에 가장 가까운 것으로 추정됩니다.

이것이 작동하는 방식은 주어진 위치에서 끝점까지 저렴한 "추정"기능을 제공하는 것입니다. 좋은 예는 새가 얼마나 멀리 거기에 도착할 것인지입니다. a*는 이것을 각 노드의 시작과 현재 거리에 추가 한 다음 가장 짧은 경로에있는 것처럼 보이는 노드를 선택합니다.

추정이 좋을수록 좋은 길을 찾는 데 걸리는 시간이 짧습니다. 이 시간이 여전히 너무 길면 간단한지도에서 경로 찾기를하고 다른 맵에서 다른 맵에서 찾을 수있어 간단한지도에서 찾은 장소 사이의 경로를 찾을 수 있습니다.

업데이트많은 검색 후, 나는 *에 관한 기사 당신이 읽을 수 있도록

다른 팁

Tom Leys가 말했듯이 (그의 게시물에 대해 언급하지만 담당자가 부족하기 때문에) Dijkstra의 알고리즘은 실제 매핑에 유용 할 것이라고 생각하지 않습니다. 단일 시작점이 필요하기 때문입니다. 출발점이 변경되면 모든 것이 다시 계산되어야하며 iPhone과 같은 장치에서는 상당히 큰 데이터 세트를 위해 이것이 매우 느리게 생각할 것입니다.

Dijkstra의 알고리즘은 N 노드의 경우 O (M log n) 및 M 모서리 (단일 경로의 경우)이며 네트워크 라우팅에 사용하기에 충분히 효율적입니다. 이는 일회성 계산에 사용되기에 충분히 효율적임을 의미합니다.

간략하게 Dijkstra의 알고리즘은 다음과 같습니다.

Take the start node
Assign it a depth of zero
Insert it into a priority queue at its depth key

Repeat:
    Pop the node with the lowest depth from the priority queue
    Record the node that you came from so you can track the path back
    Mark the node as having been visited
    If this node is the destination:
        Break
    For each neighbour:
        If the node has not previously been visited:
            Calculate depth as depth of current node + distance to neighbour
            Insert neighbour into the priority queue at the calculated depth.

Return the destination node and list of the nodes through which it was reached.

대중의 믿음과는 달리, Dijkstra의 알고리즘은 반드시 가장 짧은 경로 계산기 일 필요는 없지만이를 수행하도록 조정할 수 있습니다.

당신은 거리의 그래프와 교차로 사이의 거리와 교차로를 가져와야합니다. 이 데이터가 있으면 Dijkstra 알고리즘을 사용하여 가장 짧은 경로를 계산할 수 있습니다.

Tomtom이 'IQ 경로'라고 부르는 기술을 보면 시간당 실제 속도와 여행 시간 당 시간당 도로 당 시간당 이동 시간을 측정합니다. 이것은 도착 시간을 더 정확하게 만듭니다. 따라서 예상 도착 시간은 더 사실 기반입니다 http://www.tomtom.com/page/iq-routes

A* 알고리즘을 사용하여 경로를 계산하는 것은 오프라인 맵 데이터가있는 iPhone에서 충분히 빠릅니다. 나는 이것을 상업적으로 수행 한 경험이 있습니다. Wikipedia에 문서화 된대로 A* 알고리즘을 사용하고 도로 네트워크를 메모리에 유지하고 재사용합니다. 로드되면 스페인이나 캐나다 서부 절반과 같은 넓은 지역에서도 라우팅이 실제로 즉각적입니다.

나는 OpenStreetMap 또는 ElsWhere의 데이터를 가져 와서 동일한 ID와 함께 지점을 공유하는 두 개의 도로가 결합된다고 가정 할 때 (아는 사람들에 따라 수행하는 올바른 방법)를 가정하면 지시 된 그래프로 변환합니다. 예상 속도에 따라 다른 유형의 도로에 무게를 할당하고 도로의 일부가 일방 통행이라면 단일 아크 만 만듭니다. 양방향 도로는 각 방향으로 하나씩 두 개의 호를 얻습니다. 그것은 위험한 회전을 방지하고 라우팅 제한을 구현하기 위해 임시 코드를 제외하고는 거의 모든 것입니다.

살펴보십시오 CloudMade. 현재 위치를 기반으로 탐색 할 수있는 iPhone 및 iPad 용 무료 서비스를 제공합니다. 오픈 스트리트 맵에 제작되었으며 자신만의지도 스타일을 만드는 것과 같은 멋진 기능이 있습니다. 때때로 조금 느리지 만 완전히 무료입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top