[ZOL汽车电子] 大家好，【车仔你懂得】又双叒叕和大家见面了，上周我们一起畅谈了《高精度导航到底谁说了算》，大家都已经明确，未来无论是自动驾驶还是车联网的方方面面，都依赖于高精度地图。高精度地图，实现所有导航功能的先决条件。那么问题来了，路径规划是导航系统的基本能力之一，在地图数据上，我们的路径是如何被规划的呢？为何地图软件会知道那些路用时最短，那些路不会堵车呢？请大家随车仔一起看下去。
iOS游戏：我们相距十万光年
一、何谓路径规划？
路径规划是指导航中物体从起点移动到终点时在地图上做出路线选择行为。
一般情况下，路径规划主要功能是搜索起止点之间的最优路径。注意，路径规划并不一定寻找最短路径，路径规划有一套系统的衡量指标——时间最短、距离最短或者时间/距离综合等等。
因此，路径规划根据衡量标准，可以大致分为一下类型：
最短路径：只考虑时间，不考虑距离或其他因素；
最快路径：只考虑距离，不考虑时间或其他因素；
50/50路径：同时考虑时间和距离因素。
发展至今，导航路径规划已经不仅仅限于以上三类，随着技术发展逐渐能够满足人们多种个性化的导航需求，实际上生活中我们还会体验到如下的导航技术：
实际上，路径规划是根据一定需求在地图上进行路线选择。红绿灯少，是一种导航需求，随着移动互联网和大数据发展，这类导航需求将逐渐被满足，但是万变不离宗，所有导航需求，归根结底，还是在讨论距离和时间的问题。
二、我们导航路线是如何被规划出来的？
从过程上讲，导航路线的确定过程可以拆解成以下步骤：
输入：目的地、当前位置
计算：导航引擎在得到目的地与自身位置信息后，就需要根据地图，选择算法，计算出最优的路径。
输出：最优路径，或多条备选路径
按照算法，路径规划可以区分为静态路径规划和动态路径规划，静态路径规划算法的研究已经比较成熟，但目前在终端上的路径规划，当路程很长时，有时仍然存在资源利用率高，系统响应慢等问题。因此，目前我们日常基础到的基本上是动态路径规划。
那么，路径规划的算法有哪些？
实际上，路径规划有很多算法，在导航中，经常提到的就是Dijkstra算法和A*算法。
Dijkstra算法，中文译名为迪杰斯特拉算法，是由荷兰计算机科学家狄克斯特拉于1959 年提出的。从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra算法原理图
A*算法是导航路径计算中的标准算法。它比Dijkstra算法多了一个估算函数，若估算函数为0，A*算法也就退化为Dijkstra算法。
但在一般的嵌入式硬件上，基于性能和内存的限制与要求，不能直接使用A*算法计算路径。所以，也有很多改进的方法。
例如：
1. 应用地图数据分层的思想，简化地图中道路的网络结构，也能提高路径规划的性能；
2. 起始点与目的地的方向考虑进去，扩展时，有方向性进行扩展，可以大大减少计算量和存储空间；
3. 保存曾经的规划记录，也能达到快速检索的能力。Google的地图规划好像就采用的这种思想；
4.合理优化路网结构，降低参与路径计算的路网规模；
5.合理优化路径规划算法数据结构，提高路径计算效率；
实际上，平时中长距离的导航路径规划一般都是分层做的。譬如说你要从广州到北京，开车怎么走，当然不可能直接在路上规划吧，这样计算量太大了。比较理想的方法是，我先知道到底要经过多少城市，从每一个城市到下一个城市之间如何走才能用高速连接起来，你需要访问的数据就小得多。当最后约束到一个区那么大的地方的时候，直接上DP还是可以在可接受的时间内做出来的。
三、常见导航路径规划示例
1.打开地图应用，获取定位信息，自动获取出发地
如果定位位置，不是出发地，可以点击路线，手动输入出发地
2.定位成功后，在搜索栏输入目的地
确定目的地，一般地图会显示目的地周边信息，然后点选详细信息，确认导航到次目的地。
3.确定进行路线规划
多种路径可选，时间最少，路径最短，不堵车，无收费站，有ETC，少走高速，沿途有休息区，或者必过某个城市等等。图例展示的地图，有一个严重缺陷，就是缺少路况信息，进行实施调整，实际上，从北京到秦皇岛，选择路线3，走进京津高速，路况较好，不堵车，有可能比系统默认推荐的路线1早到家。
4.好了，林志玲语音为您导航
大家镇定点，我要开始导航了
编辑点评：
现在可以深刻理解，路线规划并不是给出最短路径。随着移动互联网的高速发展，诸如路况信息、本地化服务等需求，将逐渐成为未来路线规划的主要方向——个性化路线规划。不仅如此，路线规划，在未来的自动驾驶等一系列车联网应用场景当中将发挥着绝大作用。
推荐相关阅读：
更多汽车用品资讯请关注车品达人公众号或加入ZOL车品QQ群
别说话，扫我
推荐经销商