路線查找軟件是如何工作的？

Question

我問的是一個相當高的語言獨立水平。

路線查找（在Google地圖的「獲取路線」或GPS中找到）如何工作？我無法相信它會嘗試每一個可能的路線，並選擇最短/最快的路線。在給定起點和終點時，必須有一些邏輯方法來找到最佳路線。

任何形式的解釋都會很棒。

Answer 1

您應該閱讀shortest path problem和Dijkstra's algorithm。這兩個都用來確定兩點之間的路徑。谷歌地圖（和其他地圖應用程序）增加了額外的功能（如重新路由等），但這兩個概念是解決問題的基本前提。

Answer 2

一個很舊的文章，但我只是在尋找這個特殊的問題，我發現與解釋的好文章：http://blog.kdgregory.com/2011/12/how-gps-calculates-routes.html

基本上，它採用了A* search algorithm和路線分類（短航線，長航線，等等）來減少計算和存儲需求。