liveBook · Manning

Greedy best-first search

As explained in Algorithms Every Programmer Should Know

Greedy best-first search expands the candidate with the most promising heuristic estimate without accounting for the cost already incurred.

Greedy best-first search expands the node whose heuristic h(n) makes it look closest to the goal. It ignores the cost already spent getting there, so it can be fast but follow a promising route into a dead end or long detour. A* also considers the cost so far. section 12.1

Use it when finding a good path quickly matters more than guaranteeing the lowest-cost path. Weighted A* offers another alternative when that tradeoff is acceptable. section 12.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines the heuristic-only strategy and its tradeoff, without tracing or implementing the algorithm.
What you can do after
Evaluate whether giving up guaranteed path optimality is worthwhile in exchange for fewer explorations.
How it connects
Contrasts greedy best-first search with A* and names weighted A*, Dijkstra’s algorithm, and IDA* as alternatives.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.