How is greedy best first search different from A*?

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 of taking a path that does not bring us 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 O(bm), 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 O(bm). 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 O(bm) and a space complexity which can be polynomial. A* is complete, optimal, and it has a time and space complexity of O(bm). 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 Best First Search, 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*.