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 SpacesThe 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.
|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||AlgorithmsMachine Biases|
This is the complete list of articles we have written about algorithms.
If you enjoyed this page, please consider bookmarking Simplicable.
© 2010-2023 Simplicable. All Rights Reserved. Reproduction of materials found on this site, in any form, without explicit permission is prohibited.
View credits & copyrights or citation information for this page.