A* 是最好的寻路算法吗? [英] Is A* the best pathfinding algorithm?

问题描述

一般都说A*是解决寻路问题的最佳算法.

It is generally said that A* is the best algorithm to solve pathfinding problems.

是否存在 A* 不是 最佳求解算法的情况?

Is there any situation when A* is not the best algorithm to find solution?

与 BFS、DFS、UCS 等相比，A* 有多好?

How good is A* compared to BFS, DFS, UCS, etc?

推荐答案

简短的回答是肯定的，在某些情况下，A* 不是解决问题的最佳算法.但是，有多种方法可以评估什么构成了最佳 算法以寻找解决方案.

The short answer is yes, there are situations in which A* is not the best algorithm to solve a problem. However, there are a number of ways to assess what constitutes the best algorithm for finding a solution.

如果您在从单一来源到多个目的地的多次搜索的性能方面考虑最佳，那么您应该考虑使用更合适的方法(Dijkstra 算法).

If you are considering best in terms of performance of multiple searches from a single source to many destinations, then you should consider using a more suitable approach (Dijkstra's algorithm).

如果您在性能方面考虑最佳，那么在某些特殊情况下，DFS 和 BFS 的性能将明显优于 A*.根据过去的经验，这种情况发生在非常小的、几乎微不足道的图上，但需要仔细测试和分析才能做出更有力的陈述.

If you are considering best in terms of performance, then in some special cases DFS and BFS will significantly outperform A*. From past experience, this occurs for very small, almost trivial graphs, but would require careful testing and profiling to make a stronger statement.

如果您在路径长度方面考虑最佳，即算法生成的最终路径的长度，那么 A* 等效于任何其他最优搜索算法.

If you are considering best in terms of path-length, that is how long the final path produced by the algorithm is, then A* is equivalent to any other optimal search algorithm.

如果您在完整性方面考虑最佳，也就是说，如果存在这样的路径，算法是否总是会找到通往目标的路径.如果是，则 A* 等价于任何其他完整算法(例如广度优先搜索).

If you are considering best in terms of completeness, that is, will the algorithm always find a path to the goal if such a path exists. If so, then A* is equivalent to any other complete algorithm (for example, breadth-first-search).

如果您正在考虑最佳，因为图中的某些权重为负，那么您将需要使用特殊算法来解决这些问题(对于示例 bellman-ford)

If you are considering best in cases where some of the weights in the graph are negative, then you will need to use a special algorithm to solve those problems (for example bellman-ford)

如果您在没有可用的启发式的情况下考虑最佳，那么对于所有状态 x，您必须依靠 h(x,y)=0和 y.在这种情况下，A* 相当于最佳优先搜索.

If you are considering best in cases where the no heuristic is available then you must fall back on h(x,y)=0 forall states x and y. In this case A* is equivalent to best first search.

如果您在连续配置空间中考虑与运动规划相关的最佳情况，那么 A* 可能在低维中充分工作，但搜索图的存储开始在高维度变得不切实际，并且需要使用概率完备算法增加(例如 RRT, Bi-RRT, RDT)

If you are considering best in cases related to motion planning in continuous configuration spaces, then A* may work adequately in low dimensions, but storage of the search graph starts to become impractical at high dimensions, and the need to use probabilistically complete algorithms increases (for example RRT, Bi-RRT, RDT)

如果您在图部分可观察的情况下考虑最佳，那么您在任何时候都只知道图中所有可能的顶点和边的子集，并且您需要更改状态以观察更多图形，那么您需要为此设计的替代算法(例如，Keonig 的终身规划 A*、LPA* 正是这样做的).

If you are considering best in cases where the graph is partially observable, you only know a subset of all the possible vertices and edges within the graph at any time, and you need to change state to observe more of the graph, then you need an alternative algorithm designed for this (for example, Keonig's Lifelong Planning A*, LPA*, does exactly this).

如果您正在考虑 best 图表随时间变化的情况，当您合并移动障碍物时，这种情况在机器人技术中经常发生，那么您需要一种经过设计的算法为此(例如 Stentz 的 D* 或 Koenig & Likhachev 的 D*-Lite).

If you are considering best in cases where the graph changes over time, which occurs frequently in robotics when you incorporate moving obstacles, then you need an algorithm which is designed for this (for example Stentz's D* or Koenig & Likhachev's D*-Lite).

这篇关于A* 是最好的寻路算法吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！