在上文—— A*算法项目实践之二：基于障碍物避碰的栅格路径生成，我们得到了目标栅格路径，但发现每次计算路径所耗费的时间非常多，因此需要对A*搜索进行优化以提高其搜索速度，本文就笔者实际项目的一些经验来谈谈相关的方法，若有不对，请在评论区提醒笔者予以斧正 。
本项目基于VS2017，整个项目的代码以及上传到码云： A算法项目实践（正在更新中~）
参考文章：
1、A星算法原理及实现：
参考： https://blog.csdn.net/A_L_A_N/article/details/81392212
2、A星算法优化方法：
参考：
https://www.jianshu.com/p/b4ccd5b88487
https://zhuanlan.zhihu.com/p/80707067
https://www.cnblogs.com/xuuold/p/10366834.html
https://github.com/linyicheng1/motionPlan

A*搜索原理图：

（1）A*拓展节点时，需要根据当前栅格搜索周围的8个栅格，距离终点越远、障碍物越多，所需要搜索的栅格就越多，且对每个栅格都需要花费一定的计算时间；
（2）A*算法的时间复杂度为O(n^ 2)，n为问题的规模，例如本项目的n为91*360（可搜寻区域，栅格地图二维数组的行和列之积），最坏的情况时，本例的计算规模为(91*360)^2，因此计算量比较大。
举例来说，若没有任何优化，则下图搜索出路径所耗费的时间为111.687s（这个时间与笔者电脑性能有关）
这个时间太大以至于无法满足项目要求，因此需要对A*搜索进行优化。

回顾A*算法的流程，可以知道每个栅格的关键计算在与：
（1）从open和close表中的查找操作；
（2）从open表中搜索F最小栅格的操作。
理论上，（1）可以使用中的hash表查找（查找的效率为O(1)），（2）可以使用的堆搜索（搜索的效率为O(1)）。
具体来说，（1）需要使用hash表备份open、close表，在c++中即使用unordered_set来同时备份open、close表，并将所有的查找操作都替换为unordered_set的查找。
（2）需要使用最小堆（以栅格的F值排序）来备份open表，在c++中即使用priority_queue来备份opene表，则F最小栅格即为堆顶栅格，但是这种方法并不适用，因为A*算法有一个这样的步骤：

算法会调整open表栅格的F值，从而对priority_queue造成破坏，因此本项目代码并没有使用priority_queue来优化（2）。

启发函数的表达式为：

p表示某一栅格，g( p) 表示从起点 A移动到当前栅格p的移动耗费 (可沿斜方向移动)；
h( p)表示从指定的方格移动到终点 的预计耗费 (h( p) 有很多计算方法, 比如欧几里得距离）
w( p) 为h( p)的系数。
可以参考该文章理解启发函数：A* 算法及优化思路
改进启发函数实际是动态加权方法的应用，即实现w( p) 函数———其原则为在搜索开始时，快速到达目的地所在区域更重要；在搜索结束时，得到到达目标的最佳路径更重要。
也就是说，当h( p)较大时，w( p)也应该较大，此时A*算法会尽快向终点扩展，搜索速度很快但会错过最优路径；当h( p)较小时，w( p)也应该较小，此时A*算法会倾向于搜索最优路径而减慢搜索速度。
这是典型的以性能换速度（笔者自编）——搜索路径的速度越快但搜索出的路径却越差（以长度、转弯数做指标），下面通过2个实验可以清晰看到这一点。
例子1：w( p)为1不变，此时算法搜索出的路径的是最优路径，耗费时间：71.58 s

例子2：w( p)为1、3（h( p)较小时，w( p)为1；h( p)较大时，w( p)为3），此时路径劣于最优路径，耗费时间：0.64 s
由此可见，在放弃搜索最优路径的情况下，使用动态加权可以大大缩短A*搜索的时间。
本文的动态加权实现代码为：
注：代码中的w( p)类似一个分段函数，读者在自己项目中的动态加权需要多次测试来得到这个分段函数。

双向A*搜索原理图：

双向A*搜索算法简要过程：