Greedy Algorithm

Greedy algorithms are an approach to solving certain kinds of optimization problems. Greedy algorithms are similar to dynamic programming algorithms in that the solutions are both efficient and optimal if the problem exhibits some particular sort of substructure. A greedy algorithm builds a solution by going one step at a time through the feasible solutions, applying a heuristic to determine the best choice. A heuristic applies an insight to solving the problem, such as always choose the largest, smallest, etc.

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

Overview:

In general, greedy algorithms have five components:

1. A candidate (set, list, etc), from which a solution is created
2. A selection function, which chooses the best candidate to be added to the solution
3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
4. An objective function, which assigns a value to a solution, or a partial solution, and
5. A solution function, which will indicate when we have discovered a complete solution