Greedy Algorithm
Definition
Greedy algorithm is a method of making choices that only considers the current moment and selects the best possible option.
Description
As its name suggests, the greedy algorithm focuses on the immediate without taking a long-term perspective. Speaking positively, it’s always trying to do its best, but this may not always be wise when looking at the bigger picture. Consider the following example:
Let’s say there’s a problem of finding a path from the left 0 to the right 1. Not just finding any path, but one that crosses the fewest nodes. The optimal solution would be 0-A-C-E-1(3). However, the greedy algorithm would choose the path that seems longest at each moment. Hence, if this problem was approached with a greedy algorithm, the solution would be 0-B-D-F-G-H-1(5), incurring an extra cost of 2 compared to the optimal solution. If the first choice wasn’t 0-B, or even if it was D-E instead of D-F, a better solution could have been chosen.
In this manner, the greedy algorithm is more likely considered a ‘foolish approach’ rather than a ‘good algorithm’ in most contexts. However, for problems complex enough to necessitate an algorithm, like the example above, it won’t be as simple as just taking a quick look. That’s why usually, a naive solution using the greedy algorithm is attempted first, and then an improved algorithm is developed.