优化A* 算法运行时间python代码

说明:文章所示优化对某些地图有一定优化作用,运行速度可以提高2倍以上,但很大程度上会牺牲准确度,并且很多时候并不能用此方法加速运行,请在有一定A*算法代码基础上阅读。代码中piecemeal_matrix判断边界函数没有那么完美,只是提供一种参考,有兴趣的朋友可以和我一起改进。

A*算法在迷宫很复杂的情况下运行速度会很慢,甚至会和Dijkstra算法运行速度差不多,比如遇到如下这张复杂地图:

尽管只有约100*100像素,但是在我电脑上要运行10s左右时间才能计算出来(我电脑运行速度比较慢,不同电脑运行时间不同,文章测试环境均为同一台电脑)

遇到这种规则的方方正正的迷宫,我们可以运用(伪)图片缩小。不同于直接缩小图片,更可以说成对迷宫切片,防止图片缩小变糊。简单算法思路:把迷宫围墙边界作为转换后矩阵像素,类似于边缘检测,如下图x轴方向上的切片:

最终可以得到如下切片/缩小后图片:

最终结果对比:

优化前10s左右运行速度得出的图片:

优化后5s左右运行速度得出的图片:

切片优化python代码

优化前python代码

具体A*算法代码可见我的博客

发表评论

您的电子邮箱地址不会被公开。

浙ICP备2021019730-1    浙公网安备 33010902002953号
Copyright © 2022 PanCake