导航算法

1、路径规划的算法有哪些？

路径规划有很多算法，在导航中，经常提到的就是A*和Dijkstra算法。A*算法是导航路径计算中的标准算法。它比Dijkstra算法多了一个估算函数，若估算函数为0，A*算法也就退化为Dijkstra算法。

2、两种算法的区别

• Dijkstra 算法是全局遍历，确保运算结果一定是最短路径。
  A* 算法是策略寻路，不保证一定是最短路径。
  
• Dijkstra 需要载入全部数据，遍历搜索。（也可以分层计算，分层载入）
  A* 算法可以根据需要，分部分块载入地图数据。
  

3、算法的改进

但在一般的嵌入式硬件上，基于性能和内存的限制与要求，不能直接使用A*算法计算路径。所以，也有很多改进的方法。
例如：

1. 应用地图数据分层的思想，简化地图中道路的网络结构，也能提高路径规划的性能。
   
2. 起始点与目的地的方向考虑进去，扩展时，有方向性进行扩展，可以大大减少计算量和存储空间。
   
3. 保存曾经的规划记录，也能达到快速检索的能力。Google的地图规划好像就采用的这种思想。

4、路径规划考虑的要素

• 最短路径：只考虑时间，不考虑距离或其他因素
  
• 最快路径：只考虑距离，不考虑时间或其他因素
  
• 同时考虑时间和距离因素：50/50的路径规划方法。

5、Dijkstra算法

戴克斯特拉算法，这个算法的时间复杂度是 O(N²)
举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0