Greedy algorithm
A greedy algorithm builds a solution incrementally by choosing the locally best available option at each step, without generally accounting for all future consequences or revising prior choices.
Optimization Algorithms: AI techniques for design, planning, and control problems
Greedy decoding constructs an output sequence by selecting the locally highest-scoring available choice at each decoding step.
- How it is used
- Builds solutions through repeated local choices, from cargo-bike loading to model-based TSP decoding.
- How deep it goes
- Works through a constrained loading example and model configuration, but does not establish optimality guarantees.
- Examples
- Uses profit-per-kilogram cargo loading and greedy decoding of a pretrained model on a TSP instance.
- What you can do after
- Operate a pretrained PyTorch model by configuring greedy decoding for TSP inference.
Advanced Algorithms and Data Structures
A solution method that repeatedly makes the locally best available choice according to a specified ranking or criterion.
- How it is used
- Uses greedy choices to frame optimization problems such as packing goods and finding shortest routes.
- How deep it goes
- Defines local choice and illustrates where it succeeds or fails, without giving a general proof technique.
- Examples
- Compares food packing by calories or calories per kilogram with shortest-route selection and local optimization.
- What you can do after
- Evaluate whether a locally best choice fits a problem’s constraints before relying on a greedy solution.
Read how Advanced Algorithms and Data Structures explains greedy algorithm →
Natural Language Processing in Action, Second Edition
Greedy search generates a sequence by selecting the highest-probability next token at each step without planning over alternative continuations.
- How it is used
- Uses greedy search to generate GPT-2 text by repeatedly selecting the next token.
- How deep it goes
- Defines one-step token selection and shows probability ranking, then notes repetition loops without deriving the algorithm formally.
- Examples
- Ranks “ new” and “ non” after “NLP is a” and shows repeated data-structure text.
- What you can do after
- Apply Hugging Face GPT-2 generation and adjust temperature or repetition penalties to change token selection behavior.
Read how Natural Language Processing in Action, Second Edition explains greedy algorithm →
Grokking Algorithms, Second Edition
A greedy algorithm constructs a solution by repeatedly making locally best choices without generally reconsidering earlier choices.
- How it is used
- Builds solutions through locally best choices and provides fast approximations when exact solutions take too long.
- How deep it goes
- Defines local and global choices, walks through successful and failed examples, and gives an O(n²) set-covering implementation.
- Examples
- Uses classroom scheduling and a 35-pound knapsack to show when greedy choices succeed or miss the optimum.
- What you can do after
- Evaluate whether a local-choice strategy finds an exact answer or a fast approximation, and implement repeated best-coverage picks.
Read how Grokking Algorithms, Second Edition explains greedy algorithm →
Effective Conversational AI
Greedy decoding is a language-generation strategy that selects the highest-scoring next token at each step.
- How it is used
- Supports repeatable LLM generation for intent-data augmentation, conversation summaries, and debugging.
- How deep it goes
- Defines next-token selection as choosing the most probable word and notes repeatability, without detailing decoding internals.
- Examples
- Illustrates password-phrase generation, repeatable conversation summaries, and recipe-response debugging.
- What you can do after
- Operate generation with greedy decoding to obtain repeatable outputs for a given input.
Read how Effective Conversational AI explains greedy algorithm →
Deep Learning with Python, Third Edition
A decoding strategy that selects the most likely predicted token at each step without considering future alternatives.
- How it is used
- Selects the next token during text generation by choosing the model’s most likely prediction at each step.
- How deep it goes
- Defines the strategy and demonstrates its implementation, while noting that it ignores future alternatives.
- Examples
- Uses an argmax function as the greedy strategy passed into a text-generation loop.
- What you can do after
- Apply it via Keras operations by selecting the highest-scoring token with argmax in a generation loop.
Read how Deep Learning with Python, Third Edition explains greedy algorithm →
Transformers in Action
Greedy decoding generates a sequence by selecting the highest-probability next token at each step without retaining alternative continuations.
- How it is used
- Controls token selection during text generation by choosing the most probable next token at each step.
- How deep it goes
- Defines stepwise conditional-probability selection and explains that locally likely choices can miss coherent or globally optimal continuations.
- Examples
- Illustrates greedy choices with a maze analogy and a sentence-completion prompt generated with sampling disabled.
- What you can do after
- Apply greedy decoding with Hugging Face model.generate by setting do_sample=False and a maximum token limit.
Machine Learning Algorithms in Depth
A greedy algorithm repeatedly selects a locally optimal option in the hope of obtaining a globally optimal solution.
- How it is used
- Frames greedy choice as an algorithmic paradigm for optimization tasks, including knapsack selection and sensor placement.
- How deep it goes
- Defines local-choice heuristics, implements fractional knapsack, and links submodularity to guarantees without deriving a general proof.
- Examples
- Works through fractional knapsack and describes sensor placement using incremental mutual information.
- What you can do after
- Build a fractional-knapsack solver by ranking items by value-to-weight ratio and taking fractions when capacity runs short.
Read how Machine Learning Algorithms in Depth explains greedy algorithm →
Build a Large Language Model (From Scratch)
A decoding strategy that always selects the highest-probability next token at each generation step.
- How it is used
- Uses next-token inference as a deterministic baseline for generating text with a GPT model.
- How deep it goes
- Explains the iterative PyTorch loop, tensor positions, context truncation, softmax, argmax, and concatenation.
- Examples
- Demonstrates “Hello, I am” generation through encoded IDs, six iterations, decoded output, and an untrained model’s gibberish.
- What you can do after
- Apply it via PyTorch to generate and decode a fixed number of tokens from an encoded context.
Read how Build a Large Language Model (From Scratch) explains greedy algorithm →
Deep Learning with R, Third Edition
Greedy search is a sequence-generation strategy that selects the most probable next token at every generation step.
- How it is used
- Uses a per-step highest-probability token choice as a baseline strategy for generating text.
- How deep it goes
- Defines per-step maximum-probability selection and implements it with argmax, briefly contrasting random sampling.
- Examples
- Shows `greedy_search()` using `op_argmax` and notes that an early-trained model may repeat “the.”
- What you can do after
- Apply it via `op_argmax` as the sampling function passed to `compiled_generate()`.
Read how Deep Learning with R, Third Edition explains greedy algorithm →
Fabulous Adventures in Data Structures and Algorithms
A greedy algorithm constructs a solution by repeatedly choosing the locally best available option without generally reconsidering earlier choices.
- How it is used
- Uses greedy choices to reformat source code quickly when an acceptable result matters more than finding an optimal one.
- How deep it goes
- Defines subproblem optimization and demonstrates its trade-off with successful and failing change-making cases.
- Examples
- Uses US coin change for 73 cents and 41 cents without nickels, alongside source-code pretty printing.
- What you can do after
- Evaluate whether a fast greedy solution is acceptable by comparing it with a slower optimal alternative.
Read how Fabulous Adventures in Data Structures and Algorithms explains greedy algorithm →
Build a Reasoning Model (From Scratch)
A decoding strategy that always selects the highest-probability next token instead of sampling randomly.
- How it is used
- Uses highest-scoring token selection to implement sequential text generation during LLM inference.
- How deep it goes
- Explains score extraction, argmax indexing, shape preservation, decoding, and iterative reuse, while deferring alternative decoding strategies.
- Examples
- Demonstrates torch.argmax on score vectors and decodes token ID 20286 into “Large.”
- What you can do after
- Apply greedy decoding with PyTorch to select and decode each next token in an autoregressive generation loop.
Read how Build a Reasoning Model (From Scratch) explains greedy algorithm →
Related concepts
- top-k samplingequivalent to · Top-k sampling is a decoding technique that restricts each next-token selection to the k candidates with the highest probabilities, then samples from those candidates.
- Dijkstra's algorithmused by · Dijkstra's algorithm computes shortest paths from a source vertex in a weighted graph with nonnegative edge weights.
- samplingcontrasts with · Sampling is a procedure for selecting or generating observations, values, or outcomes from a larger population, signal, or probability distribution according to a specified method.
- beam searchalternative to · Beam search is a heuristic search and decoding technique that iteratively expands a limited set of the highest-scoring partial candidates.
- argmaxequivalent to · Argmax is an operation that identifies an argument, position, or index at which a function or collection attains its maximum value.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.