4 Greedy algorithms

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:

Problem Explanation
1. Activity selection problem At each step the algorithm always select a compatible activity with earliest deadline./td>
2. Largest rectangle problem  
3. Huffman Codeing At each step the algorithm always create a Huffman Tree node for two lowest frequency symbols.
4. Travelling salesman problem At each step the algorithm always explore a new vertex by traversing along the minimum spanning tree.
5. Fractional backpack At each step the algorithm always select an item with highest density.
6. Set cover problem At each step the algorithm always select a set which contains the most uncovered elements.


© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk