What are the differences between A* and greedy best-first search?

Question

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?

Answer 1

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

Answer 2

According to the book Artificial Intelligence: A Modern Approach (3rd edition), by Stuart Russel and Peter Norvig, specifically, section 3.5.1 Greedy best-first search (p. 92)

Greedy best-first search tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by using just the heuristic function; that is, $f(n) = h(n)$.

In this same section, the authors give an example that shows that greedy best-first search is neither optimal nor complete.

In section 3.5.2 A* search: Minimizing the total estimated solution cost of the same book (p. 93), it states

A* search evaluates nodes by combining $g(n)$, the cost to reach the node, and $h(n)$, the cost to get from the node to the goal $$f(n) = g(n) + h(n).$$

Since $g(n)$ gives the path cost from the start node to node $n$, and $h(n)$ is the estimated cost of the cheapest path from $n$ to the goal, we have $f(n)$ = estimated cost of the cheapest solution through $n$.

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of $g(n) + h(n)$. It turns out that this strategy is more than just reasonable: provided that the heuristic function $h(n)$ satisfies certain conditions, A* search is both complete and optimal. The algorithm is identical to uniform-cost search except that A* uses $g + h$ instead of $g$

Answer 3

What you said isn't totally wrong, but the A* algorithm becomes optimal and complete if the heuristic function h is admissible, which means that this function never overestimates the cost of reaching the goal. In that case, the A* algorithm is way better than the greedy search algorithm.