Greedy best-first search (GBFS) is a heuristic search algorithm. The premise is to expand the node that seems closest to a goal first, so the frontier is a priority queue ordered by each node’s heuristic value.
Some key characteristics:
- GBFS is not complete.
- By counterexample, consider a cycle where the edges are better than every other outgoing edge. So the algorithm will push the better edges to the front of the priority queue every time.
- Or alternatively, a cycle where edges don’t go towards the goal state, but they’re better than every other edge in the graph.
- GBFS is not optimal. The heuristic may underpredict a certain node such that it produces a higher cost path but a minimal heuristic sum.
GBFS is mainly used because it terminates quickly with very few iterations. But a common case is where GBFS takes you straight to the wrong goal. These flaws motivate the A-star algorithm.