Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Concept

Greedy Method

Technique

The greedy method is an algorithm design technique in which a solution is built step by step by making, at each step, the choice that is locally optimal, and by not reconsidering past choices. It is often used to solve combinatorial optimization problems. Where a problem depends only on the partial solution for one subproblem, it can be solved by considering only the locally optimal subproblem, which makes a greedy algorithm a special case of a dynamic programming algorithm in which only one partial solution is maintained. In many cases a greedy algorithm does not produce an exact solution, but it can yield solutions that approximate an exact solution in a reasonable amount of time. Algorithms recorded in this atlas are grouped here when their design technique is greedy.

Facts
Core Principle
Always take the best immediate, or local, solution while finding an answer. 1
Connections

In Field

Algorithms and Complexity Theory, Fields

Technique Used By

Beam Search, Algorithms
Birkhoff Algorithm, Algorithms
Boruvka's Algorithm, Algorithms
Bowtie (sequence analysis), Algorithms
Decision tree learning, Algorithms
Source IBM: What is a decision tree?
Fleury's Algorithm, Algorithms
Gradient Boosting Algorithm, Algorithms
Greedy Algorithm, Algorithms
Greedy Randomized Adaptive Search Procedure, Algorithms
Hierholzer's Algorithm, Algorithms
Huffman Coding Algorithm, Algorithms
ID3 Algorithm, Algorithms
Kruskal's Algorithm, Algorithms
Louvain Method, Algorithms
Metric K-Center, Algorithms
Minimum k-Cut, Algorithms
Nearest Neighbour Algorithm, Algorithms
Neighbor joining, Algorithms
Patience Sorting, Algorithms
Polygon Triangulation Algorithm, Algorithms
Prim's Algorithm, Algorithms
Reverse-Delete Algorithm, Algorithms
Shortest seek first, Algorithms
Source Arpaci-Dusseau Books: Operating Systems: Three Easy Pieces, Hard Disk Drives chapter
Smoothsort, Algorithms
Steinhaus-Johnson-Trotter Algorithm, Algorithms
Submodular set function, Algorithms
Vertex k-Center Problem, Algorithms
Sources
1. NIST DADS: greedy algorithm
Definition
Quote, Definition
always takes the best immediate, or local, solution while finding an answer
View the Source
Wikipedia: Greedy algorithm
Wikipedia, lead section
Quote, Wikipedia, lead section
A greedy algorithm is an algorithm which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices.
View the Source
Arpaci-Dusseau Books: Operating Systems: Three Easy Pieces, Hard Disk Drives chapter
Arpaci-Dusseau BooksTechnique Used By: Shortest seek first, Section 37.5 Disk Scheduling, opening paragraph, before SSTF
Quote, Technique Used By: Shortest seek first, Section 37.5 Disk Scheduling, opening paragraph, before SSTF
and thus (greedily) pick the one that will take the least time to service first
View the Source
IBM: What is a decision tree?
IBMTechnique Used By: Decision tree learning, Section on how decision tree learning works
Quote, Technique Used By: Decision tree learning, Section on how decision tree learning works
Decision tree learning employs a divide and conquer strategy by conducting a greedy search to identify the optimal split points within a tree.
View the Source
Wikipedia: Greedy algorithm
In Group: Algorithm Design Strategies, Lead
Quote, In Group: Algorithm Design Strategies, Lead
A greedy algorithm is an algorithm which, at each step, makes the choice that is locally optimal, and subsequently does not reconsider past choices.
View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.