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 | ||
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 | ||
