A* 算法优化思路

一 、程序上优化复杂度

A*算法的核心计算在于：

1. 从open和close表中进行查找
2. 从open表中搜索最小栅格
3. 从邻居中查找最小栅格

考虑从①②两点进行优化，传统的 A* 使用 vector<Point * >或者list<Point* >（Point为自己定义的点的结构体，包括坐标，FGH，父节点）

考虑到查找的复杂度较高，所以思考采用hash表进行查找，其查找的复杂度为O(1)，所以我们采用unordered_map对 openlist 和 closelist 进行备份，在查找时直接调用查找函数find或者count，由于unordered_map存在键值对应关系，可以设计为点的坐标的序号为key，即(point.x-1)*map.col+point.y，这样能确保唯一性；

考虑到排序的复杂度较高，快排也有O(nlog)的复杂度，所以使用priority_queue结构来存储openlist，即先前给出的代码中的 priority_queue<pair<int, Point*>, vector<pair<int, Point*>>, cmp> OpenList 。

注意：事实上，在我的代码中并没有对closelist进行哈希表备份，主要是懒得改了，如果读者有需要的话可以在Astar.h中进行修改，这样就不需要函数InCloseList了。

二 、 优化启发函数 F(N) = G(N)+W(N)*H(N)

参考文章： A* 算法及优化思路

在应用中就是动态加权，在H(N)较大时W(N)也应较大，当H(N)较小时W(N)也应较小，但这样修改的话，搜索出的路径并不是最优路径，但时间可以大大缩短；W(N)可以根据H(N)自行设定。

三、优化邻域

参考：依据象限搜索及混合预计耗费的A*改进算法，包含8邻域及24邻域的改进
根据目标点与当前点的位置关系将邻域缩小一角，由于我的代码是基于8邻域的没测试24邻域，在8邻域下修改为5邻域时间缩短1/3左右（在测试的时候我将地图扩大到1000点左右为了效果更加明显）

四、使用双向A*算法

并不是一个比较稳定的做法，后续如果使用到后再做补充
参考：双向A*搜索 | 双向启发式搜索（有几个关键问题做出了解答）

其他优化方法

参考文章：【路径规划】A*算法方法改进思路简析

个人A*优化后程序：

Arik/AStar (https://gitee.com/upcgyl/astar.git)