Does best-first search require machine learning?

No. A hand-designed evaluation function is sufficient.

Is A* always faster than uniform-cost search?

No universal runtime advantage follows; heuristic quality and evaluation overhead matter.

Can the frontier grow very large?

Yes. Prioritizing alternatives does not impose a fixed memory bound.

AI Glossary / Graphs and symbolic AI / Intermediate

Best-first search

Definition

Best-first search is a family of search methods that repeatedly expands the most promising waiting node according to an evaluation function. In the usual minimum-score formulation, the node with the smallest value of f(n) is selected next.

What it means

The word best describes a ranking rule, not a guarantee that the next choice leads to the best final answer. A search frontier contains alternatives that have been discovered but not yet expanded. Best-first search orders that frontier using a score.

Different scores create different behaviors. Uniform-cost search uses the cost already accumulated, g(n). Greedy best-first search uses an estimate of the remaining cost, h(n). A* combines them as g(n) + h(n). These methods share a selection pattern but have different conditions for completeness and optimality.

This distinction matters when a product description says only that it uses best-first search. Without the scoring rule, stopping condition and treatment of repeated states, the phrase says little about solution quality. A fast-looking heuristic can steer the search into an expensive route.

How it works

Begin with an initial node in a priority queue. Remove the node with the best priority, test whether it satisfies the goal under the chosen algorithm's stopping rule, and generate its successors when expansion is required. Compute their scores and add or update eligible candidates.

Graph searches must handle repeated states. Two different paths can reach the same location with different costs. Retaining the cheaper path may require updating a waiting entry or reopening a previously expanded state, depending on the algorithm and heuristic properties.

For A*, admissible heuristics do not overestimate remaining cost. Appropriate graph-search handling is still needed; consistency is a stronger condition that simplifies treatment of expanded states. These qualifications belong to the specific algorithm rather than to every best-first method.

Memory is another practical limit. Keeping a large frontier and records of reached states can consume substantial space even when the ordering reduces unnecessary expansions. Queue ties also need a policy, although a tie-breaking choice is not itself a new objective.

Three practical examples

A route planner uses A* to balance distance traveled against a lower-bound estimate of distance remaining.
A puzzle solver uses greedy best-first search to explore states that appear close to a target arrangement, accepting that the first solution may be longer than necessary.
A workflow planner uses uniform-cost search when it has meaningful action costs but no useful estimate of remaining effort.

Think of it this way

Think of a dispatcher sorting unfinished jobs by a priority column. Sorting by work already spent, estimated work remaining or their sum produces different next choices.

The analogy is limited because expanding a search node creates new alternatives and may reveal that an earlier route was inferior. A fixed list of office jobs does not automatically reproduce these state and path relationships.

Worked example

One graph, two rankings

Suppose the start S connects to A at cost 1 and B at cost 4. A connects to goal G at cost 10; B connects to G at cost 1. The two complete route costs are therefore 11 and 5.

Let h(A) = 1, h(B) = 1 and h(G) = 0. Greedy search sees a tie between A and B. If it selects A first, it generates G with heuristic score 0 and can return the route costing 11 when that goal is selected.

A* initially ranks A at 1 + 1 = 2 and B at 4 + 1 = 5. It expands A first, but the resulting goal has score 11. B still has score 5, so it is expanded before that goal. It generates a better path to G costing 5, which replaces the more expensive candidate under proper duplicate handling.

The example shows why considering accumulated cost changes the result. It does not show that every heuristic or implementation makes A* correct.

Illustrative case study

Fictional case: Cedar Routing compares two planning prototypes on a small warehouse map. Both are described internally as best-first search, but one ranks positions only by straight-line distance to the destination.

That prototype often heads towards a nearby wall and takes a long detour. The other includes distance already traveled and retains better paths to previously discovered positions. The team documents the actual scoring functions and compares returned route costs against reference answers on small maps.

It also measures memory and elapsed time. The resulting decision rests on defined behavior, not the reassuring word best. No fictional performance percentage is presented as a measured deployment result.

Common misconceptions and mistakes

Best-first always means greedy search. Greedy search is one member of the broader family.
The first generated goal must be optimal. Some algorithms must wait until the goal is selected with the appropriate priority.
A priority queue alone guarantees correctness. State tracking, cost updates and stopping rules also matter.
A good-looking estimate is necessarily admissible. Its relationship to actual remaining cost must be established.
Best-first and Best Node Search are synonyms. The latter names a particular game-tree method.

Business use

For business planning, define what the score represents before comparing implementations. Distance, time, money and risk are different quantities; combining them requires explicit units or a justified objective.

Request evidence about solution cost, unsuccessful searches, memory use and worst observed delays. If a system stops early under a time budget, label the resulting quality claim accordingly. A useful route found quickly and a proven minimum-cost route can meet different operational needs.

Check your understanding

A system ranks nodes only by estimated remaining distance. Does the name best-first establish that its first route has minimum total distance?

Answer: No. That is a greedy ranking; minimum-total-cost claims require additional algorithmic conditions and evidence.

Related terms

Learn next

Draw the four-node graph in the worked example and list the queue after each expansion. Run it using h alone, g alone and g + h. Record when the goal is generated and when it is selected, then explain why those events differ.

Sources

AIMA glossary, best-first search and associated search terminology: https://github.com/aimacode/aima-glossary/blob/master/glossary.md?plain=1

AIMA educational search implementation, showing evaluation-function-based selection and search variants: https://aima.cs.berkeley.edu/python/search.html

The route calculation and fictional comparison are original teaching examples.

Previous: Best bin first Next: Best node search