What does greedy best-first search minimize when choosing a node?

It minimizes the current heuristic estimate among available frontier candidates, subject to tie-breaking.

Can an exact remaining-cost heuristic still lead to an expensive solution?

Yes. The worked example does so because the rule ignores accumulated path cost.

Does it always expand fewer nodes than A*?

No. Relative effort depends on the graph, heuristic, duplicate handling, and stopping conditions; there is no universal speed advantage.

AI Glossary / Graphs and symbolic AI / Intermediate

Greedy best-first search

Definition

Greedy best-first search is a search strategy that expands the frontier node with the lowest estimated remaining cost to a goal. Its priority is the heuristic value h(n), rather than the cost already spent reaching the node. It aims to reach a goal quickly, but it does not generally guarantee a least-cost solution.

What it means

The method asks which available candidate appears closest to success according to a supplied estimate. That estimate may be geographical distance, a count of misplaced puzzle pieces, or another problem-specific measure. The word greedy describes this immediate preference for the most promising-looking next candidate.
The strategy still maintains a frontier of alternatives. It is not necessarily a single-path procedure that permanently commits to one move. Its defining feature is how that frontier is ordered. A candidate with a very expensive route behind it can outrank a cheaper alternative if its estimated distance ahead is smaller.

How it works

Put the start node in a priority queue ordered by h. Repeatedly remove a minimum-heuristic candidate, test for a goal according to the implementation, and add eligible successors. Use appropriate repeated-state handling to avoid unnecessary cycles or duplication.
The priority rule can be written f(n) = h(n). This differs from uniform-cost search, which orders by accumulated cost g(n), and A*, which commonly uses g(n) + h(n). Tie-breaking and duplicate policies can change the explored sequence. A useful heuristic may guide greedy search effectively, but attractive estimates alone do not establish completeness or optimality across every state space.

Three practical examples

A classroom route-search demonstration expands locations with the smallest estimated distance to the destination and compares the result with uniform-cost search.
A puzzle experiment uses a heuristic to prioritize promising arrangements, recording both solution quality and exploration effort.
A planning prototype tests whether a heuristic reaches acceptable candidate solutions within a limited search budget, while keeping optimality claims separate.

Think of it this way

Think of choosing which branch of a trail to investigate by a sign estimating distance remaining, without considering how far you have already walked. This captures the priority rule. The analogy is limited because the search can retain several alternative branches in its frontier and revisit its choices systematically; it is not simply a person following one sign forever.

Worked example

Consider a directed graph with edges S-A costing 100, A-G costing 1, S-B costing 1, and B-G costing 2. Let the heuristic values be h(A) = 1, h(B) = 2, and h(G) = 0. These estimates equal the actual remaining costs from A and B.
After expanding S, greedy best-first search compares A's heuristic 1 with B's heuristic 2 and chooses A. It then generates G, whose heuristic is 0, and can return the route S-A-G when that goal is selected. Its total cost is 100 + 1 = 101.
The alternative S-B-G costs only 1 + 2 = 3. The mistake is not that the remaining-cost estimates were inaccurate: they were exact in this example. The priority rule ignored the 100 already spent to reach A. For comparison, A* would initially give A priority 100 + 1 = 101 and B priority 1 + 2 = 3. The example demonstrates why even an admissible heuristic does not by itself make greedy best-first search optimal.

Illustrative case study

In a fictional teaching project, Alder Routes displays both the next node chosen and the eventual route cost. Students first assume that a precise distance-to-goal estimate must produce the cheapest route. The two-branch example disproves that assumption.
The team adds separate displays for accumulated cost and estimated remaining cost. It then runs different frontier-ordering rules on the same graph. The invented case illustrates algorithm comparison; it makes no claim that one strategy is fastest across real navigation tasks or that a small demonstration predicts production performance.

Common misconceptions and mistakes

Greedy best-first search is not A*. Both can use the same heuristic while making different choices because A* also considers accumulated cost. Nor does an admissible heuristic supply greedy search with A*'s usual optimality guarantees.
The strategy is also different from hill climbing, which typically works from a current candidate rather than maintaining the same kind of frontier of alternatives. Avoid an unconditional claim that greedy search is always incomplete: finite-state graph search with appropriate duplicate handling has different behavior from tree search or search in an infinite state space. State the relevant conditions.

Business use

The method is useful for exploring the trade-off between finding a solution quickly and guaranteeing its quality. It can provide a straightforward heuristic baseline in a planning or search experiment. Whether it is suitable depends on how costly poor solutions are and how informative the heuristic is.
Evaluate more than the number of expanded nodes. Record solution cost, failures, time, memory, and the tested problem distribution. If the project needs a guaranteed least-cost answer, select an algorithm whose guarantees match the model and assumptions. Do not relabel a fast candidate solution as an optimal one merely because the heuristic looked convincing.

Check your understanding

Why does greedy search prefer A in the worked example despite the costly edge from S?

Answer: Its priority is h(A) = 1, which is lower than h(B) = 2. The priority rule does not add the cost of reaching A, so the 100-cost edge does not prevent that choice.

Related terms

Learn next

Trace greedy best-first search, uniform-cost search, and A* on the same weighted graph. Write both g and h next to every frontier node. Compare the ordering rules before comparing the final paths, so that differences in behavior have an explicit explanation.

Sources

Sources: AIMA code documentation, search algorithms: https://aima.cs.berkeley.edu/lisp/doc/overview-SEARCH.html AIMA Python search documentation: https://aimacode.github.io/aima-python/searching.html

Previous: Greedy algorithms Next: Greedy decoding