当前位置: 首页> 健康> 科研 > A* 算法优化思路

A* 算法优化思路

时间:2025/7/11 9:34:20来源:https://blog.csdn.net/qq_45770364/article/details/141811483 浏览次数:0次

一 、程序上优化复杂度

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了。

个人A*改进后程序:
Arik/AStar (https://gitee.com/upcgyl/astar.git)

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

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

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

三、使用双向A*算法

后续如果使用到后再做补充

参考文章:双向A*搜索 | 双向启发式搜索
(写的不错,有几个关键问题做出了解答)

其他优化方法

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

关键字:A* 算法优化思路

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: