0
로드 그래프의 노드가 지정한 특정 값에 매핑하려는 차량의 입력 GPS 값이 수천 개 있습니다. 아래 이미지를 가져 가십시오. 각 노드 (A-F)에는 이전 에지에 대한 정보 (위도/경도는 물론)가 있습니다. 이 정보 중 일부를 입력 GPS 좌표의 각 GPS 지점과 일치시키고 싶습니다.GPS 네비게이션 알고리즘
도로 그래프 
지금까지 나는 그렇게 할 수 있어요,하지만 일부 가장자리 경우가 있습니다. 예를 들어 이미지를 가져 가면 노드 B에 도달했을 때 경로 BCD 또는 경로 BEF에있을 수 있다고 생각합니다. 노드가 멀리 떨어져있어서 우리가 입력으로 어떤 경로를 택했는지 알 수 없습니다. 도로가 단순히 2D 선이 아니기 때문입니다. 그들은 너비가 있으며 차량은 도로 가장자리에있을 수 있습니다. 도로의 폭을 알지 못하기 때문에 어느 도로가 있는지 확인하는 것은 어렵습니다. 따라서 노드 B에 도착하면 차량은 BC 또는 BE가 될 수 있습니다. 나중에 각 경로를 찾을 때까지 우리가 어디 있는지 알 수 없습니다.
우리가 단 하나의 옵션을 가질 때까지 각 경로를 탐색 할 수 있으므로 우리는 그 길에 있다는 것을 알고 있습니다. 모든 이전 노드의 데이터를 올바른 경로에 백필 할 수 있습니다. 그러나이 문제에 대한 알고리즘이 필요합니다.
코드에서 어떻게 처리 할 수 있습니까? 모든 교차로에서 DFS를 수행하고 어떤 경로가 차량에서 입력 지점을 포함하는 가장 높은 수의 가장자리를 가지고 있는지를 생각했습니다. 더 좋은 방법이 있습니까?
두 개의 도로가 평행하고 두 개 이상의 교차로에서 어떤 길을 가는지 확실하지 않은 경우 어떻게 될지 궁금합니다. 우리가 실현할 수없는 길이에 도달 할 때까지 그래프를 가로 지르는가? 또는 우리가 어느 도로에 있는지 아직 불확실한 하나 이상의 교차로를 가질 수는 없을 것입니다. 우리가 떨어져있는 경사로가 있고 두 개의 도로가 같은 방향이지만 다른 고도에있는 육교로 이어지는 경우를 상상해보십시오. 이 경우 우리는 갈라지기까지 어느 정도 시간이 걸릴 수 있습니다. – aaronbrodsan
수표를 일부 반지름으로 제한하고 이전 이동의 가중치를 고려하여이 반지름에서만 경로 변경을 고려해야합니다.당신이 우회전하면 (가장 강한 신호), 앞으로 나아갈 때 다른 병렬 경로로부터 충분히 강한 신호가 없을 때까지 현재 경로를 선호 할 가중치 함수를 구축 할 수 있습니다 (따라서 현재 경로가 길어질수록 더 힘들어집니다 (교차로가없는 한 오래!) 그런 신호가 발생하면 현재 경로를 병렬 경로로 변경합니다 (따라서 교차로뿐만 아니라 언제든지 분기가 가능합니다). –