What are Greedy Algorithms?

John Spacey, updated on September 23, 2016

Greedy algorithms are a category of algorithm that make locally optimal choices in hopes of coming close to a globally optimal solution. For example, an algorithm that needs to make 12 decisions may make one at a time as opposed to looking at all possible combinations of decisions.

Problem Spaces

The effectiveness of greedy algorithms depends on the problem space. If there is some risk that an early decision will paint the algorithm into a corner, they may perform poorly. Greedy algorithms are known to perform poorly in a game such as chess where players commonly consider strategy many moves ahead.

An example of a greedy algorithm that may work is a tourist restaurant with no repeat customers that aggressively tries to upsell food items. If the restaurant depended on regular customers such annoying tactics could drive them out of business. However, since all the customers are new it makes sense for the restaurant to try to maximize each sale without regard to the future relationship with the customer. This strategy soon collapses if customers are able to share their opinions with technology such as reputation systems.

Why Go Greedy?

Greedy algorithms are often selected when global data is uncertain, making globally optimized solutions impossible or expensive to develop. It is also common to select greedy algorithms for their simplicity and speed. In many problem spaces, calculating globally optimized solutions is prohibitively complex and resource intensive.

Overview: Greedy Algorithms
Type	Algorithms
Definition	A category of algorithm that makes locally optimal choices in hopes that these will come close to a globally optimized solution.
Value	Typically cheaper to develop, faster and less resource intensive than a globally optimized algorithm. In some cases, globally optimized solutions are impossible due to factors such as uncertainty.
Risks	Greedy algorithms are typically sub-optimal. In some problem spaces, such as chess, they are extremely sub-optimal to the point of being useless.
Related Concepts	Algorithms Machine Biases