Open Mind Tree

According to the book, the Greedy Best-First search algorithm has also been called greedy search orbest-first search by other authors.

The best-first search part of the name means that it uses an evaluation function to select which node is to be expanded next. The node with the lowest evaluation is selected for expansion because that is thebest node, since it supposedly has the closest path to the goal (if the heuristic is good). Unlike A* which uses both the link costs and a heuristic of the cost to the goal, greedy best-first search uses only the heuristic, and not any link costs. A disadvantage of this approach is that if the heuristic is not accurate, it can go down paths with high link cost since there might be a low heuristic for the connecting node.

The greedy best-first search algorithm is incomplete without cycle checking. If a closed list is used to not visit nodes which have already been visited, then the search is complete. The algorithm is also not optimal. Since the algorithm is only based on the heuristic value, if the heuristic is not exactly equal to the actual cost, it might go down a less optimal path than the ideal one.

The greedy best-first search algorithm is O(b^m) in terms of space and time complexity. (Where b is the average branching factor (the average number of successors from a state), and m is the maximum depth of the search tree.) A good heuristic can bring this down substantially for the common case, but all nodes are visited in the worst case.

As an example of the algorithm, I will use it to find the path from Start to Goal in the graph below.

First, add the Start node to the fringe.

Visit the Start node and add its neighbors to the fringe.

Visit node A and add its neighbors to the fringe.

Now there is a choice on which node to visit next. Because we are using greedy best-first search, the node with the lowest heuristic is used. If this solution was implemented, a priority queue would be used for the fringe, so it would always return the node with the lowest heuristic. Since node D has the lowest heuristic value, we visit at that node and add its neighbors to the fringe.

Now, since node E has the lowest heuristic in the fringe, it is visited at and its neighbors are added to the fringe.

Finally, since the Goal is in the priority queue with a heuristic of 0, it is visited and a path to the goal is found.

The path found from Start to Goal is: Start -> A -> D -> E -> Goal. In this case, it was the optimal path, but only because the heuristic values were fairly accurate.