Zom*_*bie 28 a-star breadth-first-search path-finding depth-first-search
通常认为A*是解决寻路问题的最佳算法.
当A*不是找到解决方案的最佳算法时,是否存在任何情况？
与BFS,DFS,UCS等相比,A*有多好？
And*_*ker 75
简短的回答是肯定的,有些情况下A*不是解决问题的最佳算法.但是,有很多方法可以评估什么构成了寻找解决方案的最佳算法.
如果您在从单一来源到多个目的地的多次搜索的性能方面考虑最佳,那么您应该考虑使用更合适的方法(Dijkstra算法).
如果您在性能方面考虑最好,那么在某些特殊情况下,DFS和BFS将明显优于A*.根据过去的经验,这适用于非常小的,几乎无关紧要的图形,但需要仔细测试和分析才能做出更强有力的陈述.
如果您在路径长度方面考虑最佳,即算法产生的最终路径的长度,那么A*等同于任何其他最优搜索算法.
如果您在完整性方面考虑最好,那么,如果存在这样的路径,算法是否总能找到目标的路径.如果是这样,则A*等同于任何其他完整算法(例如,广度优先搜索).
如果您在图中某些权重为负的情况下考虑最好,那么您将需要使用特殊算法来解决这些问题(例如bellman-ford)
如果你在没有启发式的情况下考虑最好,那么你必须依靠.在这种情况下,A*相当于最佳的第一次搜索.h(x,y)=0 forall states x and y
如果您在连续配置空间中与运动规划相关的案例中考虑得最好,那么A*可以在低维度上充分发挥作用,但搜索图形的存储在高维度上开始变得不切实际,并且使用概率完整算法的需求增加(例如RRT,Bi-RRT,RDT)
如果您在部分可观察图形的情况下考虑最佳,那么您在任何时候都只知道图形中所有可能的顶点和边缘的子集,并且您需要更改状态以观察更多的图形,然后您需要为此设计的替代算法(例如,Keonig的Lifelong Planning A*,LPA*,就是这样做的).
如果你在图表随着时间的推移而变化的情况下考虑得最好(当你合并移动的障碍物时机器人会经常发生这种情况),那么你需要一个为此设计的算法(例如Stentz的D*或Koenig和Likhachev的D*-Lite) .
小智 8
A*是特殊的,因为它可以通过播放它如何评估节点及其使用的启发式方法,变成其他路径寻找算法.你可以这样做来模拟Djikstra的,最好的第一搜索,广度优先搜索和深度优先搜索.
此外,通常很容易加快速度.例如,如果将可允许的启发式乘以常量c,则可以保证结果序列节点的成本不超过最优结果的c倍.
例如,请参阅 Ian Davis撰写的这篇精彩论文(为Star Trek Armada编写).A*与一组分层的航路点一起使用,这导致粗略的路径.然后,为了平滑路径,它们再次在包含路径上的节点和附近的节点的新生成图上运行A*,以获得更合理的路径.最后,他们运行橡皮筋以删除冗余节点.
所以,A*并不是解决所有问题的方法,但它是一种非常通用的工具.
Collaborative Diffusion是一个简单的替代方案（无需与启发式争论）。
当您需要不分青红皂白地瞄准一个目标或组中的任何成员时，它效果很好，在这种情况下可以比 A* 更快。它模仿“你正在变暖/变冷”。这分两步进行：
1.0我们使用浮点数）并使用标准扩散公式在地图上传播气味来创建的。这种气味随着从目标扩散开而变得越来越弱。一旦达到某种气味的弱点，我们就会停止传播。0.0，因为您无法移动到那里。它在足球等只有几个目标的游戏中效果最好（两支特工团队专门跟踪球和球门柱，导致只有 3 个影响图）或吃豆子（类似，多个代理跟踪 Pac）或有一个组合热图的游戏代表一组代理的质心，作为该军队中每个代理的平均值，以便一支军队可以接近“另一支军队”而不是“另一支军队中的特定单位”。这种普遍性可以提供提高的性能。
它最适合地图上有许多移动单元相当密集的情况，从而证明每次更新时必须在整个搜索空间中发生的广泛扩散是合理的，尽管每帧必须更新的地图数量会增加计算成本。