Greedy algorithms are mainly used for solving combinatorial optimization problems. Such problems require a set of variables to be determined so that some objective functions could be maximized or minimized. Typical greedy algorithms construct their solutions stepwise and at each step make choices (determine one or several variables’ values) that tend to be best at the moment. Usually a greedy algorithm will perform no backtracking once a variable’s value is decided, while on the contrast, a brute force searching algorithm will do backtracking and try every candidate solution.
Greedy algorithms usually benefit from their none-backtracking feature and run rather fast. However the optimality of its solutions also suffers from this. The hope is that the locally optimal choices at each step will lead to a final globally optimal solution. This could be achieved for some problems, but is hardly the case for many others.
For most problems where greedy strategies work, optimal substructures could be observed. That is, an optimal solution to the problem contains optimal solutions to the sub-problems [1][2].
Many optimization problems are known to be NP-hard. This implies nearly impossible polynomial time algorithms, including greedy ones, for finding optimal solutions. However in some situations greedy algorithms could provide fairly good solutions not too far away from optimal. This kind of algorithms is also called approximate algorithms.
Examples of greedy algorithms:
|