我正在使用这个 A 星 (A*) Pathfinder.java 在 Android 地图应用程序中计算和生成我的路线。https://github.com/xSmallDeadGuyx/SimpleAStar/blob/master/Pathfinder.java
当我使用A星Pathfinder.java来计算从地图上的一个点到另一个点的路线时，地图的尺寸很大，尺寸约为8000x8000。
A星探路者1乘1计算并在大地图（8000x8000）中使用，性能/计算速度相当低/慢（效率不高）。我尝试将计算量增加到 100×100，它工作正常，但绘制的路线路径在曲线上不平滑。
是否有办法使用 A 星算法或任何其他建议来提高路线计算性能来解决该问题？我需要帮助来解决这个问题。
执行：如果您正在寻找代码审查，请将工作代码发布到 CodeReview.StackExchange.com。他们可能会给您一些优化建议。
算法：以下是从算法角度考虑的几个因素。
首先，看看你的启发式。如果启发式估计太低，A* 就会退化为 Dikstra 算法。如果启发式估计太高，A* 就会退化为贪婪最佳优先搜索。具有可接受的启发式的 A* 位于中间的某个位置：它产生最优路径，但保持最优性会花费额外的计算时间。如果您愿意牺牲最优性，您可以选择一种启发式有时高估了距目标的距离。通过这样做，不能保证路径是最优的，但算法的贪婪性可以减少执行时间。
另外，如果世界是静态的（即布局已知a priori），您可以预先计算大量信息以帮助加快搜索速度。存在多种算法来完成此任务。Swamps是一种预先计算往往被不必要搜索的区域（即沼泽）的方法。除非进入或离开沼泽，否则不需要在运行时搜索区域。沼泽带来的加速在很大程度上取决于世界的地形；更具欺骗性的地图（即那些倾向于将搜索引向沼泽的地图）有很多好处。
另一种方法是使用分层寻路方法，例如HPA*。在像您的地图一样大的地图上（8000x8000，哎呀），这可能会显着提高性能。 HPA* 通过将区域分组为链接的本地集群并计算跨越集群边界的成本来进行操作a priori。然后，搜索在多个级别上进行：高层工作通过利用预先计算的成本来集中搜索，低层工作确定将使用的确切路径。
此外，还存在一些算法，可以通过利用运行时环境的特征来减少 A* 探索的节点数量。例如，跳转点搜索 (JPS)利用网格图（如您正在使用的网格图）经常表现出对称性的事实。如果您的世界中的移动成本恒定，JPS 可以“跳过”搜索中的许多节点，并显着减少搜索时间。我发现它将 A* 搜索时间缩短了 24 倍，其他人则看到了超过 30 倍的改进。
最后一点：据我所知，您正在使用 L1 路径（即 4 个基本方向）。通过预处理航路点之间的路径并使用微分启发式，您可能会获得很多收益。看本文有关 JavaScript 实现的演示和讨论here.
附加链接：
- JPS 的出色可视化效果
- JPS 的更多信息
- A* 的变体
- Amit 的 A* 页面：我所知道的最好的 A* 资源
- 如何加快 A* 博客文章的速度
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
