gps - 寻路软件是如何工作的？

Question

我的要求很高，与语言无关。

路线查找（如在 Google 地图“获取路线”或 GPS 中找到的）如何工作？我不敢相信它会尝试每条可以想象的路线并选择最短/最快等。必须有某种合乎逻辑的方法来找到给定起点和终点的最佳路线。

任何形式的解释都会很棒。

Answer 1

您应该阅读最短路径问题和Dijkstra 算法。这两者都用于确定两点之间的路径。谷歌地图（和其他地图应用程序）添加了额外的功能（例如重新路由等），但这两个概念是如何解决问题的基本前提。

Answer 2

一个非常古老的帖子，但我只是在寻找这个特定的问题，我发现了一篇很好的文章，里面有解释：http ://blog.kdgregory.com/2011/12/how-gps-calculates-routes.html

基本上，它使用A* 搜索算法和路线分类（短路线、长路线等）来减少计算和内存需求。