我有一個車輛的數千個輸入GPS值，我想要映射到道路圖上節點給定的特定值。拿下面的圖片。每個節點（A-F）都有關於連接到它的上一個邊緣的信息（以及經度/緯度）。我想在我的輸入GPS座標中將這些信息與每個GPS點相匹配。GPS導航算法
路圖 
到目前爲止，我能做到這一點，但也有一些邊緣情況。以圖像爲例，當我們到達節點B時，我們認爲我們可能在路徑BCD或路徑BEF上。直到節點分開得足夠遠以至於我們知道我們在輸入中採用了哪條路線。這是因爲道路不僅僅是一條二維線。他們有寬度，車輛可能在路邊。確定它所在的道路是困難的，因爲我們不知道道路的寬度。所以，當我們到達節點B時，車輛可以在BC或BE之間。直到後來每條路都不知道我們在哪裏。
這就是說，我們可以遍歷每條路線，直到我們只有一個選項，因此我們知道我們在那條路上。我們可以在正確的路線上回填所有先前節點的數據。然而，我有問題提出了一個算法。
我該如何處理代碼？我曾想過在每個交叉點做一個DFS，並找出哪條路徑中包含來自車輛的輸入點的邊數最多。有沒有更好的辦法？
我會首先將gps輸入映射到節點，但在映射操作期間，每個節點都應該向父節點傳播一個count++（並且如果循環是可能的，則檢測循環）。只能傳播到（但不包含）交點。比你可以沿着路徑走，並在十字路口採取最大的價值，並走這條道路。
最後你會喜歡的東西（例如）：
0 -> 0 -> 4 -> 3 -> 1
|
---> 2 -> 1 -> 0
在第二個節點，你會選擇「上」的方向。什麼是重要的，你只傳播到指定的地方，因爲你總是要到達十字路口，所以不需要進一步傳播。
如果我正確地理解了這個問題，一旦到達節點B，您對前面的路徑會有一些不確定性。然而，在到達節點C或E時，前向路徑現在已知，直到具有大於1的outdegree的下一個節點。
然後，我認爲你只需跟蹤你的路徑，直到一個交點並列出與該交點相鄰的所有節點（類似於BFS）。檢查可能的節點列表，一旦你到達一個添加到當前路徑。此時，您將知道您所在的道路，並可預測前進路線，直至下一個路口，重複直至您的目的地。
問題在於，到達節點C和E，我們仍然不知道我們在哪條路上，這是爲什麼呢？這是因爲道路有寬度，不是二維線，如果車輛在BCD的道路上，但足夠靠近我們的邊緣算法不知道它是否實際上在BCD上，而是可能在BEF上，當你檢查BEF道路時，我們看到車輛最終離BCD太遠（實際上是它），然後我們可以回溯並採取正確的道路BCD。 – aaronbrodsan
我的問題是如何實現這個專業版perly在代碼中。 – aaronbrodsan
這可能有用，但我很好奇如果兩條道路平行並且我們不確定我們在多個交叉路口上走什麼路。我們是否遍歷圖形直到達到不可行的長度？或者是否我們不可能有多於一個的交叉路口，我們仍然不確定我們正在走什麼路。想象一下，我們有一個斜坡的情況，它會導致一條立交橋，兩條道路在同一方向，但高度不同。在這種情況下，我們可能會有一段時間纔會分歧。 – aaronbrodsan
您應該將支票限制在某個半徑範圍內，並且只考慮此半徑內的路徑更改，並考慮先前搬移的重量。或多或少，如果你右轉（最強的信號），並且在你向前移動之後，你可以建立一個權重函數，這將有利於當前路徑，直到沒有足夠強的信號從另一條平行路徑（更長的電流路徑 - 更難將它改變爲平行的（只要沒有交點！）如果發生這種信號，則將當前路徑改爲平行路徑（這樣不僅可以在十字路口發散，而且可以在任何時候發生 –