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?

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

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

推荐答案

简短的答案是肯定的，在某些情况下，A *不是解决问题的最佳算法.但是，有许多方法可以评估用于寻找解决方案的 best 算法的组成.

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.

如果您考虑使用 path-length 来表示 best ，即算法生成的最终路径有多长时间，则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)

如果在无启发式功能的情况下考虑使用最佳，则必须使用h(x,y)=0 forall states x and 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).

如果图形随时间变化(在机器人中并入移动障碍物时经常发生)的情况下，您正在考虑最佳，那么您需要一种专门设计的算法为此(例如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屋！