启发式算法和A*

启发式算法
一种定义为，一个基于直观和经验的构造的算法，对优化问题的实例能给出可接受的计算成本（计算时间，占用空间等） 内，给出一个近似最优解，该近似解于真实最优解的偏离程度不一定可以事先预计
另一种定义为，启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度

之前做移动机器人路径规划时候，其中的全局规划器可以选择dijkstra算法还是A算法，dijkstra应该很多人都了解了，下面主要介绍一下A算法

---

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。

公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。

这里的h(n)也就是启发式函数，一般来讲，这个h(n)取两节点间直线距离作为估价值，也就是

h(n) = sqrt((x1-x0)^2+(y1-y0)2)

然而当时在路径规划中是按照像素格子去