In what cases would BFS and DFS be more efficient than A* search algorithm?

Question

I've tested A* search against Breadth-First Searching (BFS) and Depth First Searching (DFS) and I find that fewer nodes are being expanded with A*.

I understand that A* expands paths that are already less expensive by using the heuristic and edge cost function.

In what cases would BFS and DFS be more efficient as compared to the A* search algorithm?

Answer 1

While A* uses a priority queue, BFS utilizes a queue. Usually, queues are much faster than priority queues (eg. Dequeue() is O(1) vs O(log n)). The benefit of A* is that it normally expands far fewer nodes than BFS, but if that isn't the case, BFS will be faster. That can occur if the heuristic used is poor, or if the graph is very sparse or small, or if the heuristic fails for a given graph.

BFS is particularly useful for unweighted graphs. If the graph is weighted, you need to use Dijkstra's Algorithm. This algorithm applies a priority queue, and as such should rarely be faster than A*, except in cases where the heuristic fails.

If you are looking to learn more about Artificial Intelligence then visit this Artificial Intelligence Course which will cover topics like Euclidean distance,Pearson Correlation Coefficient,Brute Force Algorithms,traveling salesman problem,NeuroEvolution of Augmenting Topologies,Fitness Function ,Resolution Algorithm,k-nearest neighbors algorithm ,Markvo Model ,Genetic Algorith,deep first iterative deeping and many more.