Is greedy search always the fastest method?

No. Repeatedly scoring all candidates or following misleading paths can still be costly.

Can a greedy method find the optimal answer?

Yes, for suitable problems and rules with the necessary justification; the term alone provides no guarantee.

Is choosing the most likely next token a greedy method?

Yes, greedy decoding makes that local choice, but it need not maximize the probability of an entire completed sequence.

AI Glossary / Computer vision and multimodal AI / Beginner

Greedy search

Definition

Greedy search is an approach that repeatedly chooses the option that appears best according to a local rule. It builds an answer through immediate choices instead of systematically comparing every possible complete answer. The term can describe greedy algorithms broadly; in AI search, greedy best-first search specifically prioritizes states using an estimate of their remaining distance or cost to a goal.

What it means

The central question is what “best now” means. It might mean the largest immediate gain, the cheapest next connection, or the smallest estimated distance remaining. Those criteria can lead to different answers on the same problem. A choice that looks attractive in isolation can prevent a better combination later.

Greedy does not automatically mean careless or incorrect. Some problems have a structure that makes a particular greedy rule provably optimal. For other problems, it is a practical heuristic or an approximation with a limited guarantee. The rule, objective, constraints, and proof conditions matter more than the label.

How it works

First define the objective and the set of allowed actions. Score the available choices using the selected local criterion. Choose the preferred feasible option, update the partial solution or search frontier, and repeat until a stopping condition is met.

A constructive greedy algorithm commonly commits to choices without revisiting them. Greedy best-first search instead maintains candidate states and expands the one with the lowest heuristic estimate h; it does not prioritize the accumulated path cost in the same way as uniform-cost search. Tracking previously visited states can prevent redundant exploration, but it does not turn an unreliable heuristic into an optimality proof.

Three practical examples

1. An image annotation team chooses each next photograph by the number of currently uncovered object categories it contains. The greedy selection can create a useful coverage baseline, but redundant combinations and rare categories need attention.

2. A route explorer expands the location that appears closest to its destination on a map. A river or restricted crossing can make that seemingly direct option expensive.

3. A feature selection experiment adds the variable that most improves validation performance at each step. Two variables that are valuable together may be missed when neither has much individual benefit.

Think of it this way

Think of filling a basket by repeatedly choosing the most attractive item that still fits. The rule is easy to explain and quick to apply, but the first bulky item may leave awkward gaps. A different combination could have delivered more total value. The analogy illustrates local commitment; actual greedy algorithms can have rigorous mathematical guarantees when the problem has the required structure.

Worked example

Suppose a dispenser has unlimited tokens worth 1, 3, and 4 units. The task is to make 6 units using the fewest tokens. A greedy rule selects the largest token that does not exceed the remaining amount.

It first selects 4, leaving 2. It then selects 1 and another 1. The total is correct, but three tokens were used. Choosing 3 and 3 makes the same amount with two tokens, so this greedy rule is not optimal for this token system.

This small counterexample is enough to disprove a universal claim that largest-first always minimizes token count. It does not prove that every greedy rule fails, or that the same rule fails for every possible denomination system. The example demonstrates why checking only familiar cases can create false confidence.

Illustrative case study

Fictional case: A visual search startup needs a small demonstration gallery covering many product attributes. Its first selection tool repeatedly picks the image that adds the most uncovered attributes. The resulting gallery is fast to produce and easy to audit.

An editor notices that several rare materials remain absent because common attributes dominated the early choices. The team adds explicit coverage requirements and compares the greedy gallery with a small exhaustive search on a manageable subset. It records which constraints are guaranteed and which preferences are only optimized heuristically. The exercise produces a clearer selection policy without claiming that the original gallery was globally best.

Common misconceptions and mistakes

A local improvement is not evidence of a globally optimal final answer. Neither speed nor an intuitive scoring rule supplies that proof. Conversely, it is incorrect to dismiss all greedy methods as approximate: some specific algorithms are exact under stated assumptions.

Do not confuse greedy best-first search with A*. Their usual priorities differ: greedy best-first uses h, while A* uses accumulated cost g plus h. Also avoid assuming that a high-quality heuristic makes every search variant complete or optimal under all graph and stopping conditions. Compare methods on the same objective, feasibility rules, and computational budget.

Business use

Greedy methods are useful for transparent baselines, interactive tools, selection problems, and situations where evaluating all combinations is impractical. A business team can often explain why each individual decision was made, which helps identify undesirable incentives in the score.

Before deployment, test adversarial small examples and compare against exact solutions where feasible. Record final objective value, constraint violations, runtime, and sensitivity to tie breaking. When a missed combination has a high cost, a greedy result can serve as an initial candidate for subsequent improvement rather than the sole basis for action.

Check your understanding

A greedy selection achieves the best immediate gain at every step. Does that prove its final combination has the highest possible total value?

Answer: No. Earlier choices can restrict later combinations. An optimality proof or an appropriate problem-specific guarantee is needed; otherwise compare the result with alternatives and report the limitation.

Related terms

Heuristic search
Greedy best-first search
Beam search
Dynamic programming
Feature Selection
A* search
combinatorial optimization
approximation algorithm

Learn next

Create a tiny selection problem with five candidates and a limit of two selections. Write the local greedy rule, enumerate every allowed pair, and compare the totals. Then change the constraints and identify whether the original rule still makes sense.

Selection problem

Sources

Primary teaching sources: Carnegie Mellon University, “The Greedy Method,” https://www.cs.cmu.edu/~cburch/pgss97/slides/0718-greed.html ; Carnegie Mellon University, “Search and Games,” https://www.cs.cmu.edu/~15281/coursenotes/search/index.html . Relevant returned material was reviewed. The token, gallery, and selection examples are original illustrations; they do not assert a universal performance guarantee.

Previous: Greedy policy Next: Green-based demosaicking