百度地图的搜索路线是怎么计算出来的呢，好高级啊！

Question

在百度地图上面选一个起点，选一个终点，就能自动帮我们计算规划路线，那么多路线，可以说是无限的路线，这些路线不可能是百度地图的人提前录入的吧，那么它是怎么计算出来的路线呢？

Answer 1

哈哈，问题很可爱。

路径检索服务器中，保存了全国采集到的路网数据，这些数据是人工开车采集的，比如我的老东家高德有4000多人的数据采集和加工团队。

道路的数据的存储结构就是加权图，权值是根据距离等因素计算的一个数值，当你将你的起点终点请求算路时候，服务器要做的就是进行图的最小权值路径检索，当然现代的算路算法有不同的权值，可以同时算出多条路线：路程最短，时间最快，不走高速等等。

如果好奇算路算法，可以去搜一下A*（A星）算法。这个算法是个基础算法，其他大部分算法都是A＊的改良型。

当然，服务器应该也会对热门和高频率算路结果进行多级缓存，减小计算压力（这个是我猜的）。

祝你好运。

Answer 2

A*启发式搜索算法

虽说有无限的路径，但其中很大一部分都是无用的。可以设置一个估值函数，当某一路线的估值大于一个阈值时，立刻退出。