Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
559 views
in Technique[技术] by (71.8m points)

path finding - Is A* the best pathfinding algorithm?

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

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

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

question from:https://stackoverflow.com/questions/9511118/is-a-the-best-pathfinding-algorithm

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.

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).

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.

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.

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).

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)

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.

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)

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).

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).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...