EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
( @: {9 @ _9 F- Z
EDA365原创 作者：巢影字幕组
3 @! C# b5 \" o) P
: @2 d# ^$ C9 c7 r5 o7 K
8 ^5 Y% X* r( {" B4 _7 h* b, |9 o. o7 \3 b1 Z
5 O9 G$ ^7 _( q. T; T
5 w* s- q" z Q4 p5 a. X" W8 B
5 X% I. f1 t- C; A 今天我们来研究百度地图的导航功能。当代生活没有手机导航提供的路线规划、定位、引导等服务，可能你已经很难顺利的认清方向，走对路，为了在导航时给你指条明路，百度地图都做了什么？
. r0 Z3 y9 Z! l# y4 ?6 }1 E
' t. c6 r: P; u/ a; f; F3 E+ n, b
0 [8 r4 y8 f9 J3 G; @* h" i) e 一款导航软件是否好用，很大程度上取决于路线规划、准确定位和语音图像引导这三点。规划两点间的最佳路线是第一步。假设你在下午五点二十分要从北京西站去百度大厦，百度地图会推荐三条路线。其中路程最长的路线预测的驾驶时间却比另外两条路线要短得多。这些路线和时间是怎么算出来的？ 2 J h9 K! W0 W/ n+ n) }
首先得知道如何从茫茫路网中找到两点间的最短路线。1959年，荷兰计算机科学家迪杰斯特拉提出了一个经典算法。简单来说就是选择去往下一个点时总是尽可能选择路程最短的那个点。比如第一步从C出发就选择路程最短的A点，接着再通过与之前记录的路线对比长短、试错。一步步扩散到M点，再从记录下的路线，选取最短的那条。但这样找实在太慢了，要想快就得有方向的找路。比如A*算法。具体来说，同样从C点出发，除了要得知到相邻点的路程，还要知道这些点到终点的直线距离，两者之和最小的点就是下一步要去的地方，即H点。接着按同样规则到I点、D点，这时就会发现C-H-I-D 这个走法还不如最开始的C-D，于是就要倒回C点，排除C-H这个走法，选择路程距离第二段的C-G，如此A*就能很快找到后面的J、K、M，找到最短路线。 I; g W7 r0 a* ]9 o
9 b& O" t, i% w) ?4 J/ H8 M
在这个演示中，你就能很直观的看到A*相比迪杰斯特拉，试错的次数更少，大大提升了搜索的效率。需要注意，这只是简单的基础算法。对于更大更复杂的路网，像百度地图这样的软件，还会使用CH、CRP等优化算法，把路网划分成不同区域，并且增加缓存。比如从北京到广州时，就可以把京港澳高速这样的最短路径直接缓存到地图上。而不必频繁的计算中间的各种路线。不过光考虑路程最短还不够。就像开头的例子，路程短六公里，但时间却要多二十分钟。要想找到用时最短的路线，导航软件就必须要考虑拥堵情况。基于无数用户的行车数据，百度地图可以掌握各个路段的平均行车速度，结合路段的长度算出通行的平均时间。其中要注意，如果有人故意捣乱，拉着九十九台手机缓慢行走，是有可能让地图软件误以为空荡荡的一段路发生了大堵车。所以像百度地图还必须通过各种算法规则排除这些异常情况，更准确的反映实施拥堵情况。 # }- I0 U$ ~7 X. F* X
?6 e0 U0 P1 s& e
我们可以把各个路段的距离因素视为一种代价，把代价换成时间因素，再利用同样的算法就能得出驾驶时间最短的路线。但这还是不够，对于长距离导航地图软件，还要学会分析未来各个路段的路况变化。比如杭州主城区在晚高峰四点半到六点半会限行。如果你在六点出发，需要跨越限行区域，基于实时路况规划路线就要绕一大圈，而百度地图则会预测，当你到达限行边界时，是否已经过了限行时段。如果避开限行时段，就会规划更快的路线，让你少走十六公里，快二十二分钟。除了路程和时间，车道数量、限速要求、道路事故、收费站、高速路等因素都可以用于计算代价，而百度地图还让这种代价得以动态调整。因为不同人对代驾的感受并不一样，赶时间可以选择时间优先。不想过收费站的可以选择少收费。脾气不好，容易路怒的可以选择躲避拥堵。 ) N0 P8 O# c2 O2 ]
0 O# X R: m( Y% z
当然，路线规划只是基本操作，真正的考验还是在你上路之后。导航过程中的准确定位非常重要，比如上海西藏南路的这条隧道进入它。你的手机就会开始提醒你当前卫星信号弱，定位图标显示之后，而不熟悉路线的你失去导航帮助后。很可能在命运的分叉口做出错误的选择。别慌，即便失去卫星信号，百度地图还有智能定位算法帮助导航。简单来说，手机里的加速度计和陀螺仪可以采集自身X、Y、Z轴的移动加速度，和绕X、Y、Z轴旋转的角速度，X轴移动加速度大于零，意味着车辆加速，求加速度曲线下的面积就知道速度曲线，求速度曲线下的面积就知道路程曲线。同理，记录Z轴转动角速度就能算出车辆转向角度，结合路程曲线和转向角度曲线，实时还原车辆的行驶轨迹。知道路线也知道车在哪儿，但如果你不熟悉道路，还是很容易在各种复杂路口走错。这时图像语音的及时引导就尤为重要。百度地图为各种二叉路、十字路、乃至广州番禺区这种十一车道的复杂路口，都设计了直观的指示图、车道标识以及语音引导语音引导的时机和话术非常关键。比如一段需要连续转弯变道的路。你右转后立马提示变道，很可能让你反应不过来而走错路。所以百度地图会一开始就完整的提醒你先右转，再靠右走。有了心理准备。在转完后，你就能及时变道。当然如果你还是不放心手机导航的实力，最好的方法是去重庆。 像这座黄桷湾立交桥共五层、二十条匝道，足以让你得知自己的手机导航到底靠不靠谱。
+ _+ `1 y% x. ~/ L" A+ A
出品｜EDA365 作者｜巢影字幕组
) U5 M2 O' I+ o x. w1 U# J; r
1 {+ r1 S X2 q' y' e2 B- M8 R
注：本文为EDA365电子论坛原创文章，未经允许，不得转载
0 g6 i7 E! Q) v% ] | 
/1 
发表于 2021-4-30 13:47
收藏
淘帖
支持！
反对！