浅谈Astar算法

讲实话,之前打比赛的时候只是把A*当作板子来用的,也就模板题K短路那种题会用到,比赛中几乎没见过,所以对他的原理其实一概不知

现在了解之后,其实原理感觉还是蛮简单

要我说的话A*算法就是dijkstra 算法的退化版,因为他不一定找出最优路径,但是却能在平衡效率和路径质量的前提下找出次优解

相比于求单源最短路算法dijkstra 算法,A*算法实际上就是修改了前者的贪心策略

dijkstra 算法的贪心仅仅基于当前点到起点的距离,加以松弛操作以达到得到最优解的目的

而A*算法呢,在贪心的时候不仅会考虑到起点的距离D[i],同时也会考虑当前节点到终点的距离H[i],需要注意的是这里的距离指的是曼哈顿距离而不是欧几里得距离。挑选下一个加入priority_queue 的目标是基于上面两者之和的大小,取其和之小者出队

这里的H[i]我们叫他启发函数,而P[i]=D[i]+H[i]我们称之为估价函数

由于引入了启发函数,A*寻路算法就不会走出那种看起来弯弯曲曲的很奇怪的路线,一定程度上减少了跑偏的概率,这在游戏寻路中是一个很重要的机制

在具体的算法实现上,A*算法只要寻到终点便会结束,因此他不一定能得到最短路径的最优解,但却能综合考虑各种因素得到视觉上最合理的规划路线

具体A*的板子站内某篇文章里有,这里就不贴了