你懂的导航 [车仔你懂得]导航路径规划知多少?

大家好。又遇见你了。上周我们谈了“高精度导航谁说了算”。大家都明确表示，未来无论是自动驾驶还是车联网各方面都要靠高精度地图。高精度地图是所有导航功能的先决条件。那么问题来了。路径规划是导航系统的基本功能之一。我们的路径是如何在地图数据上规划的？为什么地图软件知道哪些道路时间最短，哪些道路不会被堵塞？请和司机一起看。

IOS游戏:我们相隔10万光年

1.什么是路径规划？

路径规划是引导飞行中的物体从起点移动到终点时在地图上进行路径选择的行为。

一般来说，路径规划的主要功能是搜索起点和终点之间的最佳路径。请注意，路径规划不一定要寻找最短路径。路径规划有一套系统的度量指标——最短时间、最短距离或综合时间/距离等。

因此，根据测量标准，路径规划可以大致分为以下几种类型:

最短路径:只考虑时间，不考虑距离等因素；

最快路径:只考虑距离，不考虑时间或其他因素；

50/50路线:考虑时间和距离。

到目前为止，导航路径规划已经不限于以上三类。随着技术的发展，逐渐可以满足人们的各种个性化导航需求。事实上，我们将在生活中体验以下导航技术:

其实路线规划就是按照一定的要求在地图上选择路线。红绿灯少，是一种导航需求。随着移动互联网和大数据的发展，这种导航需求将逐渐得到满足。但是所有的导航需求还是在讨论距离和时间。

二、我们的航行路线是如何规划的？

在流程上，导航路线的确定过程可以分解为以下步骤:

输入:目的地、当前位置

计算:导航引擎获得目的地和自身位置信息后，需要根据地图选择算法，计算最优路径。

输出:最佳路径，或多个备选路径

根据算法，路径规划可以分为静态路径规划和动态路径规划。静态路径规划算法的研究已经比较成熟，但目前距离较远时，仍然存在资源利用率高、系统响应慢等问题。所以目前我们的日常基础基本都是动态路径规划。

那么，路径规划的算法有哪些呢？

其实路径规划的算法有很多。导航中经常提到Dijkstra算法和A*算法。

Dijkstra算法，中文翻译为Dijkstra算法，由荷兰计算机科学家Dijkstra于1959年提出。从一个顶点到其他顶点的最短路径算法解决了有向图中的最短路径问题。Dijkstra算法的主要特点是从起点向终点向外扩展。

Dijkstra算法示意图

A*算法是导航路径计算中的标准算法。它比Dijkstra算法多了一个估计函数。如果估计函数为0，A*算法将退化为Dijkstra算法。

但是在一般的嵌入式硬件上，由于性能和内存的限制和要求，A*算法不能直接用来计算路径。所以，有很多方法可以改善。

例如:

1.利用地图数据分层的思想简化地图中道路的网络结构，也可以提高路径规划的性能；

2.考虑起点和终点的方向，在扩展时，扩展是有方向性的，可以大大减少计算量和存储量空；

3.保存以前的规划记录，也实现了快速检索的能力。谷歌的地图规划似乎采用了这种思路；

4.合理优化路网结构，减少路网参与路线计算的规模；

5.合理优化路径规划算法的数据结构，提高路径计算效率；

事实上，通常情况下，远程导航路径规划是分层进行的。比如你想从广州开车去北京，当然不可能直接在路上规划。这是太多的计算。理想的方式是我知道我要经过多少个城市，从每个城市到下一个城市如何高速连接。您需要访问的数据要小得多。当最终约束到面积那么大的地方，直接DP还是可以在可以接受的时间内完成的。

三、常见导航路径规划实例

1.打开地图应用，获取定位信息，自动获取出发地点

如果地点不是出发地点，可以点击路线，手动输入出发地点

2.定位成功后，在搜索栏中输入目的地

要确定目的地，一般地图会显示目的地的周边信息，然后点击详细信息确认导航到二级目的地。

3.确定路线规划

可以选择多种路线，时间最少，路线最短，不堵车，不设收费站，ETC，不太高速，沿途休息区，或者某个城市等。图例中显示的地图有一个严重的缺陷，就是缺少路况信息，需要调整。其实从北京到秦皇岛，选择3号线，步行进京津高速，路况好，不堵车，默认可以比系统推荐的1号线早到家。

4.好的，林志玲的声音会指引你

大家冷静。我要开始导航了