路径规划算法学习Day4-Astar算法

前言

路径规划算法学习Day3-基于栅格法的Dijkstra算法

1、A*（Astar）算法

1.1、原理

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。

公式表示为： f(n)=g(n)+h(n),
其中：
f(n) ：是从初始状态经由状态n到目标状态的代价估计，
g(n)：是在状态空间中从初始状态到状态n的实际代价，
h(n)：是从状态n到目标状态的最佳路径的估计代价。
对于路径搜索问题，状态就是图中的节点，代价就是距离

h(n)的选取保证找到最短路径（最优解的）条件，关键在于估价函数f(n)的选取（或者说h(n)的选取）。
我们以d(n)表达状态n到目标状态的距离，那么h(n)的选取大致有如下三种情况：
1）如果h(n)< d(n)到目标状态的实际距离，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
2）如果h(n)=d(n)，即距离估计h(n)等于最短距离，那么搜索将严格沿着最短路径进行， 此时的搜索效率是最高的。
3）如果 h(n)>d(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

A* 算法是在迪杰斯特拉算法的基础上进行改进的一种算法。与之不同的是，A算法是一种启发式搜索，不会像dijkstra算法一样对整个地图都进行遍历，A算法是有方向的遍历。

1.2、启发式搜索

启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。

这种搜索方式优点是搜索快，提高了效率，缺点就是得到的解有可能是次优解也有可能什么都得不到。一句话就是牺牲了精度得到了效率。

2、总结

Dijkstra与A* 对比
相同点：
两者都是以寻找最短路径为目的的算法。
不同点：
Dijkstra算法遍历的时候是对4周平等对待，没有区分的盲目进行遍历。
A* 算法是在迪杰斯特拉算法的基础上进行改进的一种算法。与之不同的是，A* 算法是一种启发式搜索，不会像dijkstra算法一样对整个地图都进行遍历，A* 算法是有方向的遍历。它会对周围各点进行评估，然后再进行搜索。

后续程序依旧是基于栅格进行，用matlab实现