3
$\begingroup$

What are the differences between the A* algorithm and the greedy best-first search algorithm? Which one should I use? Which algorithm is the better one, and why?

$\endgroup$
3
$\begingroup$

Both algorithms fall into the category of "best-first search" algorithms, which are algorithms that can use both the knowledge acquired so far while exploring the search space, denoted by $g(n)$, and a heuristic function, denoted by $h(n)$, which estimates the distance to the goal node, for each node $n$ in the search space (often represented as a graph).

Each of these search algorithms defines an "evaluation function", for each node $n$ in the graph (or search space), denoted by $f(n)$. This evaluation function is used to determine which node, while searching, is "expanded" first, that is, which node is first removed from the "fringe" (or "frontier", or "border"), so as to "visit" its children. In general, the difference between the algorithms in the "best-first" category is in the definition of the evaluation function $f(n)$.

In the case of the greedy BFS algorithm, the evaluation function is $f(n) = h(n)$, that is, the greedy BFS algorithm first expands the node whose estimated distance to the goal is the smallest. So, greedy BFS does not use the "past knowledge", i.e. $g(n)$. Hence its connotation "greedy". In general, the greedy BST algorithm is not complete, that is, there is always the risk to take a path that does not bring to the goal. In the greedy BFS algorithm, all nodes on the border (or fringe or frontier) are kept in memory, and nodes that have already been expanded do not need to be stored in memory and can therefore be discarded. In general, the greedy BFS is also not optimal, that is, the path found may not be the optimal one. In general, the time complexity is $\mathcal{O}(b^m)$, where $b$ is the (maximum) branching factor and $m$ is the maximum depth of the search tree. The space complexity is proportional to the number of nodes in the fringe and to the length of the found path.

In the case of the A* algorithm, the evaluation function is $f(n) = g(n) + h(n)$, where $h$ is an admissible heuristic function. The "star", often denoted by an asterisk, *, refers to the fact that A* uses an admissible heuristic function, which essentially means that A* is optimal, that is, it always finds the optimal path between the starting node and the goal node. A* is also complete (unless there are infinitely many nodes to explore in the search space). The time complexity is $\mathcal{O}(b^m)$. However, A* needs to keep all nodes in memory while searching, not just the ones in the fringe, because A*, essentially, performs an "exhaustive search" (which is "informed", in the sense that it uses a heuristic function).

In summary, greedy BFS is not complete, not optimal, has a time complexity of $\mathcal{O}(b^m)$ and a space complexity which can be polynomial. A* is complete, optimal, and it has a time and space complexity of $\mathcal{O}(b^m)$. So, in general, A* uses more memory than greedy BFS. A* becomes impractical when the search space is huge. However, A* also guarantees that the found path between the starting node and the goal node is the optimal one and that the algorithm eventually terminates. Greedy BFS, on the other hand, uses less memory, but does not provide the optimality and completeness guarantees of A*. So, which algorithm is the "best" depends on the context, but both are "best"-first searches.

Note: in practice, you may not use any of these algorithms: you may e.g. use, instead, IDA*.

$\endgroup$
  • $\begingroup$ > "A* is also complete (unless there are infinitely many nodes to explore in the search space)" Is this qualification necessary? If there exists a finite path from start to goal, A* will find it in finite time. Perhaps you are thinking of DFS? $\endgroup$ – Gus Jun 7 at 16:28
  • $\begingroup$ @Gus A* is not guaranteed to be complete (that is, to find a solution) if there are infinitely many nodes. I just wanted to make it explicit. $\endgroup$ – nbro Jun 7 at 16:39
  • $\begingroup$ I am disagreeing with that statement. Do you agree that BFS is complete even if there are infinitely many nodes? $\endgroup$ – Gus Jun 7 at 16:46
  • $\begingroup$ @Gus No, I don't agree that BFS is complete (in finite time) if there are infinitely many nodes. What if there are infinitely many nodes on the each layer (not necessarily infinitely many layers)? $\endgroup$ – nbro Jun 7 at 16:49
  • $\begingroup$ Thanks for clarifying. I have suggested an edit to clarify the answer. As it is written, it misleads a reader into believing A* is not complete on infinite graphs. In fact it's not complete on graphs with an infinite branching factor. But on infinite graphs with finite branching factor, it is complete. Though that point is technically correct, it's a bit obvious. Not only will A* and BFS be incomplete on these graphs, but the algorithm will loop on the very first iteration that expands a node with an infinite number of children. $\endgroup$ – Gus Jun 8 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.