How Greedy Best-First Search Works
Greedy best-first search always expands the intersection that looks closest to the goal, ignoring how far it has already come. It is often astonishingly fast and often returns a route that is not the shortest.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(d) | O(E log V) | O((V + E) log V) | O(V) |
d is the length of the route in intersections. A dead end pointing at the goal - a river, a park, a stretch of coast - can drag it into the worst case.
How greedy best-first search works
Greedy best-first search keeps the same priority queue as A* but orders it by the heuristic alone: the straight-line distance to the goal. Whatever looks closest gets expanded next, no matter how long the detour to reach it was. On an open grid that makes a nearly straight dash at the target, settling barely more intersections than the route itself. Around an obstacle it can commit to the wrong side, and because it never weighs distance travelled, it has no reason to come back and fix the route.
- Push the start with priority h(start), the straight-line distance to the goal.
- Pop the intersection that looks closest to the goal. If it is the goal, walk the parents back.
- Push every unseen neighbour with priority h(neighbour), recording where it was reached from. The first parent stays; nothing is ever relaxed.
When to use it
- Use it when any route will do and speed matters more than length: a first guess, a game unit that just needs to start moving.
- Avoid it when the length of the route matters. A* costs a little more and is guaranteed shortest with the same heuristic.
Check yourself
Why can greedy best-first return a longer route even when the heuristic is perfect for straight lines?
Because it ignores g, the distance already travelled. It happily extends a long detour whose tip is close to the goal instead of a short route whose tip is slightly further away.